FIT2093 Week 4 Tutorial Sheet (Optional)
Public Key Encryption: Part 1 (for self-study)
1. Write the following composite numbers as a multiplication of their prime factors.
(a) 72 (b) 111
Copyright By PowCoder代写 加微信 powcoder
(a) 72=23×32 (b) 111=3×37
(c) 1024 = 210
2. Complete the following modular arithmetic operations and determine the result:
(a) (32 + 18) mod 7
(b) (12×8) mod 7
(c) (56 + 125) mod 11
(d) (33 − 45) mod 9
(e) 1004 mod 7
(f) 7−1 mod 31
(g) 9−1 mod 19
(a) (32+8) mod 7
(32 mod 7)+(8 mod 7) mod 7 4 + 1 mod 7 = 5
(b) (12×8) mod 7
(12 mod 7)×(8 mod 7) mod 7) 5 × 1 mod 7 = 5
(c) (56 + 125) mod 11
(56 mod 11) + (125 mod 11) mod 11 1 + 4 mod 11 = 5
(d) (33 − 45) mod 9
(33 mod 9)−(45 mod 9) mod 9 6 + 0 mod 9 = 6
(e) 1004 mod7=(100mod7)4 mod7 24 mod7=16mod7=2
(f) SinceGCDof31and9is1thatmultiplicativeinverseexists.Since7∗9=63=31×2+1so the inverse is 7−1 = 2 mod 31.
(g) 9×(−2)=−18=19−18mod19=1mod19,thusthemultiplicativeinverseof9is−2which is 19 − 2 = 17. The answer is 17.
3. Using the “Square and Multiply” modular exponentiation algorithm calculate the following:
(a) 857 mod 11 (b) 1562 mod 31
FIT2093 Week 4 Tutorial Sheet (Optional)
(a) StartwithMSbit𝑏5 =1of𝑒=5710 =1110012
Set 𝑧 = 𝑎 = 8 and 𝑛 = 11
𝑖=4:bit𝑏4=1→− square&multiply:z=az2mod𝑛=8∗82mod11=6 𝑖=3:bit𝑏3=1→− square&multiply:z=az2mod𝑛=8∗62mod11=2 𝑖=2:bit𝑏2=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=22mod11=4 𝑖=1:bit𝑏1=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=42mod11=5 𝑖=0:bit𝑏0=1→− square multiply:z=az2mod𝑛=8∗52mod11=2 The answer is 2.
(b) StartwithMSbit𝑏5 =1of𝑒=6210 =1111102
Set 𝑧 = 𝑎 = 15 and 𝑛 = 31
𝑖=4:bit𝑏4=1→− square&multiply:z=az2mod𝑛=15∗152mod31=27 𝑖=3:bit𝑏3=1→− square&multiply:z=az2mod𝑛=15∗272mod31=23 𝑖=2:bit𝑏2=1→− square&multiply:z=az2mod𝑛=15∗232mod31=30 𝑖=1:bit𝑏1=1→− square&multiply:z=az2mod𝑛=15∗302mod31=15 𝑖=0:bit𝑏0=0→− 𝑠𝑞𝑢𝑎𝑟𝑒∶z=z2mod𝑛=152mod31=8
The answer is 8.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com