- Overview
- Modular Multiplication Using Intermediate Modulo-n Reductions
- Square and Multiply Technique
- Modular Reduction of the Exponent - The totient

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*, *a*^{b} is defined as that number *c* such that

c = a^{b} mod n

As with modular arithmetic in general, we could simply evaluate *a ^{b}*
in the domain of all integers and then reduce the result modulo-

c = 9^{11} 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 9^{11} as 3.138x10^{10}
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 n^{2}. This means that we can
evaluate the above expression, 9^{11} 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 = a^{b} = (a^{2})(a^{b-2})

which means that

c = a^{b} mod n = (a^{2} mod n)(a^{b-2}
mod n) mod n

The value *a*^{2} will always be less than *n*^{2}
and we can use this same property to break *a*^{b-2} into smaller
pieces before evaluating them. We would continue until our second factor has an
exponent of 2 or less.

For example:

c = 9^{11} mod 13 = (9^{2} mod 13)(9^{9}
mod 13) mod 13

c = (81 mod 13)(9^{9} mod 13) mod 13

c = (3)(9^{9} mod 13) mod 13

c = (3)((9^{2} mod 13)(9^{7} mod 13)) mod 13

But since we have already evaluated (9^{2} mod 13), we can quickly
proceed to

c = (3)(3)(9^{7} mod 13) mod 13

And continue the pattern to obtain:

c = (3)(3)(3)(9^{5} mod 13) mod 13

c = (3)(3)(3)(3)(9^{3} mod 13) mod 13

c = (3)(3)(3)(3)(3)(9^{1} 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 = a^{b} mod n = ((a^{2})^{b/2})(a^{b
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 = 9^{11} mod n 9^{((2)(5)+1)} mod n = ((a^{2})^{5})
(a^{1}) 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 = 9^{11} mod n = [((a^{2})^{2})^{2})]
[(a^{2})] [(a^{1})] mod n

To evaluate (((a^{2})^{2})^{2}), we simply square *
a*, reduce the result, square it again, reduce the result, square it again,
and perform a final reduction.

[(((a^{2})^{2})^{2})] mod 13 = (((9^{2})^{2})^{2})
mod 13 = ((3^{2})^{2}) mod 13 = (9^{2}) 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 = 9^{11} mod n = [((a^{2})^{2})^{2})]
[(a^{2})] [(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 = 1011_{2} = (1)8 + (0)4 + (1)2 + (1)1 = 8 + 2 + 1

Hence

9^{11} = 9^{(8+2+1)} = (9^{8})(9^{2})(9^{1})

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

a^{n}
a^{0}
1 (mod n)

However, it is trivial to construct a counter example showing that this is not the case.

2^{3}
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
a^{0} (mod n)

What if there is another value, *m,* such that we have the same result

1
a^{m} (mod n)

Assuming that such a value exists, it would also be true that, for any
integer *k*,

1
a^{km} (mod n)

since this can be written as

1
(a^{m})^{k}
1^{k} (mod n)

Similarly,

a^{b}
a^{km+b}
(mod n)

since this can be written as

a^{b}
a^{km+b}
(a^{km})(a^{b}) (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

a^{e}
a^{e 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,

a^{e}
a^{e 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 = 7^{27} mod 30

The totient of 30 is only 8, so this reduces to

c = 7^{3} mod 30

c = (49)(7) mod 30

c = (19)(7) mod 30

c = (133) mod 30

c = 13