Home › Calculators › Modular Exponentiation Calculator
Modular Exponentiation Calculator
Calculate a raised to the power b, modulo m, even when the numbers have hundreds of digits. The calculator uses exact BigInt arithmetic and the square-and-multiply method, and lists each step with the binary digits of the exponent.
Last updated:
Whole number, may be negative. Expressions like 2^64 work.
Whole number; negative uses the modular inverse
Whole number ≥ 1, e.g. 1000000007 or 2^127-1
Enter your values to see the result.
Advertisement
Advertisement
How to use the Modular Exponentiation Calculator
- Enter the base a, e.g. a message value in RSA.
- Enter the exponent b; it can be enormous, like 10^18.
- Enter the modulus m, e.g. 3233 or 10^9+7.
- Press Calculate to get a^b mod m.
- Study the table to see each squaring and multiplication.
Worked example: 3^13 mod 7 by square-and-multiply
13 in binary is 1101₂ (8 + 4 + 1). Square the base each step and multiply when the bit is 1, reducing mod 7 every time:
| Bit (right to left) | Base power mod 7 | Bit | Running result |
|---|---|---|---|
| 0 | 3¹ ≡ 3 | 1 | 1 × 3 = 3 |
| 1 | 3² ≡ 9 ≡ 2 | 0 | 3 |
| 2 | 3⁴ ≡ 2² ≡ 4 | 1 | 3 × 4 = 12 ≡ 5 |
| 3 | 3⁸ ≡ 4² = 16 ≡ 2 | 1 | 5 × 2 = 10 ≡ 3 |
So 3^13 mod 7 = 3, found with 3 squarings and 3 multiplications. Check with Fermat’s little theorem: 7 is prime, so 3^13 ≡ 3^(13 mod 6) = 3^1 = 3 ✓.
Useful rules
- Product rule: (x × y) mod m = ((x mod m) × (y mod m)) mod m, which is why reducing at every step is safe.
- Fermat: if p is prime and p does not divide a, a^(p−1) ≡ 1 (mod p), so b can be reduced mod p − 1.
- Euler: more generally, if gcd(a, m) = 1 then a^φ(m) ≡ 1 (mod m), where φ is Euler’s totient.
- Cost: square-and-multiply needs at most 2·log₂(b) modular multiplications, so even a 2048-bit exponent takes only a few thousand steps.
- Common moduli in programming contests are 10^9 + 7 and 998,244,353, both prime.
Frequently asked questions
What is modular exponentiation?
It is computing the remainder when a^b is divided by m, written a^b mod m. For example 3^4 mod 5 = 81 mod 5 = 1. It is a core operation in RSA, Diffie–Hellman, primality tests and hashing.
Why not just compute a^b and then take the remainder?
a^b gets astronomically large: 2^(10^18) has about 3 × 10^17 digits. Reducing mod m after every multiplication keeps every number below m², and the identity (x·y) mod m = ((x mod m)(y mod m)) mod m guarantees the same final answer.
How does square-and-multiply work?
Write b in binary. Repeatedly square the base (a, a², a⁴, a⁸, … all mod m) and multiply into the result the powers whose bit is 1. 3^13 uses 13 = 1101₂, so 3^13 = 3^8 · 3^4 · 3^1. This needs about log₂(b) steps instead of b − 1 multiplications.
How is it used in RSA?
Encryption computes c = m^e mod n and decryption computes m = c^d mod n. With the textbook key n = 3233, e = 17, d = 2753, the message 65 encrypts to 65^17 mod 3233 = 2790, and 2790^2753 mod 3233 gives 65 back.
What does a negative exponent mean in modular arithmetic?
a^(−k) mod m means (a⁻¹)^k mod m, where a⁻¹ is the modular inverse. It exists only when gcd(a, m) = 1. For example 7^(−1) mod 26 = 15, since 7 × 15 = 105 = 4 × 26 + 1.
What is Fermat's little theorem?
If p is prime and a is not a multiple of p, then a^(p − 1) ≡ 1 (mod p). So exponents can be reduced mod p − 1: 3^200 mod 13 = 3^(200 mod 12) mod 13 = 3^8 mod 13 = 9. The calculator shows this shortcut whenever the modulus is prime.
Are all the tools on FreeToolCabin tested for quality and accuracy?
Yes! Every tool on our site undergoes automated Q/A testing in real browser environments to ensure high precision, correct output, and zero errors. If you happen to spot a bug or have a suggestion, please contact us at [email protected] and our team will review it right away.
Related tools
Modular Inverse CalculatorFind a⁻¹ mod m with the extended Euclidean algorithm, step by step, for huge numbers too.Modulo CalculatorCalculate a mod n and the quotient, with floored, truncated and Euclidean rules.Exponent CalculatorRaise any number to a power, including negative and fractional exponents.Big Number CalculatorExact + − × ÷ mod and powers for huge integers with hundreds of digits, plus digit count.Graphing CalculatorPlot multiple functions with zoom, pan, intersections and a value table.Logarithm CalculatorCalculate log in any base, ln, log10, log2 and antilog with change-of-base steps.Quadratic Equation SolverSolve ax² + bx + c = 0 with exact roots, steps, vertex and a parabola graph.Matrix CalculatorAdd, multiply, invert and row-reduce matrices up to 5×5 with exact fractions and steps.Prime Number CheckerCheck if a number is prime, factor it with a factor tree and list primes in a range.GCF and LCM CalculatorFind the GCF and LCM of two or more numbers with Euclid steps and prime factorization.Cubic Yard CalculatorConvert length, width and depth in any unit to cubic yards, cubic feet, m³ and material weight.Factorial CalculatorExact n! up to 5000! with digit count, trailing zeros and double factorial.Prime Factorization CalculatorFind prime factors in exponent form with a factor tree, divisor count and divisors list.Exponential Growth CalculatorExponential growth and decay: final amount, rate or time, discrete or continuous.Linear Regression CalculatorLeast-squares line of best fit: slope, intercept, r, r², predictions and a scatter plot.System of Equations SolverSolve 2×2, 3×3 and 4×4 linear systems with exact fractions and step-by-step working.Cubic Equation SolverSolve ax³ + bx² + cx + d = 0 for real and complex roots with steps and a graph.Summation CalculatorEvaluate sigma notation: sum any expression in n from a to b with partial sums and a chart.Arithmetic Sequence CalculatorFind the n-th term, sum and full list of an arithmetic sequence, or d from two terms.Geometric Sequence CalculatorFind the n-th term, sum and infinite sum of a geometric sequence, or r from two terms.Fibonacci CalculatorExact n-th Fibonacci number (BigInt), sequence lists, Fibonacci check and golden ratio.Factors CalculatorAll factors and factor pairs of a number, prime factors, divisor count and perfect check.Depth of Field CalculatorNear and far focus limits, depth of field and hyperfocal distance for any camera or lens.Crop Factor CalculatorCrop factor, full-frame equivalent focal length and aperture, and field of view for any sensor.Completing the Square CalculatorRewrite ax² + bx + c in vertex form a(x − h)² + k step by step and solve it.Derivative CalculatorSymbolic derivative of any f(x) up to 5th order, with steps, slope at a point and a graph.Exposure Value CalculatorEV from aperture, shutter and ISO, or solve any missing setting with sunny 16 presets.Factoring Trinomials CalculatorFactor trinomials and polynomials: GCF, ac method, difference of squares, cubes, with steps.Integral CalculatorDefinite integral of f(x) from a to b with adaptive Simpson, area graph and antiderivative.Least Common Denominator CalculatorFind the LCD of two or more fractions and rewrite them as equivalent fractions, with steps.Limiting Reactant CalculatorFind the limiting reactant, theoretical yield and leftover excess from an equation.Parabola CalculatorVertex, focus, directrix, axis, intercepts and graph of a parabola from its equation.Polynomial Root FinderFind all real and complex roots of a polynomial up to degree 10, with the factored form.Prime Number List GeneratorList all primes in a range or the first N primes with a fast sieve; copy or download the list.Quadratic Regression CalculatorFit y = ax² + bx + c (or up to degree 6) to x, y data with R², predictions and a graph.Scatter Plot MakerPaste X,Y pairs for a scatter plot with trendline, equation, r and R². Download PNG.Synthetic Division CalculatorDivide polynomials by x − c (synthetic table) or any polynomial (long division) with steps.3D Graphing CalculatorPlot z = f(x, y) surfaces and 3D parametric curves; rotate, zoom, add contours, save PNG.Partial Derivative CalculatorPartial derivatives ∂/∂x, ∂/∂y, second and mixed orders with steps, gradient and Hessian.RREF CalculatorRow reduce any matrix to RREF with exact fractions, every row operation, pivots and rank.Stem and Leaf Plot MakerMake stem-and-leaf plots (standard, split stems or back-to-back) with a key; copy or save PNG.Taylor Series CalculatorTaylor and Maclaurin polynomials of any f(x) to order n, with exact coefficients and a graph.Antilog CalculatorInverse logarithm (antilog) in base 10, e, 2 or any base, with steps and scientific notation.Asymptote CalculatorFind vertical, horizontal and slant asymptotes and holes of a function, with graph and reasoning.Cramer's Rule CalculatorSolve 2x2 and 3x3 linear systems by Cramer's rule with every determinant shown step by step.Dot Plot MakerMake a dot plot or line plot from data or a frequency table; download PNG or SVG.Exponential Regression CalculatorFit y = a·bˣ or y = a·e^(kx) to data with r², predictions, residuals and a plot.Extended Euclidean Algorithm CalculatorFind gcd(a, b) and Bézout coefficients x, y with the full step-by-step division table.Factor Tree GeneratorDraw the prime factor tree of any number as a printable diagram, with exponent form and steps.Function Composition CalculatorFind f(g(x)), g(f(x)), f + g, f · g and f / g with values at a point and domains.X and Y Intercept CalculatorFind the x- and y-intercepts of lines, curves and functions with steps and a graph.Line Intersection CalculatorFind where two lines cross from equations, points or slopes, with parallel checks and a graph.Linear Programming SolverSolve max/min linear programs with the simplex method: tableau steps and a 2-variable graph.Nth Term CalculatorFind the nth term formula of a sequence: arithmetic, geometric, quadratic or cubic.Partial Fraction Decomposition CalculatorSplit a rational function into partial fractions with the setup, equations and solution.Perpendicular Line CalculatorEquation of the perpendicular and parallel line through a point, with distance and a graph.Polar Graphing CalculatorGraph polar equations r = f(θ): roses, cardioids, spirals, with a θ range slider and PNG export.Polynomial CalculatorAdd, subtract, multiply, divide and evaluate polynomials; see roots, degree and a graph.Polynomial Long Division CalculatorDivide polynomials with the full long division layout, quotient, remainder and steps.Scale Factor CalculatorScale factor between similar figures, plus scaled lengths, areas (k²) and volumes (k³).Set CalculatorUnion, intersection, difference and complement of up to 4 sets, with a Venn diagram and counts.Table of Values CalculatorMake an x/y table for any function with a start, end and step, then plot it or copy CSV.Algebra CalculatorSimplify, expand and factor algebraic expressions with exact answers and step-by-step working.Determinant CalculatorDeterminant of a 2×2 to 8×8 matrix with exact fractions and cofactor or row-reduction steps.Differential Equation SolverSolve first- and second-order ODEs step by step, with initial conditions, an RK4 check and a graph.Domain and Range CalculatorFind the domain and range of a function in interval notation, with steps and a graph.Eigenvalue and Eigenvector CalculatorEigenvalues (real or complex), eigenvectors and the characteristic polynomial of a square matrix.Equation SolverSolve any equation for x: exact roots, complex roots, numeric answers, steps and a graph.