Course contentsShow
← Computer Science
Lesson 2406 of 2,87254. Cryptography FundamentalsFree lesson

Mathematical Foundations: Modular Arithmetic

Core mathematical operations including modular exponentiation that enable asymmetric algorithms.

Mathematical Foundations: Modular Arithmetic

You'll learn the clock-like arithmetic that powers RSA and other asymmetric encryption systems.

The Clock Face Model

Imagine a 12-hour clock. When you add 10 hours to 5 o'clock, you don't get 15 o'clock—you wrap around to 3 o'clock. This "wrapping" behavior is modular arithmetic, and it's fundamental to public key cryptography.

In modular arithmetic, we work with remainders. When we say 17 mod 12, we're asking "what's the remainder when 17 is divided by 12?" The answer is 5, because 17 = (1 × 12) + 5.

Why It Matters for Cryptography

Modular arithmetic creates one-way mathematical operations that are easy to compute forward but hard to reverse without special information. This asymmetry is the foundation of public key systems like RSA.

Core Operations

  • Addition mod n: (a + b) mod n wraps around at n
  • Multiplication mod n: (a × b) mod n also wraps around
  • Modular exponentiation: (base^exponent) mod n raises to a power, then takes the remainder

That last operation—modular exponentiation—is the workhorse of asymmetric algorithms. Computing 7^1000000 mod 13 is fast with special techniques, but reversing it (finding the exponent given only the result) is extremely difficult without knowing secret information.

The Security Foundation

The difficulty of certain modular arithmetic problems (like factoring large numbers or computing discrete logarithms) creates the mathematical "trapdoor" that lets you publish an encryption key while keeping the decryption key secret.

Key Takeaway: Modular arithmetic provides the mathematical foundation for asymmetric cryptography by creating operations that are computationally easy in one direction but practically impossible to reverse without secret information.