Fermat theorem Lies behind this second factorization scheme, known as pollard p-1 method.
- suppose odd composite integer n to be factored has prime divisor n, with the property that p-1 is a product of relatively small primes. Let q be then any integer such that (p-1)|q. For instance q could be either k! or the least common multiple of first k positive integers, where k is taken sufficiently large. select 1<a<p-1
- $${m\equiv a^q \equiv a^{(p-1)j}\equiv 1^j \equiv1(modp)}$$ implies p | (m-1), this forces ${gcd(m-1,n)>1}$
- But it is important to note here is , if ${gcd(m-1,n)=1}$, then one should go back and select the different value of a.
- The method might fail if q (k!) is not taken to be large enough; that is if p-1 contains large prime factor or a small prime occurring to a large power, hence it is better to choose k!, which will increase the probability of finding if a factor is large prime factor.