Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 40 ยท Math Foundations

Modular Arithmetic

Learn clock arithmetic, congruence, fast modular exponentiation with pow(a, b, m) and modular inverses with pow(a, -1, m), the math under RSA and Diffie-Hellman.

Look at a clock. If it is 10 o'clock now, what time is it five hours later? Not 15, but 3. The numbers wrap around after 12. This wrap-around arithmetic is called modular arithmetic, and it is the mathematical engine behind almost all public-key cryptography. RSA, Diffie-Hellman, elliptic curves and many hash-based tricks all work with numbers that wrap around a fixed modulus.

Why does cryptography love wrap-around? Because it produces operations that are easy to perform in one direction and, for large numbers, very hard to undo. Raising a number to a power modulo a large prime takes microseconds, while recovering the exponent from the result is believed to be infeasible. You will see exactly where in later lessons; this one gives you the vocabulary and the Python tools.

The remainder operator

Python's % operator gives the remainder after division. In a % m, the number m is the modulus, and the result is always between 0 and m - 1 when m is positive.

Python Clock arithmetic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice -3 % 12 == 9. In many languages (C, Java) the remainder of a negative number is negative, but Python always returns a result with the sign of the modulus, which is what mathematicians expect. If you port code, check this carefully, because it is a classic source of bugs.

Congruence

Two numbers are congruent modulo m if they leave the same remainder when divided by m. Mathematicians write this with three bars: a โ‰ก b (mod m). Equivalently, m divides the difference a - b.

So 17 โ‰ก 5 (mod 12), because both are 5 on a clock, and also 17 - 5 = 12. Every integer belongs to exactly one of m groups, called residues: 0, 1, ..., m - 1. Arithmetic modulo m is just ordinary arithmetic where you only care about the residue.

Python Congruence in code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Working modulo m

The powerful fact is that you may reduce at any point of a calculation and the answer does not change. For addition, subtraction and multiplication:

  • (a + b) mod m = ((a mod m) + (b mod m)) mod m
  • (a - b) mod m = ((a mod m) - (b mod m)) mod m
  • (a ร— b) mod m = ((a mod m) ร— (b mod m)) mod m

This is what keeps numbers small. When a computation involves 2048-bit values, you never want intermediate results to grow to 4096 bits and beyond; you reduce after each step.

Division is the odd one out. You cannot simply divide residues: modulo 8, the numbers 6 and 14 are congruent, but 6 / 2 = 3 and 14 / 2 = 7 are not. Instead, division means multiplying by an inverse, covered below.

Python Reduce early, same answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the table for modulo 7. Every non-zero row is a permutation of 0 to 6: each row contains each residue exactly once. This only happens when the modulus is prime, and it is the reason cryptographers love prime moduli (you will see more in primes and primality testing).

flowchart LR
    A["Large calculation<br/>e.g. a * b * c"] --> B["Reduce mod m<br/>after every step"]
    B --> C["Small numbers<br/>(always below m)"]
    C --> D["Same final residue<br/>as the huge number"]

Reducing early keeps numbers small without changing the result.

Fast modular exponentiation

Computing a**b % m for huge numbers is a core operation in cryptography. Doing a**b first and then taking % is hopeless when b has hundreds of digits: the intermediate number would have more digits than there are atoms in the universe. Python's three-argument pow(a, b, m) uses square-and-multiply, which reduces after every step and needs only about as many multiplications as b has bits.

Python pow with three arguments

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The hand-written version walks through the bits of the exponent: squaring at each bit and multiplying when the bit is 1. For a 2048-bit exponent that is at most about 4,000 multiplications, each of which is on numbers smaller than the modulus.

One-way in practice

Exponentiation is the "easy direction". The reverse question, given g, p and y = g^x mod p, find x, is called the discrete logarithm problem. For small numbers you can try every x, but for a 2048-bit prime nobody knows a method fast enough, and the security of Diffie-Hellman rests on that fact.

Python Easy forward, hard backward

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Modular inverses

In ordinary arithmetic the inverse of 5 is 1/5, because 5 ร— (1/5) = 1. In modular arithmetic, the inverse of a modulo m is a number x with a * x โ‰ก 1 (mod m). With an inverse you can "divide": dividing by a means multiplying by x.

An inverse exists only when a and m share no common factor (their greatest common divisor is 1, see GCD and the extended Euclidean algorithm). For a prime modulus, every non-zero residue has one. Since Python 3.8, pow(a, -1, m) computes it directly:

Python Modular inverse with pow(a, -1, m)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The affine cipher at the end is a classical cipher that needs an inverse to decrypt. It uses the multiplier a = 7 because 7 is coprime to 26; a multiplier like 4 or 13 would lose information, as two letters would encrypt to the same one.

Tip: Never compute a modular inverse by trying every candidate in real code. Use pow(a, -1, m), which is fast even for 4096-bit numbers, and handle the ValueError for the no-inverse case.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is 29 mod 7?

    7 x 4 = 28, and 29 - 28 = 1. So 29 mod 7 = 1.
  2. 2. Why is pow(a, b, m) preferred over (a ** b) % m for large numbers?

    pow with three arguments uses square-and-multiply and reduces modulo m at each step. The result is identical, but the intermediate values stay small.
  3. 3. When does the modular inverse of a modulo m exist?

    An inverse exists exactly when a and m are coprime. Otherwise, a times anything stays a multiple of their common factor and can never equal 1 mod m.
  4. 4. Which problem is believed to be hard for large primes p and is the basis of Diffie-Hellman?

    Exponentiation is fast, but undoing it (the discrete logarithm problem) has no known efficient algorithm for suitably large parameters.

Summary

  • Modular arithmetic wraps numbers around a modulus; in Python a % m gives a residue between 0 and m - 1.
  • You can reduce modulo m at any step of an addition, subtraction or multiplication without changing the result.
  • pow(a, b, m) computes large modular powers quickly using square-and-multiply.
  • The inverse of a mod m exists only if gcd(a, m) = 1, and pow(a, -1, m) computes it; division means multiplying by the inverse.
  • Fast exponentiation versus the hard discrete logarithm is the one-way idea behind Diffie-Hellman.

Next: GCD and the Extended Euclidean Algorithm, where you learn how inverses are really computed.