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

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.

Pollard's p-1 Algorithm

For a composite integer, n, with a prime factor p, if p-1 can be expressed in terms of a product of primes and k is a multiple of p-1. By selecting an integer, a, which is greater than 1 and is coprime to n, then

 

Imply

 

Since a is coprime to n, a is coprime to p also. Imply

 

From Fermat's little theorem, if p does not divide a, then

Similarly, If k is a multiple of p-1, then

Imply p is a non-trivial divisor of ap-1-1 or ak-1 .

  or

Since p is also a prime factor of n, p divides the greatest common divisor of  ap-1-1 or ak-1,  and n.

  or

Therefore, if the greatest common divisor of  ak-1,  and n is greater than 1, the greatest common divisor is a factor of n also.

Pollard's p-1 Method

Although the Pollard's p-1 algorithm cannot be used to determine the prime factor p directly, the Pollard's p-1 method is an efficient prime factor finding method for composite integers with specific types of prime factors by choosing and testing some integers systematically.

Smooth Number Method

Smooth Number

One of the number choosing method for integer k is the making use of the concept of smooth number and the specific type of prime factor, i.e. p-1 is the product of primes.

Let x and B be integers. x is said to be B-smooth if all the prime divisors of n are less than or equal to B.

Example of Smooth Number

B	B-smooth numbers	Prime Factors
2,3,5,7,11,...	1	20,30,50,70,110,...
2,3,5,7,11,...	2	21,
3,5,7,11,...	3	31,
2,3,5,7,11,...	4	22,
5,7,11,...	5	51,
3,5,7,11,...	6	21,31,
7,11,...	7	71,
2,3,5,7,11,...	8	23,
3,5,7,11,...	9	32,
5,7,11,...	10	21,51,
11,...	11	111,
3,5,7,11,...	12	22,31,
7,11,...	14	21,71,
5,7,11,...	15	31,51,
2,3,5,7,11,...	16	24,
3,5,7,11,...	18	21,32,
3,5,7,11,...	24	23,31,
2,3,5,7,11,...	32	25,
2,3,5,7,11,...	64	26,
11,...	77	71,111,
5,7,11,...	120	23,31,51,
5,7,11,...	360	23,32,51,
5,7,11,...	1800	23,32,52,

Although B is usually a prime number, B can be a composite number providing that B is greater than or equal to the largest prime factor of x.  The key information from a B-smooth number is the prime factor of a number. However, there is no information on the power or index of the prime factor. The lowest B-smooth of a number is the greatest prime factor of the number.

Pollard's P-1 Methed by Smooth Number

Since p-1 divides k, by assuming p-1 is B-smooth, if k is also B-smooth then the choosen integer k should be sufficienly large to ensure p-1 divides k. Therefore k is the product of all  prime factors with powers less than and equal to B and the index or power ei  for each prime factor pi less than and equal to B of k should be just less than and equal to n. Imply

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

For example: n=203=p*q=7*29; let B=5 imply

Integer	B-smooth number	Prime Factors	number
k	5	27*34*53 = 128*81*125	1296000

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

Fermat's Little Theorem

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

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=1296000; n=203
ak base 10	21296000
ai base 10	21  = 21 ≡ 2 (mod 203)
	22 = 22 ≡ 4 (mod 203)
	24 = 42 ≡ 16 (mod 203)
	28 = 162 ≡ 53 (mod 203)
	216 = 532 ≡ 170 (mod 203)
	232 = 1702 ≡ 74 (mod 203)
	264 = 742 ≡ 198 (mod 203)
	2128 = 1982 ≡ 25 (mod 203)
	2256 = 252 ≡ 16 (mod 203)
	2512 = 162 ≡ 53 (mod 203)
	21024 = 532 ≡ 170 (mod 203)
	22048 = 1702 ≡ 74 (mod 203)
	24096 = 742 ≡ 198 (mod 203)
	28192 = 1982 ≡ 25 (mod 203)
	216384 = 252 ≡ 16 (mod 203)
	232768 = 162 ≡ 53 (mod 203)
	265536 = 532 ≡ 170 (mod 203)
	2131072 = 1702 ≡ 74 (mod 203)
	2262144 = 742 ≡ 198 (mod 203)
	2524288 = 1982 ≡ 25 (mod 203)
	21048576 = 252 ≡ 16 (mod 203)
ak base 10	21048576+131072+65536+32768+16384+1024+512+128
ak base 10	21048576*2131072*265536*232768*216384*21024*2512*2128
ak base 10	16*74*170*53*16*170*53*25 ≡ 197 (mod 203)

Using binary squarings modulo

base	number; a=2; k=1296000; n=203
k base 10	1296000
k base 2	(100111100011010000000)2
k base 10	220+217+216+215+214+210+29+27
ak base 10	21296000
ak base 10	2^220+2^217+2^216+2^215+2^214+2^210+2^29+2^27
ak base 2	10100111100011010000000
ai base 10; a=2	0:(1*(a^0))2 = a0 ≡ 1 (mod 203)
	1:(1*(a^1))2 = a2 ≡ 4 (mod 203)
	0:(a2*(a^0))2 = a4 ≡ 16 (mod 203)
	0:(a4*(a^0))2 = a8 ≡ 53 (mod 203)
	1:(a8*(a^1))2 = a18 ≡ 71 (mod 203)
	1:(a18*(a^1))2 = a38 ≡ 67 (mod 203)
	1:(a38*(a^1))2 = a78 ≡ 92 (mod 203)
	1:(a78*(a^1))2 = a158 ≡ 158 (mod 203)
	0:(a158*(a^0))2 = a316 ≡ 198 (mod 203)
	0:(a316*(a^0))2 = a632 ≡ 25 (mod 203)
	0:(a632*(a^0))2 = a1264 ≡ 16 (mod 203)
	1:(a1264*(a^1))2 = a2530 ≡ 9 (mod 203)
	1:(a2530*(a^1))2 = a5062 ≡ 121 (mod 203)
	0:(a5062*(a^0))2 = a10124 ≡ 25 (mod 203)
	1:(a10124*(a^1))2 = a20250 ≡ 64 (mod 203)
	0:(a20250*(a^0))2 = a40500 ≡ 36 (mod 203)
	0:(a40500*(a^0))2 = a81000 ≡ 78 (mod 203)
	0:(a81000*(a^0))2 = a162000 ≡ 197 (mod 203)
	0:(a162000*(a^0))2 = a324000 ≡ 36 (mod 203)
	0:(a324000*(a^0))2 = a648000 ≡ 78 (mod 203)
	0:(a648000*(a^0))2 = a1296000 ≡ 197 (mod 203)
ak base 10	21296000 ≡ 197 (mod 203)

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
21296000-1	203
197-1	203
196	203
196	203-196
196	7
196-7*28	7
0	7

Imply

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

Integer	B-smooth number	Prime Factors	number
p-1	3, 5	21*31	6
k	5	27*34*53 = 128*81*125	1296000
k/(p-1)		26*33*53	216000

Since the greatest prime factor of p-1 is 3-smooth also. And therefore the prime factor 7 can also be found by using B=3

Integer	B-smooth number	Prime Factors	number
p-1	3	21*31	6
k	3	27*34 = 128*81	10368
k/(p-1)		26*33	1728

let a=2, by Fermat's little theorem, imply p divides  210368-1 ≡ 168 (mod 203)

The greatest common divisor of n and ak-1 is gcd(168,203)= 7

And 7 is the prime divisor of n as before.