a0
1 (mod n)Exponentiation in modular arithmetic is defined according to the same relationship as exponentiation in normal arithmetic. Namely, given a modulus n and integers a and b, ab is defined as that number c such that
c = ab mod n
As with modular arithmetic in general, we could simply evaluate ab in the domain of all integers and then reduce the result modulo-n to find c. However, while the answer, c, will be strictly less than n, the intermediate values that we may have to work with can be enormous. For instance, let's say we wanted to find:
c = 911 mod 13
c = 31,381,059,609 mod 13
c = 3
Normally, when we work with such values we represent them as adequate approximations (the meaning of "adequate" being dictated by the application at hand). For instance, we might express 911 as 3.138x1010 and that would be close enough for most applications. In fact, expressing the result even to that resolution would frequently lead to the valid criticism that we are carrying too many significant digits and thus creating an impression of a level of accuracy that is not justified.
But work performed under modular arithmetic is, and must be, exact; regardless of how large the result is - even if it has several thousand digits - if we are off by even 1 then we get a very different answer when we reduce the result modulo-n.
The potential problem is all but impossible to truly comprehend. In practical cryptography we are frequently working with integers that have hundreds or even thousands of digits. Even if we had the resources to work with the resulting unbelievably large intermediate results (which is highly unlikely since raising an 80-digit number to another 80-digit number would result in a number with so many digits that you would have to figure out a way to write about 400 digits on every single proton and neutron in the observable universe), the time required to do so via brute force would be similarly prohibitive.
For instance, consider raising just a 10-digit number to another 10-digit number (and reducing the result modulo another 10-digit number). Even if we could multiply the present intermediate result (which will eventually have about 100 billion digits requiring nearly 4 GB of space just to store) by the 10-digit base in only one second (pretty optimistic even for a supercomputer, given the storage access requirements alone), it would take more than 3000 years to complete the calculation.
We will develop a technique that will allow a person, with just pencil and paper (no calculator), to perform this same computation performing fewer than 70 10-digit by 10-digit multiplications and modular reductions. Even if each such computation required ten minutes (which is a reasonable estimate, say, for a reasonably proficient middle school student), the work could be completed in less than twelve hours. If we let them use something as basic as the Microsoft Windows Calculator to perform the computations, they can perform the entire calculation in about half an hour. That may sound like a long time, but consider that even with only pencil and paper our teen can finish in time for a late supper while our brute force supercomputer will not finish for another thirty centuries!
When multiplying numbers using modular arithmetic, we can exploiting some basic properties to keep the range of intermediate results that we have to work to a range that is strictly less than n2. This means that we can evaluate the above expression, 911 mod 13, and never work with any number as large as 169, which is clearly a significant improvement over 31 billion and change.
The basic property that we are going to exploit to do this is
(xy) mod n = ((x mod n)(y mod n)) mod n
Simply put, when evaluating the product of two numbers, we have the option to reduce them either before or after performing the multiplication. More to the point, we can reduce any part of the expression at any time that it is useful to do so. Of course, regardless of what we do, we still have to perform a final modulo-n reduction at the end.
At first glance this may not look too useful, and that is true if x and y are already less than n. What if they aren't? For instance:
c = (132)(151) mod 13
Blindly evaluating this would go as follows:
c = 19,932 mod 13
c = 3
But using the above property we can do this much more easily:
c = (132 mod 13)(151 mod 13) mod 13
c = (2)(8) mod 13
c = 16 mod 13
c = 3
So how do we exploit this to aid in modular exponentiation?
Note that, in general,
c = ab = (a2)(ab-2)
which means that
c = ab mod n = (a2 mod n)(ab-2 mod n) mod n
The value a2 will always be less than n2 and we can use this same property to break ab-2 into smaller pieces before evaluating them. We would continue until our second factor has an exponent of 2 or less.
For example:
c = 911 mod 13 = (92 mod 13)(99 mod 13) mod 13
c = (81 mod 13)(99 mod 13) mod 13
c = (3)(99 mod 13) mod 13
c = (3)((92 mod 13)(97 mod 13)) mod 13
But since we have already evaluated (92 mod 13), we can quickly proceed to
c = (3)(3)(97 mod 13) mod 13
And continue the pattern to obtain:
c = (3)(3)(3)(95 mod 13) mod 13
c = (3)(3)(3)(3)(93 mod 13) mod 13
c = (3)(3)(3)(3)(3)(91 mod 13) mod 13
c = (3)(3)(3)(3)(3)(9) mod 13
Now we can multiply the factors in any order we wish and each time we get a result greater than 13, we can reduce it before proceeding further. For simplicity, we'll just proceed from left to right:
c = (9)(3)(3)(3)(9) mod 13
c = (27 mod 13)(3)(3)(9) mod 13
c = (1)(3)(3)(9) mod 13
c = (81) mod 13
c = 3
While this is already a major improvement compared to performing the full exponentiation first, the number of multiplications we will have to perform is still on the order of whatever our exponent is, although each such multiplication is very tightly constrained. Next we will refine this approach so that the number of multiplications that must be performed will only be on the order of the logarithm of the exponent.
Our next improvement is made possible by noting the following:
c = ab mod n = ((a2)b/2)(ab mod 2) mod n
The division in the above expression is integer division, which means that the result is the largest integer that is not larger than b - this is also known as the floor function. Using our example again:
c = 911 mod n 9((2)(5)+1) mod n = ((a2)5) (a1) mod n
However, we can repeat this procedure (many times if necessary) until the only exponents left in our expression are 1 and/or 2:
c = 911 mod n = [((a2)2)2)] [(a2)] [(a1)] mod n
To evaluate (((a2)2)2), we simply square a, reduce the result, square it again, reduce the result, square it again, and perform a final reduction.
[(((a2)2)2)] mod 13 = (((92)2)2) mod 13 = ((32)2) mod 13 = (92) mod 13 = 3
Once we have done this for the factor that represents the largest power of a, we will already know all of the other factors since they were computed as intermediate steps in finding the largest one. Now we only have to multiply the relevant factors together and reduce the final result.
c = 911 mod n = [((a2)2)2)] [(a2)] [(a)] mod n = [3][3][9] mod n = 81 mod n = 3
Finally, notice that the bookkeeping can be significantly streamlined by noting the relationship between which powers are needed and the binary representation of the original exponent:
11 = 10112 = (1)8 + (0)4 + (1)2 + (1)1 = 8 + 2 + 1
Hence
911 = 9(8+2+1) = (98)(92)(91)
To evaluate this, we will perform the square and reduce technique to evaluate the first power, making note of the value of the smaller powers along the way. Then, at whatever and however many points are convenient, we will multiply the factors.
The power (no pun intended) of this technique really can't be overstated. Even with the benefit of such a powerful algorithm, performing modulo-n exponentiation with thousand digit integers is very computationally expensive. Without it, or a similarly efficient algorithm, it would simply not be possible.
we are interested and discovering ways to exploit the behavior of modular arithmetic at a much earlier stage.
In the section above, Modular Multiplication Using Intermediate Modulo-n Reductions, the following claim was made: "More to the point, we can reduce any part of the expression at any time that it is useful to do so."
While technically a true statement, it is incomplete and a bit misleading. The impression is that any such reductions would be done modulo-n where n is the modulus of the entire expression. But if this were true, then
an
a0
1 (mod n)
However, it is trivial to construct a counter example showing that this is not the case.
23
8
2 (mod 3)
Exponents can, indeed, be reduced at any time, but they must be reduced by a different modulus. While that modulus is determined by the value of n, it is not equal to it.
First, let's establish some of the basics. We know that
1
a0 (mod n)
What if there is another value, m, such that we have the same result
1
am (mod n)
Assuming that such a value exists, it would also be true that, for any integer k,
1
akm (mod n)
since this can be written as
1
(am)k
1k (mod n)
Similarly,
ab
akm+b
(mod n)
since this can be written as
ab
akm+b
(akm)(ab) (mod n)
The conclusion from this is that, if such a value of m can be found, the exponent in a modulo-n expression can be reduced modulo-m.
Thus, for an arbitrary exponent e, we have
ae
ae mod m
(mod n)
The task now is, given a value of n, how do we find m - noting that we are still assuming that such a value exists.
The value of m can be found using Euler's Totient Theorem, which states that, for any positive integer n, that
1
a
(n)
(mod n)
for all integers a that are relatively prime to n. Note that this last requirement, though subtle and frequently forgotten, is critically important.
The function (n) is
Euler's totient function and is defined
as the number of positive integers less than and relatively prime to n.
Hence,
ae
ae mod
(n)
(mod n)
If the modulus for the expression is rich in factors, then the totient can be considerably smaller than n. That can significantly simply calculations. For instance, consider
c = 727 mod 30
The totient of 30 is only 8, so this reduces to
c = 73 mod 30
c = (49)(7) mod 30
c = (19)(7) mod 30
c = (133) mod 30
c = 13