Assignment #1 Solutions January 10, 2006

Assignment #1 Solutions January 10, 2006

Problem #1 Show that ((a mod m) b) mod m (a b) mod m and ((a mod m) b) mod m (a b) mod m Practical Aspects of Modern Cryptograph June 18, 2023

Answer #1 Let r1 a mod m, r2 (a b) mod m, and r3 ((a mod m) b) mod m. Then there exist integers q1, q2, and q3 such that a q1m r1, a b q2m r2, and ((a mod m) b) q3m r3. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #1 (cont.) r2 – r3 ((a b) – q2m) – ((a mod m) b) – q3m) ((a b) – q2m) – ((r1 b) – q3m) ((a b) – q2m) – (((a – q1m) b) – q3m) (q1 – q2 q3)m But 0 r2 m and 0 r3 m, so r2 – r3 m. Thus, (q1 – q2 q3) 0, and therefore r2 r3. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #1 (cont.) Let r1 a mod m, r2 (a b) mod m, and r3 ((a mod m) b) mod m. Then there exist integers q1, q2, and q3 such that a q1m r1, a b q2m r2, and ((a mod m) b) q3m r3. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #1 (cont.) r2 – r3 ((a b) – q2m) – ((a mod m) b) – q3m) ((a b) – q2m) – ((r1 b) – q3m) ((a b) – q2m) – (((a – q1m) b) – q3m) (bq1 – q2 q3)m But 0 r2 m and 0 r3 m, so r2 – r3 m. Thus, (bq1 – q2 q3) 0, and therefore r2 r3. Practical Aspects of Modern Cryptograph June 18, 2023

Problem #2 Find the mod 11 multiplicative inverse of each value x in the range 0 x 11. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #2 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 4 6 8 10 1 3 5 7 9 3 3 6 9 1 4 7 10 2 5 8 4 4 8 1 5 9 2 6 10 3 7 5 5 10 4 9 3 8 2 7 1 6 6 6 1 7 2 8 3 9 4 10 5 7 7 3 10 6 2 9 5 1 8 4 8 8 5 2 10 7 4 1 9 6 3 9 9 7 5 3 1 10 8 6 4 2 10 10 9 8 7 6 5 4 3 2 1 Practical Aspects of Modern Cryptograph June 18, 2023

Answer #2 (cont.) 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 4 6 8 10 1 3 5 7 9 3 3 6 9 1 4 7 10 2 5 8 4 4 8 1 5 9 2 6 10 3 7 5 5 10 4 9 3 8 2 7 1 6 6 6 1 7 2 8 3 9 4 10 5 7 7 3 10 6 2 9 5 1 8 4 8 8 5 2 10 7 4 1 9 6 3 9 9 7 5 3 1 10 8 6 4 2 10 10 9 8 7 6 5 4 3 2 1 Practical Aspects of Modern Cryptograph June 18, 2023

Answer #2 (cont.) The same cannot be done mod 12. For example, 2 Y mod 12 is even regardless of the value of Y. Therefore 2 does not have a mod 12 multiplicative inverse. Practical Aspects of Modern Cryptograph June 18, 2023

Problem #3 Compute 3141592653589793238462643383279502884197169399375105820974944 5923078164 mod 11. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #3 31 mod 11 3 32 mod 11 9 33 mod 11 5 34 mod 11 4 35 mod 11 1 36 mod 11 3 37 mod 11 9 38 mod 11 5 39 mod 11 4 310 mod 11 1 3 4 mod 11 4 Practical Aspects of Modern Cryptograph June 18, 2023

Problem #4 Compute 2718281828459045235360287471352662497757247093699959574966967 6277240766 mod 33. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #4 21 mod 33 2 22 mod 33 4 23 mod 33 8 24 mod 33 16 25 mod 33 32 26 mod 33 31 27 mod 33 29 28 mod 33 25 29 mod 33 17 210 mod 33 1 3 6 mod 33 31 Practical Aspects of Modern Cryptograph June 18, 2023

Problem #5 If p is a prime, then for integers a such that 0 a p, then a p - 1 mod p 1. Use this fact to show that 65 is not prime. Practical Aspects of Modern Cryptograph June 18, 2023

Answer #5 21 mod 65 2 22 mod 65 4 24 mod 65 16 28 mod 65 61 216 mod 65 16 232 mod 65 61 264 mod 65 16 264 mod 65 16 1 Thus 65 is not prime. Practical Aspects of Modern Cryptograph June 18, 2023