Modular Exponentiation Fast Power Calculator

Compute a^e mod m

How it works

This tool computes a^e mod m using fast power. In auto mode it selects the best available big integer engine. The trace uses the right-to-left method which squares the base each iteration and multiplies into the result when the current exponent bit is one.

while e > 0:
    if e is odd: result = (result * base) mod m
    base = (base * base) mod m
    e = floor(e / 2)

FAQs

It requires three non negative integers: a base a an exponent and a modulus greater than zero. The output is the remainder of dividing a raised to e by m.

It uses binary fast power also known as exponentiation by squaring. Auto mode chooses GMP first then BCMath then native integers based on availability to support very large inputs.

With big integer libraries inputs can be thousands of bits long. Without them the values must fit safely within native integer limits otherwise you will see a warning asking to use a big integer mode.

Step tracing shows the internal state each loop including the current exponent bit the result accumulator and the base after squaring. It helps verify correctness and is useful for learning and audits.

Choose BCMath or GMP explicitly if you know your server supports it and you want consistent behavior. Use native integers only for smaller values that comfortably fit within machine limits.

This tool assumes non negative exponents. For negative exponents you would first compute a modular inverse of the base when it exists and then raise it to the absolute exponent.

Fast power reduces multiplications to logarithmic in the exponent and applies the modulus after each multiply and square which keeps numbers small and avoids overflow and memory blowups.

The mathematics is standard but side channel resistance depends on implementation details like constant time operations. This educational tool focuses on correctness and transparency rather than hardened side channel defenses.

Compute ae mod m

How it works

FAQs

1) What inputs does modular exponentiation require?

2) Which algorithm does this calculator use?

3) How large can the numbers be?

4) What is the purpose of step tracing?

5) When should I pick a specific method instead of auto?

6) Does this compute negative exponents or modular inverses?

7) Why is performance so much better than naive power then modulo?

8) Is the method safe for cryptographic use?

Related Calculators

Compute a^e mod m