Transcript Factoring Methods

A Survey on Factoring Large Numbers
～ 巨大数の因数分解に関する調査 ～
Kanada Lab. M1
47-56338 Yoshida Hitoshi
Introduction

Factoring a number means representing it as the
product of smaller numbers.
 It is difficult to factor a large number.
 Some cryptosystems are based on the difficulty of
the factoring integer problem.
 It measures the security of the cryptosystems to
factor large numbers in short time.
page2
Contents

Introduction
 Factoring Methods
 Calculation Records
 Cryptosystem Security
page3
Contents

Introduction
 Factoring Methods
 Calculation Records
 Cryptosystem Security
page4
Factoring Methods
Trial Division
Euler’s Method
Square Forms
Factorization
Pollard’s
(p-1)-Method
Pollard’s
ρ Method
Elliptic Curve
Method
Difference of
Squares
Quadratic Sieve
Multiple Polynomial
Quadratic Sieve
Pollard’s
(p+1)-Method
Continued Fraction
Method
General Number
Field Sieve
page5
Trial Division

Algorithm


Merit


Check if “n mod i = 0” for i = 2,3,4,…
It can factor a number into prime numbers.
Demerit

‘i’ may be nearly
same size.
when n is the product of 2 primes of
page6
Trial Division

Improvement


Don’t use multiples of 2,3,5 for “i”.
Use only prime numbers for “i”.

Cannot reduce operational costs.
 This method can use at most 1030.
π(1015)=29,844,570,422,669 ≒ 30T
If one trial division can do in 50 clock
π(1015)×50[clock]÷3G[Hz] = 500K [sec] = 5.8[day]
page7
Difference of Squares

Algorithm



Demerit


May not factor a number into prime numbers.
Merit


Find x and y which implement x2-y2=n
Factor n with x2-y2=(x+y)(x-y)
Factor a large composite number into small numbers
Operational cost

O(y)
page8
Difference of Squares

Improvement

How about using “x2-y2≡0 (mod n)” ?




602-52≡0 (mod 143) ⇒ 65・55≡0
65 or 55 must have prime factor(s) of 143.
GCD(65,143)=13, GCD(55,143)=11
How to find such x, y that implement “x2–y2≡0 (mod n)”?


Find many (ai, bi) pairs that implement ai≡bi (mod n)
Make a combination that implements Πai=x2, Πbi=y2
14･67≡ 3 mod 187
31･67≡20 mod 187
14･31≡60 mod 187
(14･31･67）2≡602 mod 187
page9
Difference of Squares

How can we find those numbers efficiently?

Quadratic Sieve (QS)
Cf. Multiple Polynomial Quadratic Sieve (MPQS)

General Number Field Sieve (GNFS)
page10
Quadratic Sieve

Algorithm
1. for
i = [√n]±1,2,… , factor i2-n into prime numbers
(i2≡i2-n=p1p2p3…)
2. search
a combination that make every exponent number
even
3. x=Πi and y=√(Πprimes) implements x2-y2≡0
page11
Quadratic Sieve

Example
n=3937, √n=62.7
i=63 632≡632-n= 32=25
i=64 642≡642-n=159=3･53
i=65 652≡652-n=288=25･32
i=66 662≡662-n=419=419
i=67 672≡672-n=552=23･3･23
page12
Quadratic Sieve

Example
n=3937, √n=62.7
i=63 632≡632-n= 32=25
i=64 642≡642-n=159=3･53
i=65 652≡652-n=288=25･32
i=66 662≡662-n=419=419
i=67 672≡672-n=552=23･3･23
（63･65）2≡210･32=（25･3）2
∴GCD（63･65-25･3, n）=31
page13
Quadratic Sieve

Operational cost
 O(exp((9/8)(logn)1/2(loglogn)1/2))
 Now,
QS is one of the fastest method to factor 30~60
decimal digit numbers.

Make faster
 Large
prime factors appear rarely
 Smaller number has smaller primes.
 How can we get small numbers efficiently?
page14
Quadratic Sieve

Example
n=3937, √n=62.7
i=63 632≡632-n= 32=25
i=64 642≡642-n=159=3･53
i=65 652≡652-n=288=25･32
i=66 662≡662-n=419=419
i=67 672≡672-n=552=23･3･23
（63･65）2≡210･32=（25･3）2
∴GCD（63･65-25･3, n）=31
page15
Quadratic Sieve

Operational cost
 O(exp((9/8)(logn)1/2(loglogn)1/2))
 Now,
QS is one of the fastest method to factor 30~60
decimal digit numbers.

Make faster
 Large
prime factors appear rarely
 Smaller number has smaller primes.
 How can we get small numbers efficiently?
page16
Quadratic Sieve

Make faster
(Multiple Polynomial QS) ; i2-n ⇒ (ai+b)2-n
 MPQS is the fastest to factor 60～120 digit numbers
 MPQS
QS
MPQS
page17
General Number Field Sieve (GNFS)
Original “Number Field Sieve” was for special
numbers ⇒ Special Number Field Sieve (SNFS)
 Algorithm






Polynomial definition step
Sieving step
Matrix solving step
Making square root step
Operational cost
O(exp((64/9)1/3(logn)1/3(loglogn)2/3))
[Cf. QS→O(exp((9/8)(logn)1/2(loglogn)1/2)) ]
page18
Contents

Introduction
 Factoring Methods
 Calculation Records
 Cryptosystem Security
page19
Calculation Records

Factoring records
page20
Calculation Records

Factoring records
1. 200 decimal digits number (RSA200)



Bonn university
Algorithm : GNFS
Sieving step



Matrix step


Various machines and time
Dec 2003 ～ Oct 2004 (≒ 2.2GHz Opteron × 55 years)
80 × 2.2GHz Opteron (Cluster) × 3 months (Dec 2004 ～)
May 2005 factoring completed
page21
Calculation Records

Factoring records
2. 176 decimal digits number (A factor of 11281+1)



Yuji Kida (Rikkyo university) and NTT laboratory
Algorithm : GNFS
Sieving step



Matrix step


Various machines (≒ 3.2GHz Pentium4 × 9.7 years)
16 Mar 2005 ～ 12 Apr 2005 (27days)
32 × 3.2GHz Pentium4 (Cluster) × 2.5 days
Apr 2005 factoring completed
page22
Contents

Introduction
 Factoring Methods
 Calculation Records
 Cryptosystem Security
page23
Cryptosystem Security

RSA use 1024 bit length key



How long does it take to factor 1024bit number?
5.8×105～1.4×106 years(?) [Kida, 2003]
RSA Factoring Challenge




8 composite numbers (576～2048bit) to factor
576 bit number was factored (Dec 3, 2003)
200 decimal digit number (old problem) was factored
640 bit number is 193 decimal digit
page24
Cryptosystem Security

TWIRL




Make sieving step of GNFS in device
It will take 1 year to sieve 1024bit length number
Not in practice yet
Quantum Computing


Shor’s algorithm may run very fast
Quantum computer is not in practice
page25
That’s All
Thank you
page26