Intro to Crypto and ModSupplementary NotesPrepared by Raymond WongPresentedbyRaymond Wong
Intro to Crypto and Mod Supplementary Notes Prepared by Raymond Wong Presented by Raymond Wong
e.g.1 (Page 4) E.g., m = 21n= 921 can be expressed as9x2 + 3(i.e., ng + r)ris defined to be 21 mod921 mod9isequalto3q=2r=30≤r<n
e.g.1 (Page 4) ◼ E.g., m = 21 n = 9 21 can be expressed as 9 x 2 + 3 (i.e., nq + r) q = 2 r = 3 0 r < n r is defined to be 21 mod 9 21 mod 9 is equal to 3
e.g.2 (Page 9)Illustration of[(-m) mod n] = n - [m mod n] E.g., m = 44 mod 5=4n= 5-4 mod 50=5-4=1= 5 - (4 mod 5) E.g., m = 99 mod 5 = 4n= 5-9 mod 5= 5 - (9 mod 5)=5-4=1
e.g.2 (Page 9) ◼ Illustration of [(-m) mod n] = n – [m mod n] ◼ E.g., m = 4 n = 5 E.g., m = 9 n = 5 -4 mod 5 -9 mod 5 4 mod 5 = 4 9 mod 5 = 4 = 5 – (4 mod 5) = 5 – (9 mod 5) = 5 – 4 = 1 = 5 – 4 = 1
e.g.3 (Page 10)2x8mod9=16mod9=7(2 mod 9) (8 mod 9) = 2 x8 = 16Conclusion:2 x 8 mod 9 ± (2 mod 9) (8 mod 9)(2 + 8) mod 9 = 1(2 mod 9) + (8 mod 9) = 2 + 8 = 10Conclusion:(2 + 8) mod 9 ± (2 mod 9) + (8 mod 9)
e.g.3 (Page 10) 2 x 8 mod 9 = 16 mod 9 = 7 (2 mod 9) (8 mod 9) = 2 x 8 = 16 (2 + 8) mod 9 = 1 (2 mod 9) + (8 mod 9) = 2 + 8 = 10 Conclusion: 2 x 8 mod 9 (2 mod 9) (8 mod 9) Conclusion: (2 + 8) mod 9 (2 mod 9) + (8 mod 9)
e.g.4 (Page 11)Illustration of Lemma 2.2 E.g.,i= 1n = 51 mod5= 1(1 + 5) mod 5 = 6 mod 5 = 1(1 + (-1)x5) mod 5 = -4 mod 5 = 1(1 + 2x5) mod 5 = 11 mod 5 = 1(1 + (-2)x5) mod 5 = -9 mod 5 = 1(1 + (-3)x5)mod 5=-14 mod5= 1(1 + 3x5) mod 5 = 16 mod 5 = 1(1 + k5) mod 5 = 1
e.g.4 (Page 11) ◼ Illustration of Lemma 2.2 ◼ E.g., i = 1 n = 5 1 mod 5 = 1 (1 + 5) mod 5 = 6 mod 5 = 1 (1 + 2x5) mod 5 = 11 mod 5 = 1 (1 + 3x5) mod 5 = 16 mod 5 = 1 (1 + k.5) mod 5 = 1 (1 + (-1)x5) mod 5 = -4 mod 5 = 1 (1 + (-2)x5) mod 5 = -9 mod 5 = 1 (1 + (-3)x5) mod 5 = -14 mod 5 = 1