Factoring large integers: pollard p-1 method
It is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a special-purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest example of an algebraic-group factorisation algorithm.
From Wikipedia
Pollard p-1 algorithm
- N > 2
- b = ( a finite integer )
- Let k be a multiple of all (or nearly all) integers <= b ( i.e k = b )
- 2 <= a <= N - 2 ( with a random )
- Compute Greatest Common Divisor (GCD) between a^k-1(mod N) and N
- So we need to comput a^k-1 in ZN and to find the Greatest Common Divisor between this value and N ( i.e : use the Euclid’s algorithm )
- If GCD = 1 then return to 4. ; else if GCD > 1 then GCD is a prime number and we found a factor of N
