Report

DTTF/NB479: Dszquphsbqiz Announcements: Homework 2 due now Computer quiz Thursday on chapter 2 Questions? Today: Finish congruences Fermat’s little theorem Euler’s theorem Important for RSA public key crypto – pay careful attention! Day 9 The Chinese Remainder Theorem establishes an equivalence A single congruence mod a composite number is equivalent to a system of congruences mod its factors Two-factor form Given gcd(m,n)=1. For integers a and b, there exists exactly 1 solution (mod mn) to the system: x a(modm) x b(modn) CRT Equivalences let us use systems of congruences to solve problems Solve the system: How many solutions? Find them. x 3(mod7) x 5(mod15) x 2 1(mod35) The Chinese Remainder Theorem also applies generally to n factors Let m1, m2,… mk be integers such that gcd(mi, mj)=1 when i ≠ j. For integers a1, … ak, there exists exactly 1 solution (mod m1m2…mk) to the system: x a1 (modm1 ) x a2 (modm2 ) ... x ak (modmk ) Modular Exponentiation is extremely efficient since the partial results are always small Compute the last digit of 32000 Compute 32000 (mod 19) Idea: Get the powers of 3 by repeatedly squaring 3, BUT taking mod at each step. Q Modular Exponentiation Technique and Example (All congruences are mod 19) Compute (mod 19) 32000 32 9 34 9 2 81 5 38 52 25 6 Technique: 316 6 2 36 17(or 2) Repeatedly square 3, but take mod at each step. 332 172 289 4 Then multiply the terms you need to get the desired power. 3256 5 Book’s powermod() 364 4 2 16 3128 162 256 9 3512 6 31024 17 32000 (31024 )(3512 )(3256 )(3128 )(364 )(316 ) 32000 (17)(6)(5)(9)(16)(17) 32000 (1248480) 32000 9(mod19) Modular Exponentiation Example 32000 Compute (mod 152) 32 9 34 9 2 8 1 38 8 12 6 5 6 1 2 5 316 2 52 6 2 5 1 7 332 1 72 2 8 9 1 3 7 364 1 3 72 1 8 7 6 9 7 3 3128 9 3256 8 1 3512 2 5 31024 1 7 32000 (31024 )(3512 )(3256 )(3128 )(364 )(316 ) 32000 (17)(25)(81)(9)(73)(17) 32000 (384492875 ) 32000 9(mod152) Fermat’s Little Theorem: If p is prime and gcd(a,p)=1, then a(p-1)≡1(mod p) 1-2 Fermat’s Little Theorem: If p is prime and gcd(a,p)=1, then a(p-1)≡1(mod p) S= 1 2 3 4 5 6 Examples: 22=1(mod 3) 64 =1(mod ???) (32000)(mod 19) f(1)=2 f(2)=4 f(3)=6 f(4)=1 f(5)=3 f(6)=5 Example: a=2, p=7 1-2 The converse when a=2 usually holds Fermat: p 1 a 1(mod p) If p is prime and doesn’t divide a, Converse: If a p 1 1(mod p) , then p is prime and doesn’t divide a. This is almost always true when a = 2. Rare counterexamples: n = 561 =3*11*17, but 560 2 1(mod561) n = 1729 = 7*13*19 Can do first one by hand if use Fermat and combine results with Chinese Remainder Theorem Primality testing schemes typically use the contrapositive of Fermat n Even? no div by other small primes? no Prime by Factoring/ advanced techn.? yes prime 3 Primality testing schemes typically use the contrapositive of Fermat n Even? 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 nn11 ? ? n ) n1) 22 (mod 1(mod yes Prime by Factoring/ advanced techn.? yes prime Euler’s Theorem is like Fermat’s, but for composite moduli If gcd(a,n)=1, then f ( n) a So what’s f(n)? 1(modn) 4 f(n) is the number of integers a, such that 1 ≤ a ≤ n and gcd(a,n) = 1. Examples: 14 1. f(10) = 4. 2. When p is prime, f(p) = ____ 3. When n =pq (product of 2 primes), f(n) = ____ 5 The general formula for f(n) p are distinct primes 6 p 1 f (n) n p p|n Example: f(12)4 [Intuition from Bill Waite, RHIT 2007] 7-10 Euler’s Theorem can also lead to computations that are more efficient than modular exponentiation f ( n) a 1(modn) as long as gcd(a,n) = 1 Basic Principle: when working mod n, view the exponents mod f(n). Examples: 1. 2. 3. 4. Find last 3 digits of 7803 Find 32007 (mod 12) Find 26004 (mod 99) Find 26004 (mod 101)