{"id":77,"date":"2018-07-21T10:43:56","date_gmt":"2018-07-21T10:43:56","guid":{"rendered":"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=77"},"modified":"2018-12-27T10:00:07","modified_gmt":"2018-12-27T10:00:07","slug":"modular-exponentiation","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/chapter\/modular-exponentiation\/","title":{"rendered":"Modular Exponentiation"},"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\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n\u00d8\u00a0 To review the concept of Modular Exponentiation\r\n\r\n\u00d8\u00a0\u00a0 To define the purpose of Modular Exponentiation in cryptography\r\n\r\n\u00d8\u00a0\u00a0 To discuss about the inverse multiplication\r\n\r\n\u00d8\u00a0\u00a0 To understand these concepts with some examples\r\n\r\n \r\n\r\n7.1 Introduction<\/strong>\r\n\r\n \r\n

Modular exponentiation is an exponentiation\u00a0\u00a0<\/a><\/span>performed over a modulus. <\/a>It is useful in computer science, <\/a>especially in the field of public-key cryptography.<\/a><\/p>\r\n \r\n

Consider the following scenario,<\/p>\r\n \r\n\r\nAB<\/sup> mod C = ( (A mod C)B<\/sup> ) mod C\r\n\r\n \r\n\r\nOften we want to calculate AB mod C for large values of B.\r\n\r\nUnfortunately, AB<\/sup> becomes very large for even modest sized values for B.\r\n\r\n \r\n\r\nFor Example:\r\n\r\n \r\n\r\n290<\/sup> = 1237940039285380274899124224\r\n\r\n7256<\/sup> = 221359540004604815545018861547494593716251705026007306991636639052470\r\n\r\n4974007989996848003433\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 837940380782794455262312607598867363425940560014856027866381946458951\r\n\r\n20583737911647366324673350968 0721264246243189632348313601\r\n\r\n \r\n

These huge values cause our calculators and computers to return overflow errors and also it would take a long time to find the mod of these huge numbers directly.In order to implement exponentiation relative some modulo needs to be done a lot. So this operation better be doable, and fast.<\/p>\r\n \r\n\r\n \r\n\r\n7.2 Fast Modular Exponentiation<\/strong>\r\n\r\n \r\n

For real-life needs of number theoretic computations, just raising numbers to large exponents isn't very useful, because extremely huge numbers start appearing very quickly, and these don't have much use. What's much more useful is modular\u00a0<\/a>exponentiation, <\/a>raising integers to high powers . In such case, we can reuse the efficient algorithms developed in the previous article, with very few modifications to perform modular exponentiation as well. This is possible because of some convenient properties of modular arithmetic. In order to implement exponentiation relative some modulo needs to be done a lot. So this operation better be doable, and fast.<\/p>\r\n \r\n\r\n1)\u00a0 Q: How is it even possible to compute 28533397<\/sup> mod 4559 ?\r\n\r\nAfter all, 28533397<\/sup> has approximately 3397\u00b74 digits!\r\n\r\n \r\n\r\nA:\u00a0\u00a0 By taking the mod after each multiplication.\r\n\r\nexample:\r\n\r\n \r\n\r\n233<\/sup> mod 30\u00a0=\u00a0\u00a0 -73<\/sup> (mod 30)\r\n\r\n= (-7)2<\/sup> \u00b7(-7) (mod 30) 49 \u00b7 (-7) (mod 30) 19\u00b7(-7) (mod 30) -133 (mod 30)\r\n\r\n=17 (mod 30)\r\n\r\n \r\n\r\nTherefore, 233<\/sup> mod 30 = 17.\r\n\r\n<\/div>\r\n \r\n

\r\n

2)\u00a0 Q<\/strong>: What if had to figure out 2316<\/sup> mod 30. Same way tedious: need to multiply 15 times. Is there a better way?<\/p>\r\n \r\n\r\nA<\/strong>: Better way. Notice that 16 = 2\u00b72\u00b72\u00b72 so that 2316<\/sup> = 232\u00b72\u00b72\u00b72<\/sup> = (((232<\/sup>)2<\/sup>)2<\/sup>)2<\/sup>\r\n\r\n \r\n\r\nTherefore:\r\n\r\n \r\n\r\n2316<\/sup> mod 30\u00a0\u00a0\u00a0 (((-72<\/sup>)2<\/sup>)2<\/sup>)2<\/sup> (mod 30)\r\n\r\n=(((49)2<\/sup>)2<\/sup>)2<\/sup> (mod 30)= (((-11)2<\/sup>)2<\/sup>)2<\/sup> (mod 30)\r\n\r\n=((121)2<\/sup>)2<\/sup> (mod 30) =((1)2<\/sup> )2<\/sup> (mod 30)\r\n\r\n=(1)2<\/sup> (mod 30) =\u00a0 1(mod 30)\r\n\r\nWhich implies that 2316 mod 30 = 1.\r\n\r\n \r\n\r\n3) Q<\/strong>: How about 2325<\/sup> mod 30 ?\r\n\r\n \r\n

