{"id":670,"date":"2024-11-27T02:51:34","date_gmt":"2024-11-27T02:51:34","guid":{"rendered":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/?page_id=670"},"modified":"2024-11-27T03:12:55","modified_gmt":"2024-11-27T03:12:55","slug":"670-2","status":"publish","type":"page","link":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/670-2\/","title":{"rendered":"Modular Arithmetic Foundations"},"content":{"rendered":"\n

CS 463\/563: Cryptography for Cybersecurity
Fall 2024
Homework #2<\/strong><\/h2>\n\n\n\n


Note: Modular arithmetic is fundamental to cryptography. In this system, you can only have integers. For example, in mod 14 system, the answer MUST be 0,1,2,3,\u20269,11,12,13. Non-integer values have no place in this arithmetic. If you have an answer which is a floating point, such as 12.5, then you are doing something wrong.<\/p>\n\n\n\n


Question 1: Modular Arithmetic: Compute the following without a calculator. SHOW YOUR WORK.<\/p>\n\n\n\n


i. 150 * 92 mod 14 (Hint: a*b mod c = ((a mod c) * (b mod c)) mod c)
((150 mod 14) * (92 mod 14)) mod 14 ((10) * (8)) mod 14
80 mod 14 = 10
Final answer is 10

ii. 6 * (4\/11) mod 14 (Hint: In mod 14 system, a, a+14, a+28, a+42, a+56, etc. are all equivalent)
((6 mod 14) * (4\/11 mod 14)) mod 14 ((6) * (4\/11 mod 14)) mod 14
11x mod 14 = 4 mod 14 4 mod 14 = 4 (11<\/em>8) mod 14 = 4
((6) * (8)) mod 14 48 mod 14 = 6 Final answer is 6

iii. 24\/17 mod 14 (Hint: First, simplify the numerator and denominator separately by applying the mod function independently, and then solve as in (ii) above)
24 mod 14 = 10
17 mod 14 = 3
3 x 5 = 15, and 15 mod 14 = 1
(24\/17) mod 14 = (10 x 5) mod 14
50 mod 14 = 8
Final answer is 8

iv. 48 * 512 mod 14 (Hint: Try to compute the exponent in stages, each time simplifying it using the mod function. For example, to compute 48 mod 14, express 48 mod 14 = (42 mod 14)4 mod 14, compute the one in the parenthesis, and repeat this process)
4^8 mod 14
(4^2 mod 14)^4 mod 14
(16 mod 14)^4 mod 14
2^4 mod 14
16 mod 14
2
4^8 mod 14 = 2

5^12 mod 14
(5^2 mod 14)^6 mod 14
(25 mod 14)^6 mod 14
11^6 mod 14
(11^2 mod 14)^3 mod 14
(121 mod 14)^3 mod 14
9^3 mod 14
729 mod 14
1
5^12 mod 14 = 1

((4^8 mod 14)(5^12 mod 14)) mod 14 <\/em>
((2)<\/em>(1)) mod 14
2 mod 14
2
Final answer is 2

v. 510 * 68 mod 14 (same as above)
5^10 mod 14
(5^2 mod 14)^5 mod 14
(25 mod 14)^5 mod 14
11^5 mod 14
161,051 mod 14
9
5^10 mod 14 = 9

6^8 mod 14
(6^2 mod 14)^4 mod 14
(36 mod 14)^4 mod 14
8^4 mod 14
(8^2 mod 14)^2 mod 14
(64 mod 14)^2 mod 14
8^2 mod 14
64 mod 14
8
6^8 mod 14 = 8

((5^10 mod 14) * (6^8 mod 14)) mod 14
((9) * (8)) mod 14
72 mod 14
2
The final answer is 2

Question 2: SHOW YOUR WORK. You may use EXCEL or a calculator.

i. Show the elements of groups Z13 and Z* (Note that 13 is a prime number)<\/p>\n\n\n\n

Z13 = {0,1,2,3,4,5,6,7,8,9,10,11,12}
Z*13 = {1,2,3,4,5,6,7,8,9,10,11,12} <\/em><\/p>\n\n\n\n

ii. Show the elements of groups Z18 and Z<\/em> (Note that 18 is NOT a prime number)<\/p>\n\n\n\n

Z18 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}
Z*18 = { 1, 5, 7, 11, 13, 17} <\/em><\/p>\n\n\n\n

iii. Find the order of 5 in Z<\/em>*13 (Hint: Order of an element in a finite group G is the smallest positive integer k such that ak =1 where 1 is the identity element of G)

5^1 = 5
5^2 = 25 = 12 mod 13
5^3 = 125 = 8 mod 13
5^4 = 625 = 1

iv. Find (if it exists) the multiplicative inverse of 5 \u2208 Z13 (integer ring) (Hint: For a \u2208 Zn, its multiplicative inverse, if it exists, is defined as a-1 such that a.a-1 \u2261 1 mod n)
5a = 1 mod 13
5a = 1
a= 5a mod 13 =
a=1 5 mod 13 = 5
a=2 10 mod 13 = 10
a=3 15 mod 13 = 2
a=4 20 mod 13 = 7
a=5 25 mod 13 = 12
a=6 30 mod 13 = 4
a=7 35 mod 13 = 9
a=8 40 mod 13 = 1
Final answer is the inverse of 5 is 8 in z13

v. Is Z*13 a cyclic group? If so, what is its order and the generator element? (Hint: group G which contains some element \u03b1 with maximum order ord(\u03b1) = |G| is said to be cyclic. Elements with maximum order are called generators)

Yes Z13 is a cyclic group. <\/em>
2^2 = 4 mod 13 = 4 <\/em>
2^3 = 8 mod 13 = 8 <\/em>
2^4 = 16 = 3 mod 13 = 3 <\/em>
2^5 = 2<\/em>*2^4 = 2*3 = 6 mod 13 = 6 <\/em>
2^6 = 2<\/em>*2^5 = 2*6 = 12 mod 13 = 12 <\/em>
2^7 = 2<\/em>*2^6 = 2*12 = 24 = 11 mod 13 = 11 <\/em>
2^8 = 2<\/em>*2^7 = 2*11 = 22 = 9 mod 13 = 9<\/em>
2^9 = 2<\/em>*2^8 = 2*9 = 18 = 5 mod 13 = 5 <\/em>
2^10 = 2<\/em>*2^9 = 2*5 = 10 mod 13 = 10<\/em>
2^11 = 2<\/em>*2^10 = 2*10 = 20 = 7 mod 13 = 7<\/em>
2^12 = 2<\/em>*2^11 = 2*7 = 14 = 1 mod 13 = 1

12 is the smallest integer such that 2^12 = 1 mod 13 and thus the order of 2 is 12 in the group.

2 is also the element of maximum order and is thus the generator element of this group.<\/p>\n","protected":false},"excerpt":{"rendered":"

CS 463\/563: Cryptography for Cybersecurity Fall 2024Homework #2 Note: Modular arithmetic is fundamental to cryptography. In this system, you can only have integers. For example, in mod 14 system, the answer MUST be 0,1,2,3,\u20269,11,12,13. Non-integer values have no place in this arithmetic. If you have an answer which is a floating point, such as 12.5,… <\/p>\n

Read More<\/a><\/div>\n","protected":false},"author":25223,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/pages\/670"}],"collection":[{"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/users\/25223"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/comments?post=670"}],"version-history":[{"count":2,"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/pages\/670\/revisions"}],"predecessor-version":[{"id":698,"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/pages\/670\/revisions\/698"}],"wp:attachment":[{"href":"https:\/\/sites.wp.odu.edu\/edwin-wells-4\/wp-json\/wp\/v2\/media?parent=670"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}