{"id":66,"date":"2018-07-21T10:21:14","date_gmt":"2018-07-21T10:21:14","guid":{"rendered":"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=66"},"modified":"2018-12-27T09:58:09","modified_gmt":"2018-12-27T09:58:09","slug":"modular-arithmetic","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/chapter\/modular-arithmetic\/","title":{"rendered":"Modular Arithmetic"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\n\u27a2\u00a0\u00a0 To understand the basics of Modular Arithmetic\r\n\r\n\u27a2\u00a0\u00a0 To learn about the binary operation\r\n\r\n\u27a2\u00a0\u00a0 To learn about the additive and multiplicative inverse\r\n\r\n\u27a2\u00a0\u00a0 Some examples related to these concepts\r\n\r\n \r\n\r\n \r\n\r\n6.1 INTRODUCTION<\/strong>\r\n\r\n \r\n

Modular arithmetic is a system of arithmetic for integers, <\/a>where numbers \"wrap around\" upon reaching a certain value. Modular arithmetic allows us to easily create groups, <\/a>rings <\/a>and fields <\/a>which are fundamental building blocks of most modern public-key cryptosystems.<\/p>\r\n \r\n

For example, Diffie-Hellman <\/a>uses the multiplicative group of integers modulo a prime pp. There are other groups which would work.Modular or clock arithmetic is arithmetic on a circle instead of a number line modulo N , we use only the twelve whole numbers from 0 through N-1<\/p>\r\n \r\n\r\n1:00 and and 13:00 hours are the same(1=13mod12)\r\n\r\n1:00 and and 25:00 hours are the same(1=25mod12)<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n6.1.1 Usage of Modular Arithmetic<\/strong>\r\n\r\n \r\n

Modular arithmetic is very well understood in terms of algorithms for various basic operations. That is one of thereason why we use finite fields (AES) in symmetric key cryptography. Cryptography requires hard problems. Some problems become hard with modular arithmetic. For example, logarithms are easy to compute over all integers . but can become hard to compute when you introduce a modular reduction. Similarly with finding roots. Mod-arithmetic is the central mathematical concept in cryptography. Almost any cipher from the Caesar Cipher to the RSA Cipher use it.There are two types of \u201cmod\u201d.<\/p>\r\n \r\n\r\nThe mod<\/strong> function\r\n\r\n \r\n\r\n\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Inputs a number a<\/em> and a base b<\/em>\r\n\r\n\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Outputs a<\/em> mod<\/strong> b<\/em> a number between 0 and b<\/em> \u20131 inclusive\r\n\r\n\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 This is the remainder of a b\r\n\r\n\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Similar to Java\u2019s % operator.\r\n\r\n\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Relates two numbers a, a\u2019<\/em> to each other relative some base b<\/em>\r\n\r\n\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 a a\u2019 <\/em>(mod b<\/em>) means that a <\/em>and a\u2019 <\/em>have the same remainder when dividing by b<\/em>\r\n\r\n \r\n\r\nSimilar to Java\u2019s \u201c%\u201d operator except that answer is always positive. E.G. -10 mod<\/strong> 3 = 2, but in Java \u201310%3 = -1.\r\n\r\n \r\n\r\nQ:\u00a0\u00a0\u00a0\u00a0 Compute\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 113 mod<\/strong> 24\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 -29 mod<\/strong> 7\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n6.2 Congruent numbers<\/strong>\r\n\r\n \r\n

Integers that leave the same remainder when divided by the modulus m are somehow similar, however, not identical. Such numbers are called \"congruent\". For instance, 1 and 13 and 25 and 37 are congruent mod 12 since they all leave the same remainder when divided by 12.<\/p>\r\n \r\n\r\nEquivalently: a mod b = a\u2019 mod b\r\n\r\n \r\n\r\nQ:\u00a0\u00a0\u00a0\u00a0 Which of the following are true?\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 3 (mod 17)\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 -3 (mod 17)\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 172\u00a0\u00a0 177 (mod 5)\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 -13\u00a0\u00a0 13 (mod 26)\r\n\r\n \r\n\r\nA:\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 3 3 (mod 17) True. any number is congruent to itself (3-3 = 0, divisible by all)\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 -3 (mod 17) False. (3-(-3)) = 6 isn\u2019t divisible by 17.\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 172\u00a0\u00a0 177 (mod 5) True. 172-177 = -5 is a multiple of 5\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 -13\u00a0\u00a0 13 (mod 26) True: -13-13 = -26 divisible by 26.\r\n\r\n \r\n

The (mod) congruence is useful for manipulating expressions involving the mod function. It lets us view modular arithmetic relative a fixed base, as creating a number system inside of which all the calculations can be carried out.<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 a mod b\u00a0\u00a0 a (mod b)\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Suppose a\u00a0\u00a0 a\u2019 (mod b) and c\u00a0\u00a0 c\u2019 (mod b) Then:\r\n\r\n<\/div>\r\n

\r\n

\u00a0 \u00a0 \u2013\u00a0 a+c\u00a0\u00a0\u00a0 (a\u2019+c\u2019 )(mod b)<\/p>\r\n

\u2013\u00a0 ac\u00a0\u00a0 a\u2019c\u2019 (mod b)<\/p>\r\n

\u2013\u00a0 a k\u00a0\u00a0 \u00a0a\u2019 k (mod b)<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n6.3Modular Addition<\/strong>\r\n\r\n \r\n

First add the two numbers, Secondly, divide the sum by the modulus to compute the remainder. In \"8-hour-land\" where a day lasts only 8 hours, we would add 12 and 9 as follows: First, 12+9 = 21, secondly 21 divided by the modulus 8 leaves a remainder of 5 since 21=2*8+5.<\/p>\r\n \r\n\r\n6.4 Modular Subtraction<\/strong>\r\n\r\n \r\n\r\nFirst subtract, secondly compute the remainder. Example 1: 25 - 8 = 17 MOD 12 = 5\r\n\r\nExample 2: 50 - 11 = 39 MOD 12 = 3\r\n\r\n \r\n\r\n6.5 Modular Multiplication<\/strong>\r\n\r\n \r\n

A mod expert would find the answer to 123 * 62 mod 12 immediately. It is 6.Without being a Gauss genius, she computes 123 mod 12 = 3 and 62 mod 12 = 2 and multiplies those two answers. To verify this: 123*62 mod 12 = 7626 mod 12 = 6. This computation aid is true for addition and subtraction as well<\/p>\r\n \r\n\r\n6.6 Computation Rules for Mod Arithmetic<\/strong>\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 \u25cf\u00a0a + b mod m = (a mod m) + (b mod m)\r\n\r\n\u25cf\u00a0a - b mod m = (a mod m) - (b mod m)\r\n\r\n\u25cf\u00a0a * b mod m = (a mod m) * (b mod m)\r\n\r\n<\/div>\r\n
\r\n

Example 1: <\/strong>Addition Modulo 8<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Example 3: <\/strong>Additive and Multiplicative inverses Modulo 7<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n\r\n\u00a0 6.7 Properties of Modular Arithmetic<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\n6.8 Modular Arithmetic Examples<\/strong>\r\n\r\n \r\n\r\nQ:\u00a0\u00a0\u00a0\u00a0 Compute the following.\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>307<\/strong>1001<\/strong><\/sup> mod 102<\/strong>\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>(-45 \u00b7 77) mod 17<\/strong>\r\n\r\n3.\u00a0\u00a0\"\"\u00a0\u00a0\u00a0\u00a0\u00a0<\/strong>\r\n\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>\u00a0<\/strong>\r\n\r\n\"\"\u00a0<\/strong>\r\n\r\n\u00a0<\/strong>Therefore, the answer is 0.<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\n6.9 Proving Modular Identities<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n6.10 Simple Encryption and Decryption using Modular Arithmetic<\/strong>\r\n\r\n \r\n\r\n6.10.1 Basic Steps involved in Encryption<\/strong>\r\n\r\n \r\n\r\nVariations on the following have been used to encrypt messages for thousands of years.\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Convert a message to capitals.\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 Think of each letter as a number between 1 and 26.\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 Apply an invertible modular function to each number.\r\n\r\n4.\u00a0\u00a0 Convert back to letters (0 becomes 26).<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\n6.10.2 Encryption Example<\/strong>\r\n\r\n \r\n\r\nLet the encryption function be\r\n\r\nf\u00a0 <\/em>(a<\/em>) = (3a<\/em> + 9) mod<\/strong> 26\r\n\r\nEncrypt \u201cStop Thief\u201d <\/span>\r\n\r\n1. STOP THIEF\u00a0\u00a0<\/span>(capitals)<\/span>\r\n\r\n2. 19,20,15,16 20,8,9,5,6<\/span>\r\n\r\n3. 14,17,2,5 17,7,10,24,1<\/span>\r\n\r\n4. NQBE QGJXA<\/span>\r\n\r\n<\/div>\r\n \r\n\r\n6.10.3 Decryption Example<\/strong>\r\n\r\n \r\n\r\nDecryption works the same, except that you apply the inverse function.\r\n\r\nExample: Find the inverse of\r\n\r\nf <\/em>(a<\/em>) = (3a<\/em> + 9) mod 26\r\n\r\ng <\/em>(a<\/em>) = 3-1 (a - 9)\r\n\r\n \r\n

We\u2019ll see that since gcd(3,26) = 1, the inverse of 3 is actually well defined modulo 26 and is the number 9. This gives:<\/p>\r\ng <\/em>(a<\/em>) = 9 (a - 9) mod 26 = (9a <\/em>\u2013 3) mod 26\r\n\r\n \r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n\u27a2 The basics of Modular Arithmetic is explored\r\n\r\n\u27a2 The Modular arithmetic operation is explored\r\n\r\n\r\n\r\n\r\n
you can view video on Modular Arithmetic<\/strong><\/td>\r\n\"\"<\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n\r\n\"\"","rendered":"
\"epgp<\/a>
\n<\/span><\/div>\n
\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Learning Objectives<\/strong><\/p>\n

 <\/p>\n

\u27a2\u00a0\u00a0 To understand the basics of Modular Arithmetic<\/p>\n

\u27a2\u00a0\u00a0 To learn about the binary operation<\/p>\n

\u27a2\u00a0\u00a0 To learn about the additive and multiplicative inverse<\/p>\n

\u27a2\u00a0\u00a0 Some examples related to these concepts<\/p>\n

 <\/p>\n

 <\/p>\n

6.1 INTRODUCTION<\/strong><\/p>\n

 <\/p>\n

Modular arithmetic is a system of arithmetic for integers, <\/a>where numbers “wrap around” upon reaching a certain value. Modular arithmetic allows us to easily create groups, <\/a>rings <\/a>and fields <\/a>which are fundamental building blocks of most modern public-key cryptosystems.<\/p>\n

 <\/p>\n

For example, Diffie-Hellman <\/a>uses the multiplicative group of integers modulo a prime pp. There are other groups which would work.Modular or clock arithmetic is arithmetic on a circle instead of a number line modulo N , we use only the twelve whole numbers from 0 through N-1<\/p>\n

 <\/p>\n

1:00 and and 13:00 hours are the same(1=13mod12)<\/p>\n

1:00 and and 25:00 hours are the same(1=25mod12)<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

6.1.1 Usage of Modular Arithmetic<\/strong><\/p>\n

 <\/p>\n

Modular arithmetic is very well understood in terms of algorithms for various basic operations. That is one of thereason why we use finite fields (AES) in symmetric key cryptography. Cryptography requires hard problems. Some problems become hard with modular arithmetic. For example, logarithms are easy to compute over all integers . but can become hard to compute when you introduce a modular reduction. Similarly with finding roots. Mod-arithmetic is the central mathematical concept in cryptography. Almost any cipher from the Caesar Cipher to the RSA Cipher use it.There are two types of \u201cmod\u201d.<\/p>\n

 <\/p>\n

The mod<\/strong> function<\/p>\n

 <\/p>\n

\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Inputs a number a<\/em> and a base b<\/em><\/p>\n

\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Outputs a<\/em> mod<\/strong> b<\/em> a number between 0 and b<\/em> \u20131 inclusive<\/p>\n

\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 This is the remainder of a b<\/p>\n

\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Similar to Java\u2019s % operator.<\/p>\n

\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 Relates two numbers a, a\u2019<\/em> to each other relative some base b<\/em><\/p>\n

\u25aa\u00a0\u00a0\u00a0\u00a0\u00a0 a a\u2019 <\/em>(mod b<\/em>) means that a <\/em>and a\u2019 <\/em>have the same remainder when dividing by b<\/em><\/p>\n

 <\/p>\n

Similar to Java\u2019s \u201c%\u201d operator except that answer is always positive. E.G. -10 mod<\/strong> 3 = 2, but in Java \u201310%3 = -1.<\/p>\n

 <\/p>\n

Q:\u00a0\u00a0\u00a0\u00a0 Compute<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 113 mod<\/strong> 24<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 -29 mod<\/strong> 7<\/p>\n<\/div>\n

 <\/p>\n

\n

6.2 Congruent numbers<\/strong><\/p>\n

 <\/p>\n

Integers that leave the same remainder when divided by the modulus m are somehow similar, however, not identical. Such numbers are called “congruent”. For instance, 1 and 13 and 25 and 37 are congruent mod 12 since they all leave the same remainder when divided by 12.<\/p>\n

 <\/p>\n

Equivalently: a mod b = a\u2019 mod b<\/p>\n

 <\/p>\n

Q:\u00a0\u00a0\u00a0\u00a0 Which of the following are true?<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 3 (mod 17)<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 -3 (mod 17)<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 172\u00a0\u00a0 177 (mod 5)<\/p>\n

4.\u00a0\u00a0\u00a0\u00a0\u00a0 -13\u00a0\u00a0 13 (mod 26)<\/p>\n

 <\/p>\n

A:<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 3 3 (mod 17) True. any number is congruent to itself (3-3 = 0, divisible by all)<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 -3 (mod 17) False. (3-(-3)) = 6 isn\u2019t divisible by 17.<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 172\u00a0\u00a0 177 (mod 5) True. 172-177 = -5 is a multiple of 5<\/p>\n

4.\u00a0\u00a0\u00a0\u00a0\u00a0 -13\u00a0\u00a0 13 (mod 26) True: -13-13 = -26 divisible by 26.<\/p>\n

 <\/p>\n

The (mod) congruence is useful for manipulating expressions involving the mod function. It lets us view modular arithmetic relative a fixed base, as creating a number system inside of which all the calculations can be carried out.<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 a mod b\u00a0\u00a0 a (mod b)<\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Suppose a\u00a0\u00a0 a\u2019 (mod b) and c\u00a0\u00a0 c\u2019 (mod b) Then:<\/p>\n<\/div>\n

\n

\u00a0 \u00a0 \u2013\u00a0 a+c\u00a0\u00a0\u00a0 (a\u2019+c\u2019 )(mod b)<\/p>\n

\u2013\u00a0 ac\u00a0\u00a0 a\u2019c\u2019 (mod b)<\/p>\n

\u2013\u00a0 a k\u00a0\u00a0 \u00a0a\u2019 k (mod b)<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

6.3Modular Addition<\/strong><\/p>\n

 <\/p>\n

First add the two numbers, Secondly, divide the sum by the modulus to compute the remainder. In “8-hour-land” where a day lasts only 8 hours, we would add 12 and 9 as follows: First, 12+9 = 21, secondly 21 divided by the modulus 8 leaves a remainder of 5 since 21=2*8+5.<\/p>\n

 <\/p>\n

6.4 Modular Subtraction<\/strong><\/p>\n

 <\/p>\n

First subtract, secondly compute the remainder. Example 1: 25 – 8 = 17 MOD 12 = 5<\/p>\n

Example 2: 50 – 11 = 39 MOD 12 = 3<\/p>\n

 <\/p>\n

6.5 Modular Multiplication<\/strong><\/p>\n

 <\/p>\n

A mod expert would find the answer to 123 * 62 mod 12 immediately. It is 6.Without being a Gauss genius, she computes 123 mod 12 = 3 and 62 mod 12 = 2 and multiplies those two answers. To verify this: 123*62 mod 12 = 7626 mod 12 = 6. This computation aid is true for addition and subtraction as well<\/p>\n

 <\/p>\n

6.6 Computation Rules for Mod Arithmetic<\/strong><\/p>\n<\/div>\n

\n

\u00a0 \u00a0 \u25cf\u00a0a + b mod m = (a mod m) + (b mod m)<\/p>\n

\u25cf\u00a0a – b mod m = (a mod m) – (b mod m)<\/p>\n

\u25cf\u00a0a * b mod m = (a mod m) * (b mod m)<\/p>\n<\/div>\n

\n

Example 1: <\/strong>Addition Modulo 8<\/p>\n

 <\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Example 3: <\/strong>Additive and Multiplicative inverses Modulo 7<\/p>\n<\/div>\n

\"\"<\/p>\n

\n

\u00a0 6.7 Properties of Modular Arithmetic<\/strong><\/p>\n

 <\/p>\n

\"\"<\/p>\n<\/div>\n

\n

 <\/p>\n

6.8 Modular Arithmetic Examples<\/strong><\/p>\n

 <\/p>\n

Q:\u00a0\u00a0\u00a0\u00a0 Compute the following.<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>307<\/strong>1001<\/strong><\/sup> mod 102<\/strong><\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>(-45 \u00b7 77) mod 17<\/strong><\/p>\n

3.\u00a0\u00a0\"\"\u00a0\u00a0\u00a0\u00a0\u00a0<\/strong><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>\u00a0<\/strong><\/p>\n

\"\"\u00a0<\/strong><\/p>\n

\u00a0<\/strong>Therefore, the answer is 0.<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

6.9 Proving Modular Identities<\/strong><\/p>\n

 <\/p>\n

\"\"<\/p>\n

 <\/p>\n

6.10 Simple Encryption and Decryption using Modular Arithmetic<\/strong><\/p>\n

 <\/p>\n

6.10.1 Basic Steps involved in Encryption<\/strong><\/p>\n

 <\/p>\n

Variations on the following have been used to encrypt messages for thousands of years.<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 Convert a message to capitals.<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 Think of each letter as a number between 1 and 26.<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 Apply an invertible modular function to each number.<\/p>\n

4.\u00a0\u00a0 Convert back to letters (0 becomes 26).<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

6.10.2 Encryption Example<\/strong><\/p>\n

 <\/p>\n

Let the encryption function be<\/p>\n

f\u00a0 <\/em>(a<\/em>) = (3a<\/em> + 9) mod<\/strong> 26<\/p>\n

Encrypt \u201cStop Thief\u201d <\/span><\/p>\n

1. STOP THIEF\u00a0\u00a0<\/span>(capitals)<\/span><\/p>\n

2. 19,20,15,16 20,8,9,5,6<\/span><\/p>\n

3. 14,17,2,5 17,7,10,24,1<\/span><\/p>\n

4. NQBE QGJXA<\/span><\/p>\n<\/div>\n

 <\/p>\n

6.10.3 Decryption Example<\/strong><\/p>\n

 <\/p>\n

Decryption works the same, except that you apply the inverse function.<\/p>\n

Example: Find the inverse of<\/p>\n

f <\/em>(a<\/em>) = (3a<\/em> + 9) mod 26<\/p>\n

g <\/em>(a<\/em>) = 3-1 (a – 9)<\/p>\n

 <\/p>\n

We\u2019ll see that since gcd(3,26) = 1, the inverse of 3 is actually well defined modulo 26 and is the number 9. This gives:<\/p>\n

g <\/em>(a<\/em>) = 9 (a – 9) mod 26 = (9a <\/em>\u2013 3) mod 26<\/p>\n

 <\/p>\n

 <\/p>\n

Summary<\/strong><\/p>\n

\u27a2 The basics of Modular Arithmetic is explored<\/p>\n

\u27a2 The Modular arithmetic operation is explored<\/p>\n\n\n\n
you can view video on Modular Arithmetic<\/strong><\/td>\n\"\"<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\"\"<\/p>\n","protected":false},"author":3,"menu_order":5,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-kulothungan"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-66","chapter","type-chapter","status-publish","hentry","contributor-dr-kulothungan"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/66","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":6,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/66\/revisions"}],"predecessor-version":[{"id":531,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/66\/revisions\/531"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/66\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/media?parent=66"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapter-type?post=66"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/contributor?post=66"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/license?post=66"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}