Great Theoretical Ideas In Computer Science Steven Rudich Lecture 8 CS 15 251 Feb 5 2004 Spring 2004 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 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 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 Proof Recall x ny n x y k n and n x y Hence k x y Of course k x y x ky 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 Equivalently 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 Proof of 3 xa yb a x y y b a n a x y and n y b a Fundamental lemma of plus minus and times modulo n 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 Please calculate in your head 329 666 mod 331 2 4 8 323 A Unique Representation System Modulo n We pick exactly one representative from each residue class We do all our calculations using the 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 Closure x y2 Zn x y 2 Zn Associativity 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 Commutativity 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 reduced system modulo 2 Z2 0 1 Two binary associative operators on Z2 0 1 2 0 1 0 0 1 0 0 0 1 1 0 1 0 1 2 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 1 2 3 4 2 2 3 4 0 1 2 0 2 4 1 3 3 3 4 0 1 2 3 0 3 1 4 2 4 4 0 1 2 3 4 0 4 3 2 1 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 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 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 …
View Full Document
Unlocking...