The Pollard p - 1 Factoring Method

Table[{NextPrime[10^j,-1], FactorInteger[NextPrime[10^j,-1]-1]},{j,1,40}]//TableForm

We see from this that the following prime has the property that p - 1 has only small prime factors (less than 750000).

p=9999999999999999961

PrimeQ[p]

q=RandomPrime[10^60]

n=p*q

The following takes a huge amount of time.

FactorInteger[n, 2]

But we can run through a loop to compute 2^(750000!) mod n.

b=2; Do[b=PowerMod[b,j,n], {j,750000}]; b

GCD[b-1,n]