Accepts decimal, hex (0x...), or binary (0b...). Negative allowed.
Negative exponent uses modular inverse when gcd(a, m) = 1.
Must be positive. Very large values supported via BigInt.
Provide pairwise coprime factors whose product equals m. Typically primes.
Result
Value:
—
dec
Raw (decimal): —
Bit length: — bits
Time: — ms
Steps: —
Inverse used
gcd(a, m) = 1
Montgomery used
CRT used
Exponentiation by Squaring — Step Table
| # | Exponent bit | a2^k mod m | Result after step |
|---|
Steps are omitted when CRT or Montgomery mode is enabled.
Example Data
Click a row to load inputs. Results populate automatically.
| # | a (base) | e (exponent) | m (modulus) | Result a^e mod m |
|---|
Formula Used
We compute a^e mod m via one of three methods:
- Basic: Exponentiation by squaring with repeated squaring and multiply when the bit is 1.
- Montgomery: Uses Montgomery reduction in a transformed domain for faster modular multiplies when m is odd.
- CRT: If factors of m are provided and pairwise coprime, compute residues modulo each factor and reconstruct with the Chinese remainder theorem.
// Basic (non-negative e) res := 1; b := a mod m while e > 0: if e odd: res := (res · b) mod m b := (b · b) mod m e := floor(e/2) // Negative e: use inverse if gcd(a, m)=1, then raise to |e|
CRT reconstruction (pairwise coprime factors m_i) uses an iterative form of Garner’s algorithm to combine residues into the unique solution modulo m.
How to Use
- Enter a (base), e (exponent), and positive m (modulus). Prefix 0x for hex or 0b for binary.
- Enable Montgomery for big odd moduli to accelerate multiplies.
- Enable CRT only if you know coprime factors of m; enter them comma‑separated. We validate their product equals m.
- For negative exponents, keep “Handle negative exponents” enabled; it uses a modular inverse of a modulo m.
- Choose the output format: decimal, hex, or binary. Copy, share, or export results and steps.
FAQs
The calculator uses browser-native BigInt, enabling extremely large integers limited primarily by memory and your browser. There’s no fixed digit cap for inputs or modulus.
A negative exponent needs the modular inverse of a. The inverse exists iff a and m are coprime. Otherwise, modular division is undefined and we report an error.
Yes, if the factors are known and balanced in size. We exponentiate modulo each factor and reconstruct, typically reducing operand sizes and improving performance for large semiprimes.
When the modulus is odd and multiplications dominate runtime, Montgomery reduction speeds up repeated multiplies. It is standard in cryptographic implementations.
Yes. Each residue computation mod m_i can use Montgomery if m_i is odd. The tool will automatically use Montgomery per factor when enabled.
No. Factoring large integers is hard. Provide the factors yourself to use CRT; otherwise the basic or Montgomery method is used directly modulo m.
Yes. CSV export includes the step table for the basic method. PDF export includes inputs, result summary, and steps when available.