Repository files navigation

Modular exponentiation is used in public key cryptography.

It involves computingb to the powere (modm):

c ←b^e (modm)

You could brute-force this problem by multiplyingb by itselfe - 1 times, but it is important to havefast (efficient) algorithms for this process.

In cryptography, the numbers involved are usually very large. Without an efficient algorithm, the process would take too long.

This article is educational - it is a summary of what I have learned about the process of modular exponentiation, with a few code implementations of a possible algorithm rather than a presentation of the most efficient methods.

THe most basic approach would be to multiplyb by itselfe - 1 times, and performing floor division on the result to obtain the result modulom (which will be the remainder or residue of floor division of the result by the modulus). There are a few problems with this approach:

1. Ifb ande are large numbers,b^e will be enormous - which causes problems representing the resultant data as a native type in many languages/systems.
2. Ifb ande are large, a lot of multiplications are required. The universe might not last long enough for us to carry out the computation…

For multiplication (modm) congruence is maintained. In other words:

if a ≡ x (mod m) then a ∙ k ≡ x (mod m)

It follows that if we're just concerned with congruences (i.e. the residue mod m), multiplying the congruences provides the same result as multiplying the factors and then taking the result modulo m:

If a ∙ a ≡ x (mod m), then a (mod m) ∙ a (mod m) ≡ x (mod m)

In terms of an exponentiation algorithm, multiplying the result modulom at each step leads to much smaller numbers which spares computational resources.

Forc ←b^e (modm)

Start with 1, multiply byb, take the result mod(m), repeate times.

In other words:

1. Start withc ← 1
2. Repeate times:c ←c ∙b modm

Ifc ←b^e (modm) and

e = 2^k

We can computec using the "squares" method - this allows for fast computation of large positive integer powers of a number.

From rules of indices:

(b^e)^f = b^ef

For example, this allows a⁸, can be represented as ((a²)²)².

If you calculate a⁸ naively:

a⁸ = a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a

...7 multiplications are required (the exponent - 1).

Alternatively, computinga⁸ as((a²)²)² requires three multiplications:

• a ∙ a = s₁
• s₁ ∙ s₁ = s₂, where s₂ is equivalent to (a²)²
• s₂ ∙ s₂ = s₃, where s₃ is equivalent to ((a²)²)²

In this way,aⁿ requires no more than 2 log₂(e) multiplications, wheree is the exponent.

So long as our exponent is a power of 2, and we multiply congruences at each stage, we have an efficient algorithm that can be converted to code:

#!/usr/bin/env python3defexponent_power_of_2(a,e_power2,mod):foriinrange (0,e_power2):a= (a*a)%modreturna

The previous algorithm gets us on the right track, but it has a major limitation - it only works if the exponent is a power of two.

We can however take the principle and generalise it so that it works for any number.

The idea is to take any number represented as the summation of powers of two - which as luck would have it, is exactly the way that modern computers represent numbers - and to create a running total of the required squares.

Example:

a¹¹ = a⁸ ∙ a² ∙ a¹

...Notice that 8, 2 and one are powers of 2 (3, 1 and 0 respectively).

We can get the answer by working through each power of two up to the maximum possible given the size of e, squaring the base at each stage and only adding the squares to the result if the given power of two is a factor in the exponent.

Given a baseb, an exponente and modulom, compute b^e (mod m):

1. Create an integer (or long) variable calledresult and set this result equal to 1.
2. Check the least significant bit (2⁰) of the exponent e. If it is 1, setresult equal tobase.
3. Check each bit in the exponent by iteratively bitshifting and masking against 1 - this checks each position in order, starting from the second-least-significant bit (we have already considered the least significant bit in stage 2.
4. Start a loop
5. At each iteration, setbase equal to the value of the previousbase squared, modulom
6. At each stage, if the LSB ofe is set, setresult equal to the product of the previousresult and the currentbase (which is the previous base squared, as described in stage 3), all modulom
7. When the value ofe is NULL, end the loop
8. The value of result is the product of all b to the power of two for all powers of two that constitute the exponent.

In summary, set the result to be 1. Starting from the least significant bit of the exponent, iteratively check each bit - which denotes that the particular power of two is a component of the exponent. Square the base modulo m at each stage. If the exponent bit is set, multiply the base with the current result, modulo m. The final result is the base raised to the exponent mod m - the product of a set of base raised to exponents that constitute the original exponent broken into powers of two.

Fast modular exponentiation can be carried out recursively based on the fact that:

• a^e = a^e/2 x a^e/2 (when e is even) and
• a^e = a^{e - 1} * a (when e is not even)

The recursive method breaks the exponentiation down into simpler and simpler computations:

1. Define function modExp(base, exponent, modulus)
2. Set base case - if exponent = 1, return 1
3. If the exponent is even, return square(func(base, exponent / 2, mod)) % mod
4. If the exponent is not even, return (base % mod) * func(base, exponent - 1, mod)

intfastExp(intb,inte,intm){intresult=1;if (1&e)result=b;while (1) {if (!e)break;e >>=1;b= (b*b) %m;if (e&1)result= (result*b) %m;}returnresult;}

defmod_exp2(base,exp,mod):ifexp==0:return1ifexp&1==0:r=mod_exp(base,exp/2,mod)return (r*r)%modelse:return (base%mod*mod_exp(base,exp-1,mod))%mod

This repo contains working code for fast modular exponentiation in:

• C
• C++
• Python

• Modular Arithmetic, Khan Academy, with practice quizzes
• Intro to modular exponentiation, You Tube, Mark's Education Tutorials
• Modular Exponentiation Made Easy, Randall Heyman YouTube
• Good description, with a recursive example in C
• Video describing the recursive algorithm