Trying to guess p and q from N by using Diffie-Hellman cycles algorithm, too slow BigInteger.Pow approach

Question

Well,

I implemented a program to find p and q given N.

For p = 11 and q = 7, with a generator of g=2 or g=8 it seems to work pretty well,

But when I use a list of prime numbers given on the internet, it last forever, the point is that actually, BigInteger.Pow is slower than GetCycles method.

This is my code:

using System.Diagnostics;
using System.Numerics;

BigInteger g = 8; // generator
BigInteger p = 7; // 100069; //7;
BigInteger q = 11; // 13093; //11;
var N = p * q; // prime number N

bool GetCycles(out int i)
{
    BigInteger m = 1;
    i = 1;
    var baseValue = g;

    while (baseValue != 1)
    {
        baseValue = baseValue * g % N;
        m = m * g % N;
        m = (m + 1) % N;
        i++;
        if (m == 1)
        {
            break;
        }
    }

    if (i % 2 != 0)
    {
        Console.WriteLine($"{i} must be even.");
        return true;
    }

    return false;
}

var cycles = -1;
var exit = SW("Cycles", () => GetCycles(out cycles));

if (exit) return;

Console.WriteLine("Found cycle: " + cycles);

var r2 = cycles / 2;
var A = BigInteger.Pow(g, r2) + 1;
var B = BigInteger.Pow(g, r2) - 1;

BigInteger GetPrime(BigInteger f)
{
    var n = N;
    var mod = f % n;

    BigInteger solution = 0;

    while (mod != 0)
    {
        var prevMod = mod;
        mod = n % mod;
        n = prevMod;

        if (mod == 0)
            solution = prevMod;
    }

    return solution;
}

var pSolution = SW("A", () => GetPrime(A));
var qSolution = SW("B", () => GetPrime(B));

Console.WriteLine($"p={pSolution}\nq={qSolution}");

T SW<T>(string key, Func<T> action)
{
    var sw = Stopwatch.StartNew();
    var t = action();
    sw.Stop();

    Console.WriteLine($"[{key}] Elapsed {sw.ElapsedMilliseconds} ms!");
    return t;
}

Is there a more optime solution to calculate A & B? Because it's slower than the GetCycles method that lasts like ~9100ms on the GetCycles method for p=13147 and q=13229.