`-=[]⟨⟩\;',./~!@#$%^&*()_+{}|:"<>? 𝑎𝑏𝑐𝑑𝑒𝑓𝑔ℎ𝑖𝑗𝑘𝑙𝑚𝑛𝑜𝑝𝑞𝑟𝑠𝑡𝑢𝑣𝑤𝑥𝑦𝑧 Å − × ⋅∓±∘꞊﹦∗∙ ℯ 𝔸𝔹ℂ𝔻𝔼𝔽𝔾ℍ𝕀𝕁𝕂𝕃𝕄ℕ𝕆ℙℚℝ𝕊𝕋𝕌𝕍𝕎𝕏𝕐ℤ𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻𝐼𝐽𝐾𝐿𝑀𝑁𝑂𝑃𝑄𝑅𝑆𝑇𝑈𝑉𝑊𝑋𝑌𝑍 ∼∽∾≁≂≃≄≅≆≇≈≉≌≐≠≡ ≤≥≦≧≨≩≪≫ ∈∉∊∋∌∍ ⊂⊃⊄⊅⊆⊇ 𝛼𝛽𝛾𝛿𝜀𝜁𝜂𝜃𝜄𝜅𝜆𝜇𝜈𝜉𝜊𝜋𝜌𝜎𝜏𝜐𝜑𝜒𝜓𝜔 ∀∂∃∅⦰∆∇∎∞∝∴∵ ∏∐∑⋀⋁⋂⋃ ∧∨∩∪ ∫∬∭∮∯∰∱∲∳ ∥⋮⋯⋰⋱ ‖ ′ ″ ‴ ⁄ ⁗ ʹ ʺ ‵ ‶ ‷ ﹁﹂﹃﹄︹︺︻︼ ︗ ︘ ︿﹀︽︾﹇﹈︷︸ ⏜ ⏝ ⎴ ⎵ ⏞ ⏟ ⏠ ⏡ ←↑→↓↤↦↥↧↔↕↖↗↘↙▲▼◀▶↺↻⟲⟳ ↼↽↾↿⇀⇁⇂⇃⇄⇅⇆⇇ ⇐⇑⇒⇓⇔⇌⇍⇏⇕⇖⇗⇘⇙⇙⇳⥢⥣⥤⥥⥦⥧⥨⥩⥪⥫⥬⥭⥮⥯

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	293554 = 512243625	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	26710886428388608220971522131072232768210242512
ak base 10	19050937233563325662 ≡ 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	29355473 = 512243625343	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	426256426644261642644262*4261 (mod 667)
ak base 10	2101651103652*426 ≡ 581 (mod 667)