Pollard's p-1 Method

Pollard's p-1 method is a prime factorization algorithm discovered by John Pollard in 1974. Limited by the algorithm, the Pollard's p-1 method is only work for integers with specific factors.

If the number n has a prime factor p such that p-1 can be expressed in terms of a product of primes, the finding of prime factor p is based on the selected boundary B of the B-powersmooth number.  The algorithm fails when the selected boundary B is smaller than the B-powersmooth number of p-1.

Pollard's P-1 Methed by PowerSmooth Number

Pollard's P-1 Methed by PowerSmooth Number Example 2

For example: n=667=p*q=23*29; let B=5 imply

Integer	B-smooth number	Prime Factors	number
k	5	22*31*51 = 4*3*5	60

Therefore for B=5, k5 or (p5-1)m5 is equal to 60.

Fermat's Little Theorem

let a=2, by Fermat's little theorem, let p be one of the prime factors of n, imply p idivides ak-1.

Greatest Common Divisor

Since ak-1 is a very large number, before finding the greatest common divisor of n and ak-1,  ak-1 can be raised to the high power modulo n. Imply

Using squarings modulo

base	number; a=2; k=60; n=667
ak base 10	260
ai base 10	21  = 21 ≡ 2 (mod 667)
	22 = 22 ≡ 4 (mod 667)
	24 = 42 ≡ 16 (mod 667)
	28 = 162 ≡ 256 (mod 667)
	216 = 2562 ≡ 170 (mod 667)
	232 = 1702 ≡ 219 (mod 667)
ak base 10	232+16+8+4
ak base 10	232*216*28*24
ak base 10	219*170*256*16 ≡ 538 (mod 667)

and using the residue to calculate the greatest common divisor. Imply 

The greatest common divisor of n and ak-1 is

Using Euclid's algorithm

ak-1	n
260-1	667
538-1	667
537	667-537=130
537-4*130=17	130
17	130-7*17=11
17-11=6	11
6	11-6=5
6-5=1	5
1	5-5*1=0
1	0

Imply

The algorithm fails because the greatest common divisor of n and ak-1 is equal to 1. The number n does not have prime divisor p with p-1 is 5-powersmooth. Therefore the bound B equals to 5 fails, a larger bound B' should be used.

Let B=7,  imply

Integer	B-powersmooth number	Prime Factors	number
k	7	22*31*51*71 = 4*3*5*7	60 * 7 = 420

Therefore for B=7, k7 or (p7-1)m7 is equal to 60*7 = 420. Imply  k7 =  k5 * 7. And  the new ak can be expressed as

And ak can be raised to the high power modulo n, imply

Using squarings modulo

base	number; a=538; k=7*; n=667
ak base 10	5387 (mod 667)
ai base 10	5381  = 5381 ≡ 538 (mod 667)
	5382 = 5382 ≡ 633 (mod 667)
	5384 = 6332 ≡ 489 (mod 667)
ak base 10	5384+2+1 (mod 667)
ak base 10	5384*5382*5381 (mod 667)
ak base 10	489*633*538 ≡ 349 (mod 667)

and using the residue to calculate the greatest common divisor. Imply 

The greatest common divisor of n and ak-1 is

Using Euclid's algorithm

ak-1	n
2420-1	667
349-1	667
348	667-348=319
348-319=29	319
29	319-11*29=0
29	0

Imply

Integer 29, the greatest common divisor of n and ak-1 is also the prime divisor of n. And p-1 is  7-powersmooth.

Integer	B-powersmooth number	Prime Factors	number
p-1	7	22*71	28
k	7	22*31*51*71 = 4*3*5*7	420
k/(p-1)		20*31*51*70	15