Computing Large Modular Exponents
Today, we'll be talking about something from number theory that comes up a lot in cryptography – modular exponentiation.
If you've ever taken a look at any resource related to the field of cryptography, you must have come across expressions like \(3^{97}\) mod \(353\) or \(327^{400}\) mod \(919\) or something like that, right?
Well, if you've ever wondered how such calculations are actually done like I did–after all, even calculators excuse themselves with a Math Error! when faced with such numbers–you're about to get your answer.
Now, this is not a post about modular arithmetic in general, so I'll be focusing mainly on modular exponentiation, but let me just start with a very brief introduction of the basics. If you are already aware of what modular arithmetic is, you may skip to the next section (sections are separated by dashes). If you're not, read the paragraphs below, and if you still don't understand it, Google around and come back to read the next section once you've got the basics in hand.
Modular arithmetic is basically the arithmetic of a clock. What's 4 hours after 10? 2 o'clock! But \(10 + 4 = 14\), isn't it? So what happens? What happens is that the numbers circle back after 12. For the purpose of this discussion, let's take 12 o'clock to be 0 o'clock, the way it's shown on some digital clocks, because it will simplify things. So, the rule is that after 11, you go back to 0 and then 1 and 2 and 3 and so on. Similarly, what's 6 hours before 3 o'clock? 9 o'clock. This means that the wraparound works backwards as well. Before 0, there comes 11, and then 10 and so on. This is fundamentally what modular arithmetic is, though here it is just modulo 12. In general, we can carry out computations modulo other numbers as well.
As far as instants of time are concerned, however, we can't really talk about multiplication like we did addition (\((10 + 4)\) mod \(12 = 2)\) and subtraction (\((3 - 6)\) mod \(12 = 9)\) above. But when talking about modular arithmetic in general, multiplication is also a possibility, and is dealt with similarly. For example, if we compute \((4 * 5)\) mod \(7\), we get 6, because \(4 * 5 = 20\), but our numbers loop back after 6, so 7 goes back to 0, 8 is 1, and so on, 14 is again 0, and so 20 is 6. This enumeration is only for explaining the concept, by the way, in reality we just carry out the computation (addition, subtraction or multiplication–division is a bit more complicated), then divide the answer (20 in this example) by the modulus (7 here), and the remainder is our desired answer (6 in this case).
The above relationship can be understood by looking at integer division. We divide a number \(n\) by a divisor \(d\), and get a quotient \(q\) and a remainder \(r\), with the relationship between these quantities being \(n = qd + r\). In this relation, if we put the modulus \(m\) in place of \(d\), i.e. \(n = qm + r\), then \(r\) is our answer. There are many other things to be said about modular arithmetic, but let's leave it at that and move towards the main topic of our post. But one last thing before we move on: to calculate \(n\) mod \(m\) on a calculator, shift to Base-N mode (the decimal option), and enter: \(n-n/m*m\). (The way this works is that \(n/m\) gets evaluated first, but the decimal points get truncated due to the Base-N mode, so it effectively serves as the quotient, making the expression equivalent to \(n - qm\), which is equal to \(r\).) There are other methods, but this is both simple, and generally applicable.
––––––––––
Now, for addition, subtraction or multiplication (and even small-scale exponentiation), we can just carry out the computations normally to simplify the expression to \(n\) mod \(m\) and then calculate it. But what about expressions like \(3^{97}\) mod \(353\) or \(327^{400}\) mod \(919\) that were mentioned at the start of the post? Those are too large to be calculated the normal way. For such computations, we make use of a property of modular arithmetic, which is:
\(ab\) mod \(m = [(a\) mod \(m)(b \) mod \(m)]\) mod \(m\)
This property (which also holds for higher number of factors, e.g. \(abc\), \(abcd\) and so on) allows us to decompose our problem into smaller and smaller problems, which we can solve and then combine their solutions to get the solution to our original problem. Typically, the decomposition we carry out involves powers of 2, and so it is called exponentiation by squaring. We will first discuss this method, and then another option which could be more efficient, but is not as systematic.
Instead of explaining the method using general terms, I think it will be more useful to learn it by doing a practical example. So, let us find the answer to \(3^{97}\) mod \(353\) using this method.
First, we convert the exponent to binary. \(97\) in binary is \(1100001_{2}\) (do the conversion however you are comfortable). What this means is that \(97 = 64 + 32 + 1\) (because each of the bits represents a power of 2 and so on). So, by the laws of indices, \(3^{97} =\) \(3^{64}\) * \(3^{32}\) * \(3^{1}\).
Next, we find \(3^{k}\) mod \(353\) for \(k = 1, 2, 4, 8, 16, 32\) and \(64\) one by one. The first three are smaller than the modulus, so have themselves as the answers:
\(3^{1}\) mod \(353\) = \(3\) mod \(353\) = \(3\)
\(3^{2}\) mod \(353\) = \(9\) mod \(353\) = \(9\)
\(3^{4}\) mod \(353\) = \(81\) mod \(353\) = \(81\)
The next two can still be computed using a calculator (via the method described at the end of the last section, or any other one–there can be several):
\(3^{8}\) mod \(353\) = \(6561\) mod \(353\) = \(207\)
\(3^{16}\) mod \(353\) = \(43046721\) mod \(353\) = \(136\)
However, when we go further, it becomes impossible to calculate the mods even using a calculator, because even though the calculator can compute the powers of 3, the answers are only provided up to a certain number of significant figures. Thus, we begin to use the property of modular multiplication mentioned above.
\(3^{32}\) mod \(353 = [(3^{16}\) mod \(353)(3^{16} \) mod \(353)]\) mod \(353 = (136 * 136)\) mod \(353\) = \(18496\) mod \(353\) = \(140\)
\(3^{64}\) mod \(353 = [(3^{32}\) mod \(353)(3^{32} \) mod \(353)]\) mod \(353 = (140 * 140)\) mod \(353\) = \(19600\) mod \(353\) = \(185\)
This could be continued further if required, but since we computed above that \(3^{97} =\) \(3^{64}\) * \(3^{32}\) * \(3^{1}\), we have already obtained the highest exponent we need. From the computations above, we have:
\(3^{1}\) mod \(353\) = \(3\)
\(3^{32}\) mod \(353\) = \(140\)
\(3^{64}\) mod \(353\) = \(185\)
Using these values with the relationship, we get:
\(= (185 * 140 * 3)\) mod \(353\) = \(77700\) mod \(353\) = \(40\)
Thus, our answer is \(3^{97}\) mod \(353 = 40\). See? Wasn't too difficult, right? (Though, admittedly, a bit tedious. But the joy of solving a problem even a calculator couldn't solve right off the bat more than makes up for it, no?) So, equipped with this method in your arsenal, you can now solve ridiculously large modular exponents by yourself and impress your friends. Haha.
––––––––––
As a final point, let me now talk a bit about how we can carry out this computation a bit more efficiently. Instead of decomposing the expression into factors necessarily involving powers of 2, we can decompose it iteratively, at each step taking into account the largest computation we can accurately perform with a calculator. Let's try this method on \(248^{97}\) mod \(353\).
First, we do some trial-and-error to see what power of 248 can accurately be calculated using a calculator. We find that it is \(248^{4} = 3782742016\), which gives us \(248^{4}\) mod \(353 = 17\).
Now, we see that \(97 = 4 * 24 + 1\), so \(248^{97} =\) \(248^{4*24}\) * \(248^{1}\). This means that:
\(248^{97}\) mod \(353 = [(248^{4*24}\) mod \(353)(248^{1} \) mod \(353)]\) mod \(353\)
\(= [(17^{24}\) mod \(353)(248^{1} \) mod \(353)]\) mod \(353\)
Now, we see what the highest power of 17 is that we can accurately determine using the calculator. We find it to be \(17^{8} = 6975757441\), which gives us \(17^{8}\) mod \(353 = 185\). We can also see that \(24 = 8 * 3\), and so \(17^{24} =\) \(17^{8*3}\). So, we manipulate things accordingly:
\(248^{97}\) mod \(353 = [(17^{8*3}\) mod \(353)(248^{1} \) mod \(353)]\) mod \(353\)
\(= [(185^{3}\) mod \(353)(248^{1} \) mod \(353)]\) mod \(353\)
These, we can compute directly. \(185^{3} = 6331625\), which gives us \(185^{3}\) mod \(353 = 217\), while \(248^{1}\) mod \(353 = 248\). Thus,
\(248^{97}\) mod \(353 = (217 * 248)\) mod \(353 = 53816\) mod \(353 = 160\)
The problem with this method is that it only gives a slight advantage in efficiency (in terms of the number of large mods that have to be computed), but sacrifices simplicity and thus increases the chances of making mistakes. Therefore, I don't really recommend doing such unsystematic decompositions unless you can clearly spot suitable ones.
Alright, folks, that is all for today. \(327^{400}\) mod \(919\) is your homework. Good luck!
~ ASD0x41
Comments