Topic
Number Theory & Cryptography
From prime factors and remainders to coprimality, inverse operations, efficient powers, Euler's theorem, and RSA.
Start Here
- Primes and FactorizationWhy should different ways of breaking a number apart always reach the same prime ingredients? And if those ingredients are unique, why can finding them be difficult? These are separate questions: a theorem can guarantee an answer without supplying a fast way to calculate it.
Go Deeper
- Modular Arithmetic: Numbers on a ClockA clock forgets complete turns. Starting at 10 on a twelve-hour clock and moving forward 5 hours lands at 3: 10+5=15, but 15 and 3 differ by one full turn of 12.
- GCD and the Euclidean AlgorithmImagine cutting two ropes into equal-length pieces without leaving a remainder. The longest possible piece length is their greatest common divisor, abbreviated gcd. For integers, divisors are exact: 6 divides both 48 and 18, and no larger positive integer does.
- Modular Inverses and Extended EuclidAn ordinary reciprocal undoes multiplication: multiplying by 3 and then by 1/3 returns the starting value. Modulo n, we need an integer that undoes multiplication up to a remainder.
- Fast Modular Powers: Repeated SquaringComputing 13²⁷ as an ordinary integer creates a large number only to discard almost all of it when taking a remainder. Repeated squaring keeps the part we need at every step.
- Euler's Totient and TheoremMultiplication modulo n sometimes loses information. Multiplication by a number coprime to n does the opposite: it rearranges all the invertible residues without merging any. Euler's theorem is a consequence of that rearrangement.
- RSA from First PrinciplesA public-key system lets anyone encrypt for a recipient while only the recipient can decrypt. RSA builds that separation from a modulus whose prime factors the owner knows. The mathematics is a reversible operation with a secret shortcut; a secure encryption scheme needs additional encoding and protocol rules.