The p-1 method is used to factor primes for instance p & q such that n = p*q and avoid weaknesses in the implementation of the algorithm.
The method works well when q-1 or p-1 can be factored as a product of given small primes.
Therefore to factor 618240007109027021, we first compute;
2^(100!) mod n using Power (2,100!) mod n
In our case;
n := 618240007109027021
a1:Â = 100!;
t1Â :Â = Power (2,a1) mod n
a1 = 9.3326215443944152681699238856267e+157
t1 = 78737314835659020
Then we find a factor of n, test if it’s prime, and evaluate how p-1 factors;
factor1:= igcd (t1 – 1, n); // use gcd to find the factor
isprime(factor1) //test if factor is prime
ifactor(factor1-1) //if the factor is prime, test how p-1 factors
so factor1 = 250387201
And it’s true (2)8 (3)5 (5)2 (23) (7)
To find the second factor q, we simply divide n by p and also evaluate how q-1 factors;
Factor2:= n/factor1; // divide n by factor1 to obtain q (factor2)
isprime(factor2) //test if q is prime
ifactor(factor2-1) //if the factor is prime, test how q-1 factors
factor2 = 2469135821
And it’s true, (2)2 (5) (123456791)
