Great Theoretical Ideas In Computer Science John Lafferty Lecture 9 CS 15 251 Sept 27 2005 Carnegie Mellon University Modular Arithmetic and the RSA Cryptosystem p 1 p Fall 2005 1 MAX a b MIN a b a b n m means that m is an integer multiple of n We say that n divides m True 5 25 2 66 7 35 False 4 5 8 2 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 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 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 GCD x y LCM x y xy MAX a b MIN a b a b a mod n means the remainder when a is divided by n If dn r a 0 r n Then r a mod n and d a div n 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 31 equals 81 modulo 2 31 81 mod 2 31 2 81 31 mod 2 1 81 mod 2 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 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 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 Equivalence mod n implies equivalence mod any divisor of n If x n y and k n Then x k y Example 10 6 16 10 3 16 If x n y and k n Then x k y 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 Proof of 3 xa yb mod n Fundamental lemma of plus minus and times modulo n When doing plus minus and times modulo n I can at any time in the calculation replace a number with a number in the same residue class modulo n Please calculate 249 504 mod 251 2 2 4 247 A Unique Representation System Modulo n We pick exactly one representative from each residue class We do all our calculations using these representatives Unique representation system modulo 3 Finite set S 0 1 2 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 Unique representation system modulo 3 Finite set S 0 1 1 and defined on S 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 The reduced system modulo n Zn 0 1 2 n 1 Define n and n a n b a b mod n a n b a b mod n Zn 0 1 2 n 1 a n b a b mod n a n b a b mod n n and n are associative binary operators from Zn X Zn Zn When n or n Closed x y2 Zn x y 2 Zn Associative x y z2 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 n and n are commutative associative binary operators from Zn X Zn Zn Commutative x y2 Zn x y y x The reduced system modulo 3 Z3 0 1 2 Two binary associative operators on 3 0 1 0 1 2 3 0 0 0 0 0 1 2 1 0 1 1 1 2 0 2 0 2 2 2 0 1 Z3 2 0 2 1 The Boolean interpretation of Z2 0 1 0 means FALSE 2 0 1 XOR 1 means TRUE 2 0 1 AND 0 0 1 0 0 0 1 1 0 1 0 1 The reduced system Z4 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 The reduced system Z5 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 0 1 2 3 4 0 0 0 0 0 0 1 1 2 3 4 0 1 0 2 2 3 4 0 1 2 0 3 3 4 0 1 2 3 0 4 4 0 1 2 3 4 0 The reduced system Z6 0 1 2 3 4 5 0 1 2 3 4 5 0 0 1 2 3 4 5 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 2 0 3 0 4 0 5 0 The reduced system Z6 0 1 2 3 4 5 0 1 2 3 4 5 0 0 1 2 3 4 5 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 An operator has the permutation property if each row and each column has a permutation of the elements For every n n on Zn has the permutation property 0 1 2 3 4 5 0 0 1 2 3 4 5 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 An operator has the permutation property if each row and each column has a permutation of the elements …
View Full Document
Unlocking...