Transcript Day21-200607Spring-Primality - Rose

DTTF/NB479: Dszquphsbqiz
Day 21
Announcements:
1.
2.
3.
4.
5.
Congrats on reaching the halfway point once again!
DES graded soon
Short “pop” quiz on Ch 3. (Thursday at earliest)
Reminder: pass in worksheet on using RSA today or
tomorrow.
Term project groups and topics due by Friday.
Questions?
This week:


Primality testing, factoring
Discrete Logs
Plus-delta
5-min
Term projects
Use Ch 10 – 19 as inspiration.



Elliptic curves?
Quantum crypto?
Security protocols?
Deliverables:


A paper demonstrating your understanding of
the topic
A 20-min in-class presentation 9th/10th week
Groups of ~3 to bound presentation time.
Pulling 479 back into cache
RSA: public-key system: n, e known




Easy to encrypt
But need factorization of n (pq) to find d to decrypt.
Factorization is a “one-way” function
Builds on lots of ch 3 number theory, like Euclid,
Fermat, and Euler.
You used Maple to send messages
You looked at some “implementation mistakes”
(for example, using small values for e)
Compositeness testing
Oops, did I say primality testing?
Today, we discuss three techniques
that can guarantee a number is
composite, and guess when one is
prime.
1. Square Root Compositeness Theorem
+
2. Fermat’s Theorem
=
3. Miller-Rabin Compositeness Test
Square Root Compositeness Theorem
Given integers n, x, and y:
If x  y , but x   y(mod n)
2
2
Then n is composite, and gcd(x-y, n) is a
non-trivial factor
Proof: live in class
Toy example showing 35 is composite
using x=2 and y=12.
Review
Fermat’s little theorem:

If n is prime and doesn’t divide a, then
a
n 1
 1(mod n)
Contrapositive:

a n1  1(mod n)
If
then n is composite
In practice,
a n1  1(mod n)

If
then n is probably prime

Rare counterexamples (15k our of first 10B ints) called pseudoprimes
Notes


Never gives factors
Compute using powermod
Prime
=1
Not 1
Most
None
Composite Rare pseudoprime
All
Miller-Rabin Compositeness Test
To test whether n is prime or composite
Given odd n>1, write n-1=2km, where k >=1.
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.
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
Examples of Miller-Rabin
Given odd n>1, write n-1=2km, where k >=1.
1. n=189
Choose a base a randomly (or just pick a=2)
2. n=561 (Fermat says prob prime)
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.
Why does it work?
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
Those composites that even get by M-R
are called strong pseudoprimes
(~20% of pseudoprimes < 10B).
Using within a primality testing scheme
n
Odd?
no
div by other small primes?
no
Fermat?
yes
Prime by Factoring/
advanced techn.?
yes
prime
Using within a primality testing scheme
n
Finding large probable primes

#primes < x =
x
 ( x) 
ln( x)
Density of primes: ~1/ln(x)
Odd?
no
div by other small primes?
For 100-digit numbers, ~1/230.
no
So ~1/115 of odd 100-digit numbers
are prime
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
Pass M-R?
yes
Prime by Factoring/
advanced techn.?
yes
prime