Modular exponentiation facts for kids

Modular exponentiation is about finding the value of the equation c = b^e mod m. This is the remainder when dividing b^e by m. It is the inverse function of the discrete logarithm. Because modular exponentiation is easy and fast, and finding the discrete logarithm is difficult, both are used in fields such as public-key cryptography.

Right-to-left binary method

When dealing with very large whole numbers, directly finding the result can be very resource intensive. We can make some optimisations to save computation power with principles like exponention by squaring.

Let's solve c = b^e mod m:

1. If m is 1, then we know that c must be 0 because every whole number is divisible by 1.
2. Pull the number 1 aside and name it r.
3. Find b mod m and replace b with the result.
4. While e is larger then 0 do the following:
   1. If e is an odd number:
      1. Find $(r * b)\ mod\ m$ and replace r with the result.
   2. Halve e and round it down to the nearest whole number. Then replace e with the result.
   3. Find $b^2\ mod\ m$ and replace b with the result.
5. Your answer will now be r.