Great Theoretical Ideas In Computer Science Steven Rudich Lecture 8 CS 15 251 Feb 3 2005 Spring 2005 Carnegie Mellon University Modular Arithmetic and the RSA Cryptosystem p 1 p 1 n m means that m is a an integer multiple of n We say that n divides m True 5 25 2 66 7 35 False 4 5 8 2 MAX a b MIN a b a b Greatest Common Divisor GCD x y greatest k 1 s t k x and k y GCD Greatest Common Divisor What is the GCD of 12 and 18 12 22 3 16 2 32 Common factors 21 and 31 Answer 6 Least Common Multiple LCM x y smallest k 1 s t x k and y k Prop GCD x y xy LCM x y LCM x y xy GCD x y 1 GCD x y xy LCM x y LCM x y xy GCD x y x 22 3 12 y 32 5 45 GCD 12 45 3 LCM 12 45 22 32 5 180 x y 540 a mod n means the remainder when a is divided by n If ad r n 0 r n Then r a mod n and d a div n 31 equals 81 modulo 2 31 81 mod 2 31 2 81 31 mod 2 1 81 mod 2 2 31 81 GCD x y LCM x y xy MAX a b MIN a b a b Modular equivalence of integers a and b a b mod n a n b a and b are equivalent modulo n iff a mod n b mod n iff n a b n is an equivalence relation In other words Reflexive a n a Symmetric a n b b n a Transitive a n b and b n c a n c 2 a n b n a b a and b are equivalent modulo n n induces a natural partition of the integers into n classes a and b are said to be in the same residue class or congruence class exactly when a n b a n b n a b a and b are equivalent modulo n Define the residue class i to be the set of all integers that are congruent to i modulo n Residue Classes Mod 3 Equivalence mod n implies equivalence mod any divisor of n 0 6 3 0 3 6 1 5 2 1 4 7 2 4 1 2 5 8 6 6 3 0 3 6 7 5 2 1 4 7 1 4 1 2 5 8 If x n y and k n Then x k y If x n y and k n Then x k y Proof Recall x ny n x y k n and n x y Hence k x y Of course k x y x ky Example 10 6 16 10 3 16 Fundamental lemma of plus minus and times modulo n If x n y and a n b Then 1 x a n y b 2 x a n y b 3 xa n yb 3 Equivalently Fundamental lemma of plus minus and times modulo n If n x y and n a b Then 1 n x y a b 2 n x y a b 3 n xa yb When doing plus minus and time modulo n I can at any time in the calculation replace a number with a number in the same residue class modulo n Proof of 3 xa yb a x y y b a n a x y and n y b a A Unique Representation System Modulo n Please calculate in your head 329 666 mod 331 2 4 8 323 We pick exactly one representative from each residue class We do all our calculations using the representatives Unique representation system modulo 3 Unique representation system modulo 3 Finite set S 0 1 2 Finite set S 0 1 1 and defined on S and defined on S 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 4 Zn 0 1 2 n 1 a n b a b mod n a n b a b mod n The reduced system modulo n Zn 0 1 2 n 1 n and n are associative binary operators from Zn X Zn Zn When n or n Define n and n a n b a b mod n Closure x y Zn x y Zn a n b a b mod n Associativity x y z Zn x y z x y z Zn 0 1 2 n 1 a n b a b mod n a n b a b mod n The reduced system modulo 3 Z3 0 1 2 n and n are commutative associative binary operators from Zn X Zn Zn Commutativity x y Zn x y y x The reduced system modulo 2 Z2 0 1 Two binary associative operators on Z3 3 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 2 0 1 2 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 The Boolean interpretation of Z2 0 1 0 means FALSE Two binary associative operators on Z2 3 1 means TRUE 2 0 1 2 0 1 0 0 1 0 0 0 1 1 0 1 0 1 XOR AND 5 The reduced system The reduced system Z4 0 1 2 3 Z5 0 1 2 3 4 0 1 2 3 0 1 2 3 0 1 2 3 4 0 1 2 3 0 0 1 2 3 4 0 0 0 0 0 0 0 0 1 2 3 0 0 0 0 0 1 1 2 3 4 0 1 0 1 2 3 4 1 1 2 3 0 1 0 1 2 3 2 2 3 4 0 1 2 0 2 4 1 3 3 3 4 0 1 2 3 0 3 1 4 2 2 2 3 0 1 2 0 2 0 2 4 4 0 1 2 3 4 0 4 3 2 1 3 3 0 1 2 3 0 3 2 1 The reduced system The reduced system Z6 0 1 2 3 4 5 Z6 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 0 1 2 3 4 5 0 0 1 2 3 4 5 0 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 …
View Full Document
Unlocking...