Sideway
output.to from Sideway
Factorization


Pollard's p-1 Method


1


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

image 

Imply

image 

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

image 

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

image

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

image

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

image  or image

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

image  or image

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.

image
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

image
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

image
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 

image

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

image

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.


©sideway

ID: 120500004 Last Updated: 2012/5/15 Revision: 1

IMAGE

Home (1)

Business

Management

HBR (3)

Information

Recreation

Hobbies (7)

Culture

Chinese (1097)

English (334)

Reference (65)new

Computer

Hardware (148)

Software

Application (187)

Digitization (24)

Numeric (19)

Programming

Web (540)new

CSS (SC)

HTML

Knowledge Base

Common Color (SC)

Html Entity (Unicode) (SC)

Html 401 Special (SC)

OS (367)

MS Windows

Windows10 (SC)

DeskTop (5)

Knowledge

Mathematics

Formulas (8)

Number Theory (206)new

Algebra (17)

Trigonometry (18)

Geometry (18)

Calculus (67)

Complex Analysis (5)new

Engineering

Tables (8)

Mechanical

Mechanics (1)

Rigid Bodies

Statics & Dynamics (129)

Fluid (5)

Fluid Kinematics (5)

Control

Process Control (1)

Acoustics (19)

FiniteElement (2)

Biology (1)

Geography (1)

Latest Updated Links

Copyright © 2000-2019 Sideway . All rights reserved Disclaimers last modified on 10 Feb 2019