Transcript Day11-200607Spring-FermatEuler - Rose

DTTF/NB479: Dszquphsbqiz
Day 11
Announcements:



HW3 updated. Due next Thursday
Written quiz tomorrow on chapters 1-2 (next slide)
Computer quiz next week on breaking codes from
chapter 2
Questions?
Today:



Finish Modular Exponents example
Fermat’s little theorem
Euler’s theorem
Tomorrow’s Quiz
Rules:



Written problems
Closed book and computer
You may bring a note sheet: 1 handwritten sheet of
8.5 x 11 paper, one side only.
Content:




Concepts of the algorithms we discussed, how they
work, how you can break them using various attacks
Inverses of integers and matrices (mod n)
Working out some examples by hand, like 5-1 mod (7)
Anything else from ch 1-2, but nothing that will require
a computer.
Modular Exponentiation
(All congruences are mod 152)
Compute 3^2000
(mod 152)
Technique:

Repeatedly square
3, but take mod at
each step.
32  9
34  9 2  81
38  812  6561  25
316  252  625  17
332  17 2  289  137
364  137 2  18769  73

Then multiply the
terms you need to
get the desired
power.
Matlab’s
powermod()
3128  9
3256  81
3512  25
1024
3
 17
32000  (31024 )(3512 )(3256 )(3128 )(364 )(316 )
32000  (17)( 25)(81)(9)(73)(17)
32000  (384492875)
32000  9
Is there an easier way to compute 32000
(mod 152)?
Consider first a similar example, 32000
(mod 17) (chosen so p is prime).
Today’s theorems will be really important
when dealing with RSA encryption – pay
careful attention!
Fermat’s Little Theorem
a
p 1
 1(mod p)
if p is prime and doesn’t divide a.
Examples: 22(mod 3), 44 (mod ???)
So what’s (32002)(mod 17)?
Converse when a=2
p 1
If p is prime and doesn’t divide a, a  1(mod p)
Converse:
If a p 1  1(mod p) , p is prime and doesn’t divide a.
This is almost always true when a = 2. Rare
counterexamples:



n = 561 =3*11*17, but
2560  1(mod 561)
n = 1729 = 7*13*19
Can do first one by hand if use Fermat and combine results with
Chinese Remainder Theorem
Using Fermat within a primality
n
testing scheme
Even?
no
div by other small primes?
no
Prime by Factoring/
advanced techn.?
yes
prime
Using Fermat within a primality
testing scheme (ch 6) n
Odd?
no
Use Fermat as a filter since it’s
faster than factoring (if
calculated using the powermod
method).
Fermat: p prime
Contrapositive?
2p-1
= 1 (mod p)
Why can’t we just compute 2n-1(mod n)
Using Fermat if it’s so much faster?
div by other small primes?
no
?
n 1
2 (mod n) 1
yes
Prime by Factoring/
advanced techn.?
yes
prime
Euler’s Theorem
af ( n )  1(mod n)
Analog to Fermat for composite modulus
What’s f(n)?
f(n) = the number of integers a, s.t., 1<= a <= n
where gcd(a,n) = 1.
Ex: f(10) = 4.
What’s f(p) for p prime?
What about f(n), where n =pq (a product of 2 primes)
Euler’s f-function
 p 1 

f (n)  n 
p 
p| n 
Notes: The p are taken from the set of distinct primes
that divide n
Eg, for n=60, use p = 2 (only once), 3, and 5.

Answer: f(60)16
When we compute the ratios, what about mutual
exclusion? Consider the intuition:


Crossing out every number divisible by 3 leaves 2/3 of them.
If I crossed out the even numbers first, then
crossing out every odd number divisible by 3 still leaves 2/3 of
those left!
*Thanks to Bill Waite for this good insight
Back to Euler’s Theorem
a
f (n)
 1(mod n)
As long as gcd(a,n,) = 1
Examples:



Find last 3 digits of 7803
Find 32007 (mod 12)
Find 243210 (mod 101)
Basic Principle: when working mod n, view the exponents mod f(n).