A<\/strong>: The previous method of repeated squaring works for any exponent that\u2019s a power of 2. 25. However, we can break 25 down as a sum of such powers: 25 = 16 + 8 + 1. Apply repeated squaring to each part, and multiply the results together. Previous calculation:<\/p>\r\n \r\n\r\n238<\/sup> mod 30 = 2316<\/sup> mod 30 = 1\r\n\r\n \r\n\r\nThus: 2325<\/sup> mod 30\u00a0\u00a0\u00a0 2316<\/sup>+8+1 (mod 30)\r\n\r\n \r\n\r\nThe previous method of repeated squaring works for any exponent that\u2019s a power of\r\n\r\n \r\n

2.\u00a0\u00a0\u00a0\u00a0 25. However, we can break 25 down as a sum of such powers: 25 = 16 + 8 + 1. Apply repeated squaring to each part, and multiply the results together. Previous calculation:<\/p>\r\n \r\n\r\n238<\/sup> mod 30 = 2316<\/sup> mod 30 = 1\r\n\r\n \r\n\r\nThus: 2325<\/sup> mod 30\u00a0\u00a0 2316+8+1<\/sup> (mod 30) 2316<\/sup>\u00b7238<\/sup>\u00b7231<\/sup> (mod 30)\u00a0 1\u00b71\u00b723 (mod 30)\r\n\r\n \r\n\r\nFinal answer:\u00a0\u00a0 2325<\/sup> mod 30 = 23\r\n\r\n \r\n\r\n4)\u00a0 Q<\/strong>: How could we have figured out the decomposition 25 = 16 + 8 + 1 from the binary (unsigned) representation of 25?\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 A<\/strong>: 25 = (11001)2<\/sub> This means that\r\n\r\n25 = 1\u00b716+1\u00b78+0\u00b74+0\u00b72+1\u00b71 = 16+8+1\r\n\r\n \r\n

Can tell which powers of 2 appear by where the 1\u2019s are. This follows from the definition of binary representation.<\/p>\r\n \r\n\r\n7.3 Properties of Modular Arithmetic<\/strong>\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 [(a mod n) + (b mod n)] mod n = (a + b) mod n\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 [(a mod n) - (b mod n)] mod n = (a - b) mod n\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 [(a mod n) x (b mod n)] mod n = (a x b) mod n\r\n\r\n \r\n\r\n7.3.1 Proof of property 1.<\/strong>\r\n\r\n \r\n\r\nLet (a mod n) = Ra and (b mod n) = Rb. Then, we can write a = Ra + jn for some integer j and b = Rb + kn for some integer k.\r\n\r\n \r\n\r\n(a + b) mod n = (Ra + jn + Rb + kn) mod n\r\n\r\n=\u00a0 [Ra + Rb + (k + j) n] mod n\r\n\r\n=\u00a0 (Ra + Rb) mod n\r\n\r\n=\u00a0 [(a mod n) + (b mod n)] mod n\r\n\r\n \r\n\r\n7.3.2 Example<\/strong>\r\n\r\n \r\n\r\n11 mod 8 = 3; 15 mod 8 = 7\r\n\r\n \r\n\r\n[(11 mod 8 ) + (15 mod 8)] mod 8 = 10 mod 8 = 2\r\n\r\n(11 + 15) mod 8 = 26 mod 8 = 2\r\n\r\n[(11 mod 8 ) - (15 mod 8)] mod 8 = -4 mod 8 = 4\r\n\r\n(11 - 15) mod 8 = -4 mod 8 = 4\r\n\r\n[(11 mod 8 ) x (15 mod 8)] mod 8= 21 mod 8 = 5\r\n\r\n(11 x 15) mod 8 = 165 mod 8 = 5\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n7.4 Exponentiation<\/strong>\r\n\r\n \r\n

