Transcript Day22-200607Spring-Factoring - Rose

DTTF/NB479: Dszquphsbqiz
Day 22
Announcements:
1.
2.
3.
4.
Pass in worksheet on using RSA now.
DES graded soon
Short “pop” quiz on Ch 3 (Thursday at earliest)
Term project groups and topics due by Friday
1. Can use discussion forum to find teammates
5.
HW6 posted, due date bumped back to next week (and a few
questions added), but doing what’s there now might help your
quiz prep.
Questions?
This week:


Primality testing, factoring
Discrete Logs
Miller-Rabin
Given odd n>1, write n-1=2km, where k >=1.
So:
Choose a base a randomly (or just pick a=2)
Let b0=am(mod n)
If b0=+/-1, stop. n is probably prime by
Fermat
For i = 1..k-1
Compute bi=bi-12.
If bi=1(mod n), stop. n is composite by
SRCT, and
gcd(bi-1-1,n) is a factor.
If bi=-1(mod n), stop. n is probably
prime by Fermat.
If bk=1 (mod n), stop. n is composite by
SRCT
Else n is composite by Fermat.
k
   
a n 1   a
 b
...
2
m
2
0
b1
bk
Big picture: Fermat on steroids
By doing a little extra work (finding k
to change the order of the powermod),
we can call some pseudoprimes
composite and find some of their factors
Using within a primality testing scheme
n
(From Day 11)
Odd?
no
div by other small primes?
no
Fermat?
yes
Prime by Factoring/
advanced techn.?
yes
prime
Using within a primality testing scheme
Finding large probable primes

x
#primes < x = ( x) 
ln( x)
Density of primes: ~1/ln(x)
For 100-digit numbers, ~1/230.
So ~1/115 of odd 100-digit numbers
are prime
n
Odd?
no
div by other small primes?
no
Pass M-R?
Can start with a random large odd
number and iterate, applying M-R
to remove composites. We’ll soon
find one that is a likely prime.
Maple’s nextprime() appears to do
this, but also runs the Lucas test:
http://www.mathpages.com/home/k
math473.htm
Alternatively, could repeat M-R to get
high probability prime
yes
Prime by Factoring/
advanced techn.?
yes
prime
Factoring
If you are trying to factor n=pq and know
that p~q, use Fermat factoring:


Compute n + 12, n + 22, n + 32, until you reach
a perfect square, say r2 = n + k2
Then n = r2 - k2 = (r+k)(r-k)
The moral of the story?

Choose p and q such that _____
Example
Factor n = 3837523
Concepts we will learn also apply to factoring
really big numbers. They are the basis of the
best current methods
All you have to do to win $30,000 is factor a 212
digit number.
This is the RSA Challenge:
http://www.rsa.com/rsalabs/node.asp?id=2093#RSA704
Quadratic Sieve (1)
Factor n = 3837523
Want x,y: x 2  y 2 , but x   y(mod n) gcd(x-y, n) is a factor
Step 1: Pick a factor base, just a set of small factors.


In our examples, we’ll use those < 20.
There are 8: 2, 3, 5, 7, 11, 13, 17, 19
Quadratic Sieve (2a)
Factor n = 3837523
2
2
Want x,y: x  y , but x   y(mod n)  gcd(x-y, n) is a factor
Step 2: We want squares that are congruent to products of
factors in the factor base.
Our hope: Reasonably small numbers are more likely to be
products of factors in the factor base.
Want x 2  kn  e , so approximate with x  kn  e
1.
2.
3.
Then x 2  kn  2e kn  e 2 which is small as long as k isn’t too big
Loop over small e, lots of k.
A newer technique, the number field sieve, is somewhat faster
Quadratic Sieve (2b)
Factor n = 3837523
Want x,y: x 2  y 2 , but x   y(mod n) gcd(x-y, n) is a factor
Step 2: We want squares that are congruent to products of
factors in the factor base.
Our hope: Reasonably small numbers are more likely to be
products of factors in the factor base.
Want x 2  kn  e , so approximate with x  kn  e
Examples:
8077  17n  1; 8077 2  38  2 19(mod n)
9398  23n  4; 93982  59375  55 19(mod n)
Quadratic Sieve (3)
Factor n = 3837523
Want x,y: x 2  y 2 , but x   y(mod n) gcd(x-y, n) is a factor
Step 3: Want two non-congruent perfect squares
Example: (8077  9398)2  2 19  55 19  2  5  (52 19)2
This is close, but all factors need to be paired
Recall:
8077 2  38  2 19(mod n)
93982  59375  55 19(mod n)
Quadratic Sieve (3b)
Factor n = 3837523
Want x,y: x 2  y 2 , but x   y(mod n) gcd(x-y, n) is a factor
Step 3: Want two non-congruent perfect squares
Example: (8077  9398)  2 19  55 19  2  5  (52 19)2
This is close, but all factors need to be paired
Generate lots of # and experiment until all factors are paired.
1964 2  32 133 (mod n)
14262  5  7 13(mod n)
2
2

(1954 14262) 2  3  5  7 13
1147907  17745
2
So what?
2
2

gcd(1147907-17745, n)=1093
2 2
Other factor = n/1093=3511
Quadratic Sieve (3b)
Factor n = 3837523
Want x,y: x 2  y 2 , but x   y(mod n) gcd(x-y, n) is a factor
Step 4: Want to get 2 non-congruent perfect squares
Example: (8077  9398)  2 19  55 19  2  5  (52 19)2
This is close, but all factors need to be paired
Generate lots of # and experiment until all factors are paired.
To automate this search:
Can write each example are a row in a matrix, where
each column is a prime in number base
Then search for dependencies among rows mod 2.
May need extra rows, since sometimes we get x=+/-y.
My code
Factor n = 3837523
To automate this search:
Each row in the matrix is
a square
Each column is a prime
in the number base
Search for
dependencies among
rows mod 2.
For last one (green)
(9398  8077  3397) 
 (23  53 13 19)
So we can’t use the square
root compositeness
theorem
Sum:
Sum:
Sum:
0 2 2 2 0 4 0
8 4 6 0 2 4 0
6 0 6 0 0 2 0
0
2
2