🔁 Modular Arithmetic Calculator
7¹²⁸ mod 13 in seven squarings, not 128 multiplications — with the square-and-multiply table shown. Plus modular inverses (17⁻¹ mod 43) via extended Euclid, step by step.
7^128 mod 13 = 3
| Exponent bit | Operation | Accumulator (mod 13) |
|---|---|---|
| 1 | start: acc = base (bit 1) | 7 |
| 0 | square | 10 |
| 0 | square | 9 |
| 0 | square | 3 |
| 0 | square | 9 |
| 0 | square | 3 |
| 0 | square | 9 |
| 0 | square | 3 |
Square-and-multiply reads the exponent in binary (10000000) — 8 steps instead of 128 multiplications. This is the same algorithm inside RSA and Diffie–Hellman.
Exact BigInt arithmetic with the full algorithm trace — the working your cryptography or number-theory course wants to see. Runs locally.
How the modular arithmetic calculator works
The power tab computes aᵇ mod n by square-and-multiply: read the exponent in binary, square the accumulator for each bit and multiply by the base when the bit is 1 — turning 128 multiplications into 8 steps, each shown in a trace table with the bit, the operation and the accumulator. The inverse tab runs the extended Euclidean algorithm on (a, n), displaying the full quotient/remainder table; when gcd(a, n) = 1 the back-substituted coefficient is the inverse, verified on-page (a × a⁻¹ ≡ 1 mod n), and when the gcd isn't 1 the tool explains why no inverse exists. Both run on exact BigInt, comfortably handling the 20-digit values cryptography homework throws around.
These two algorithms are the beating heart of public-key cryptography: RSA encryption is literally a^e mod n by square-and-multiply, and the RSA private key is a modular inverse computed by extended Euclid. They're also precisely the computations language models fumble most confidently — modular exponentiation answers from chatbots are wrong so often that "verify with a real calculator" is standard advice in CS courses. This is that real calculator, with the working your assignment wants.
Frequently asked questions
What does aᵇ mod n mean?
The remainder when aᵇ is divided by n. The trick is that you never need the astronomically large aᵇ itself — reducing mod n after every multiplication keeps numbers small, and square-and-multiply keeps the multiplication count logarithmic in b.
How does square-and-multiply work?
Write the exponent in binary. Scan its bits left to right: square the accumulator each bit, and additionally multiply by the base when the bit is 1. For b = 128 (binary 10000000) that's 7 squarings after the initial step — the table shows every one.
What is a modular inverse?
The number x with a·x ≡ 1 (mod n) — division's stand-in in modular arithmetic. It exists exactly when gcd(a, n) = 1, and the extended Euclidean algorithm finds it; 17⁻¹ mod 43 is 38, since 17 × 38 = 646 = 15 × 43 + 1.
Why does my inverse not exist?
Because a and n share a factor. If gcd(a, n) = g > 1, then a·x mod n is always a multiple of g and can never be 1. The tool shows the gcd from the Euclid table so you can see the blocking factor.
What is this used for outside homework?
RSA and Diffie–Hellman key exchange (modular powers), RSA key generation (modular inverse), hashing and checksums, cyclic schedules, and ISBN/IBAN-style check digits — modular arithmetic is the arithmetic of computing.