An overview of integer factorization
49 Pages
English
Gain access to the library to view online
Learn more

An overview of integer factorization

Gain access to the library to view online
Learn more
49 Pages
English

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


Subjects

Informations

Published by
Reads 20
Language English
Document size 4 MB

Exrait

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
￿￿