About This Calculator

1. What is this calculator for?
2. Can I embed this on my website?
3. How does modular exponentiation work?

What is this calculator for?

This calculator performs modular exponentiation. It calculates the result of a base number raised to an exponent, then divided by a modulus, returning the remainder.

Can I embed this on my website?

Yes, you can embed this calculator on your website. Here's the embed code:

<iframe width="415" height="220" src="http://www.a-calculator.com/modular-exponentiation/embed.html" frameborder="0" allowtransparency="true"></iframe>

How does modular exponentiation work?

Modular exponentiation is the operation of finding the remainder when a base number is raised to an exponent, then divided by a modulus. It is efficiently computed using the "Square-and-Multiply" algorithm, also known as "Exponentiation by Squaring". Here's how the algorithm works:

1. Initialization: Set the result \(r = 1\) (the identity element for multiplication).
2. Binary Representation: Express the exponent \(n\) in binary form.
3. Iteration: For each bit in the binary representation of \(n\) (starting from the leftmost bit):
   1. Square: Square the current value of \(r\) and take the remainder modulo \(m\), i.e., \(r = (r^2) \mod m\).
   2. Multiply (if needed): If the current bit in the binary representation of \(n\) is 1, multiply \(r\) by \(a\) and take the remainder modulo \(m\), i.e., \(r = (r \cdot a) \mod m\).
4. Result: After processing all bits, \(r\) will contain \(a^n \mod m\).

For example, to calculate \(3^{13} \mod 7\):

1. Initialize \(r = 1\).
2. The binary representation of \(13\) is \(1101\).
3. Iterate through the bits of \(13\):
   1. Bit \(1\): Square \(r = 1^2 = 1\), Multiply \(r = 1 \cdot 3 = 3\).
   2. Bit \(1\): Square \(r = 3^2 = 9 \equiv 2 \mod 7\), Multiply \(r = 2 \cdot 3 = 6\).
   3. Bit \(0\): Square \(r = 6^2 = 36 \equiv 1 \mod 7\).
   4. Bit \(1\): Square \(r = 1^2 = 1\), Multiply \(r = 1 \cdot 3 = 3\).
4. The result is \(3^{13} \mod 7 = 3\).