Exponentiation is done by repeated multiplication, as in ordinary arithmetic. A good thing about modular arithmetic is that the numbers you are working with will be kept relatively small. At each stage of an algorithm, the mod function should be applied.<\/p>\r\n \r\n\r\nThus to multiply 39 * 15 mod 11<\/em> we first take mods to get\r\n\r\n \r\n\r\n39 mod 11 = 6 <\/em>and 15 mod 11= 4<\/em>\r\n\r\n \r\n\r\nThe multiplication required is now\r\n\r\n \r\n\r\n6*4 mod 11 = 24 mod 11 = 2<\/em>\r\n\r\n \r\n\r\n\"\"\r\n\r\n7.5 Modular Division<\/strong>\r\n\r\n \r\n

Modular division is defined when modular inverse of the divisor exists. The inverse of an integer \u2018x\u2019 is a another integer \u2018y\u2019 such that (x*y) % m = 1 where m is the modulus. When does inverse exist? Inverse a number \u2018a\u2019 exists under modulo \u2018m\u2019 if \u2018a\u2019 and \u2018m\u2019 are co-prime, i.e., GCD of them is 1.<\/p>\r\n \r\n\r\nWhat is 5 \u00f7 3 mod 11<\/em>?\r\n\r\n \r\n

A<\/strong>: We need to multiply 5<\/em> by the inverse<\/em> of 3 mod 11.<\/em>When you multiply a number by its inverse, the answer is 1.<\/p>\r\n \r\n\r\nThus the inverse of 2 is \u00bd since 2* \u00bd = 1\r\n\r\nThe inverse of 3 mod 11<\/em> is 4<\/em> since 3*4=1 mod 11<\/em>\r\n\r\nThus 5 \u00f7 3 mod 11 = 5*4 mod 11 = 9 mod 11<\/em>\r\n\r\n<\/div>\r\n\u00a0<\/em>\r\n

\r\n\r\n7.6 Euclidean algorithm<\/strong>\r\n\r\n \r\n

The Euclidean algorithm or Euclid's algorithm is an efficient method for computing the greatest common divisor <\/a>(GCD) of two numbers, the largest number that divides both of them without leaving a remainder. <\/a>It is named after the ancient Greek mathematician <\/a>Euclid, <\/a>who first described it in Euclid's Elements <\/a>(c. 300 BC). It is an example of an algorithm, <\/a>a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions <\/a>to their simplest form, <\/a>and is a part of many other number-theoretic and cryptographic calculations.<\/p>\r\n \r\n

gcd(a,b<\/em>) = gcd(b, b<\/em> mod a<\/em>)<\/p>\r\n

int Euclid(int a, int b) {<\/p>\r\n

if (b == 0) return a;<\/p>\r\n

else return Euclid(b, b % a)<\/p>\r\n

}<\/p>\r\n \r\n\r\n7.6.1 Finding Inverses in Z<\/strong>n<\/strong>\r\n\r\n \r\n

The numbers that have inverses in Zn are relatively prime to n. We can use the Euclidean Algorithm to see if a given \u201cx\u201d is relatively prime to \u201cn\u201d; then we know that an inverse does exist. How can we find the inverse without looking at all the remainders? A problem for large n.For example if we are trying to find x with 4 x \u2261 1 ( mod 13 ) 4x\u22611(mod13). Since you already have 13 = 4 \u22c5 3 + 1 13=4\u22c53+1, it follows that 4 \u22c5 3 \u2261 \u2212 1 ( mod 13 ) 4\u22c53\u2261\u22121(mod13). That's almost, but not quite what you need.<\/p>\r\n \r\n\r\nSo let's multiply left and right by -1. Then you get:\r\n\r\n4 \u22c5 \u2212 3 \u2261 1 ( mod 13 )\r\n\r\n4\u22c5\u22123\u22611(mod13) Much closer.\r\n\r\nIt follows that 4\u22121\u2261\u22123\u226110(mod13).\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n7.6.2 Using the Extended Euclidean Algorithm<\/strong>\r\n\r\n \r\n\r\nThe extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography.\r\n\r\n \r\n