C#, первообразный корень

[zhenya.ya]

Есть проблема в получении первообразного корня по модулю p: при довольно небольших p корни получаются, но при большом p (порядка p = 750070109400197 и более) - повисает! Что не так?!

public BigInteger GetPRoot(BigInteger p)
        {
            for (BigInteger i = 0; i < p; i++)
                if (IsPRoot(p, i))
                    return i;
            return 0;
        }
 
        public bool IsPRoot(BigInteger p, BigInteger a)
        {
            if (a == 0 || a == 1)
                return false;
            BigInteger last = 1;
            HashSet<BigInteger> set = new HashSet<BigInteger>();
            for (BigInteger i = 0; i < p - 1; i++)
            {
                last = (last * a) % p;
                if (set.Contains(last)) // Если повтор
                    return false;
                set.Add(last);
            }
            return true;
        }