An overview of integer factorization

Description

Niveau: Supérieur
An overview of integer factorization From the dark ages to the modern times jerome.milan (at) lix.polytechnique.fr March 2010

• better square detection


• fermat ?


• logb ·


• deduce sieve


• latter enhancements


• fermat's method


• pollard's rho


• square then


• polynomial time

Sujets

• Fermat's factorization method
• Pollard's rho algorithm
• Time complexity

Informations

• Publié par: chaeh
• Nombre de lectures: 20
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

An overview of integer factorization
From the dark ages to the modern times
jerome.milan (at) lix.polytechnique.fr
March 2010The Dark Ages
Fermat’s method
The p−1 method
The p+1 method
Pollard’s Rho
SQUFOF
2Fermat’s method
Fermat − Around 1643, in a letter to Mersenne•
2 2Write N = p p as N = x −y =(x +y)(x−y)• 1 2
√
• If N is not a square then x≥￿ N￿+1
Fermat’s method (simplest form)
integer N to factorInput:
a factor p of NOutput:
√
m←￿ N￿+11.
2. while (true)
2m −N if is a square then￿
2m+ m −N return
else
m←m+1
3Fermat’s method
Basic enhancements•
• Replace squarings by additions
2 2(m+1) −N =m −N +(2m+1)
• Better square detection test (e.g. a square ≡ 0, 1, 4 or 9)16
• Deduce sieve on x
￿ ￿√
2 √( N−p )1Runs in with best case in • O O( N)
2p1
Latter enhancements•
1/3• R. Lehman (1974) in O(N )
1/4• J. McKee (1999) heuristically in O(N )
1/3• R. Erra/C. Grenier (2009) in polynomial time if |p −p |<N1 2
4
The p−1 method
Published by Pollard in 1974 (previously known by D.N & D.H Lehmer)•
Based on Fermat’s little theorem•
p−1• If then gcd(x,p)=1 x =1modp
r￿
eiLet and y= p• B ∈Ni
i=0
• y is B-smooth ≡∀i ∈ [0,r],p ≤ Bi
ei• y is B-power smooth ≡∀i ∈ [0,r],p ≤ Bi
A special-purpose algorithm•
• Succeeds if a is B-power smooth, for some bound Bp −1i
2• Runs in O(B · logB · log N)
5The p−1 method
Pollard’s p−1 (first stage)
integer N to factorInput:
bound B1
a factor p of N or failureOutput:
x1. Choose coprime with N
B !1i = 1..B2. for do // Compute x mod N1
i x←x modN
p← gcd(x− 1,N)3.
p=1 p=N4. if ( ) and ( )
p return
else
return failure
6
￿￿The p−1 method
First stage example•
• N = 421×523
• B=7 x=3
B!• gcd(x −1,N) = 421
2• (420 is 7-power smooth)420 = 2 ×3×5×7
Optional second stage •
• If not -power smooth, first stage will failp−1 B1
• Second stage allows one factor of to be in p−1 [B ,B ]1 2
B! q• Compute for all primes q in gcd((x ) − 1,N) [B ,B ]1 2
• Standard continuation, FFT continuation, etc.
7The p−1 method
Pollard’s p−1 (second stage – standard continuation)
integer N to factorInput:
B !1y = x mod N from first stage
Bbound 2
a factor p of N or failureOutput:
1. [Precomputations]
{q ,q ...q } [B ,B ] Let be the primes in 1 2 k 1 2
q −qi+1 i y ← y mo d N for all i ∈ [1,k]i
2. [Gcds]
q1 z← y mod N1
j = 1..k for do
p← gcd(z− 1,N)
p=1 p=N if ( ) and ( ) return p
z← z×y mod N i
return failure
8
￿￿The p+1 method
H.C. Williams – 1982•
• Similar to p−1 but succeeds if p+1 is -power smoothB1
k￿
eiSuppose • p= q −1i
i=1
Lucas sequence • V (P,Q)k
22• Let , roots of and∆= P −4Qβ x −Px+Qα
k k• V (P,Q)≡α +βk
• Fact 1. If and then(gcd(∆,N) = 1) (( /p)=−1)
p divides V (P,Q)− 2B !1
• Fact 2. There is an efficient algorithm to computeV (P,1)k
using recursive formulae
9
∆The p+1 method
Williams’ p+1 (first stage)
integer N to factorInput:
bound B1
a factor p of N or failureOutput:
2P gcd(P −4,N)=11. Choose so that 0 0
P ←V (P ,1)2. // There’s an efficient algo for thatm B ! 01
// using recursion formulae
p← gcd(N,P − 2)3. m
p=1 p=N4. if ( ) and ( )
p return
else
return failure
10
￿￿