 output.to from Sideway
Number Theory

Factorization

Pollard's p-1 Method

Draft for Information Only

# Content

``` Pollard's p-1 Method   Pollard's p-1 Algorithm   Pollard's p-1 Method    Smooth Number Method    Smooth Number     Example of Smooth Number    Pollard's P-1 Methed by Smooth Number     Pollard's P-1 Methed by Smooth Number Example 1```

# 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.

ID: 120500004 Last Updated: 2012/5/15 Revision: 1 Home (5)

Management

HBR (3)

Information

Recreation

Hobbies (7)

Culture

Chinese (1097)

English (336)

Reference (66)

Computer

Hardware (149)

Software

Application (187)

Digitization (24)

Numeric (19)

Programming

Web (618) CSS (SC)

ASP.NET (SC)

HTML

Knowledge Base

Common Color (SC)

Html 401 Special (SC)

OS (388) MS Windows

Windows10 (SC)

.NET Framework (SC)

DeskTop (7)

Knowledge

Mathematics

Formulas (8)

Number Theory (206)

Algebra (20)

Trigonometry (18)

Geometry (18)

Calculus (67)

Complex Analysis (21)

Engineering

Tables (8)

Mechanical

Mechanics (1)

Rigid Bodies

Statics (92)

Dynamics (37)

Fluid (5)

Control

Acoustics (19)

Biology (1)

Geography (1)