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-smooth number.  The algorithm fails when the selected boundary B is smaller than the B-smooth number of p-1.

Pollard's P-1 Methed by Smooth Number

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

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

Integer	B-smooth number	Prime Factors	number
k	5	29*35*54 = 512*243*625	77760000

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

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=77760000; n=667
ak base 10	21296000
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)
	264 = 2192 ≡ 604 (mod 667)
	2128 = 6042 ≡ 634 (mod 667)
	2256 = 6342 ≡ 422 (mod 667)
	2512 = 4222 ≡ 662 (mod 667)
	21024 = 6222 ≡ 25 (mod 667)
	22048 = 252 ≡ 625 (mod 667)
	24096 = 6252 ≡ 430 (mod 667)
	28192 = 4302 ≡ 141 (mod 667)
	216384 = 1412 ≡ 538 (mod 667)
	232768 = 5382 ≡ 633 (mod 667)
	265536 = 6332 ≡ 489 (mod 667)
	2131072 = 4892 ≡ 335 (mod 667)
	2262144 = 3352 ≡ 169 (mod 667)
	2524288 = 1692 ≡ 547 (mod 667)
	21048576 = 5472 ≡ 393 (mod 667)
	22097152 = 3932 ≡ 372 (mod 667)
	24194304 = 3722 ≡ 315 (mod 667)
	28388608 = 3152 ≡ 509 (mod 667)
	216777216 = 5092 ≡ 285 (mod 667)
	233554432 = 2852 ≡ 518 (mod 667)
	267108864 = 5182 ≡ 190 (mod 667)
ak base 10	267108864+8388608+2097152+131072+32768+1024+512
ak base 10	267108864*28388608*22097152*2131072*232768*21024*2512
ak base 10	190*509*372*335*633*25*662 ≡ 426 (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
277760000-1	667
426-1	667
425	667-425=242
425-242=183	242
183	242-183=59
183-3*59=6	59
6	59-9*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-smooth. Therefore the bound B equals to 5 fails, a larger bound B' should be used.

Let B=7,  imply

Integer	B-smooth number	Prime Factors	number
k	7	29*35*54*73 = 512*243*625*343	77760000 * 343 = 26671680000

Therefore for B=7, k7 or (p7-1)m7 is equal to 77760000*343 = 26671680000. Imply  k7 =  k5 * 343. 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=426; k=343*; n=667
ak base 10	426343 (mod 667)
ai base 10	4261  = 4261 ≡ 426 (mod 667)
	4262 = 4262 ≡ 52 (mod 667)
	4264 = 522 ≡ 36 (mod 667)
	4268 = 362 ≡ 629 (mod 667)
	42616 = 6292 ≡ 110 (mod 667)
	42632 = 1102 ≡ 94 (mod 667)
	42664 = 942 ≡ 165 (mod 667)
	426128 = 1652 ≡ 545 (mod 667)
	426256 = 5452 ≡ 210 (mod 667)
	426512 = 4222 ≡ 662 (mod 667)
ak base 10	426256+64+16+4+2+1 (mod 667)
ak base 10	426256*42664*42616*4264*4262*4261 (mod 667)
ak base 10	210*165*110*36*52*426 ≡ 581 (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
226671680000-1	667
581-1	667
580	667-580=87
580-6*87=58	87
58	87-58=29
58-2*29=0	29
0	29

Imply

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

Integer	B-smooth number	Prime Factors	number
p-1	7	22*71	28
k	7	29*35*54*73 = 512*243*625*343	26671680000
k/(p-1)		27*35*54*72	952560000