Modular Arithmetic
Modular arithmetic takes remainders after integer operations, keeping results within [0, n); it is the foundation of number theory and cryptography.
Purpose
To keep operations closed within a finite range, the basis of RSA, Diffie-Hellman, and other cryptography.
Mechanism
(a + b) mod n and (a × b) mod n are defined under modulus n. The modular inverse a^(-1) satisfies a·a^(-1) ≡ 1 (mod n); it exists when gcd(a,n)=1 and is found with the extended Euclidean algorithm. Fermat's little theorem: a^(p-1) ≡ 1 (mod p) for prime p.
Use cases
- RSA encryption and decryption
- Diffie-Hellman key exchange
- Hash-mod sharding
- Checksum computation
Examples
- Input
(7 + 8) mod 5Output015 mod 5 = 0
Common errors
- Negative modulo behaves differently across languages
- Know your language's behavior or normalize with ((a%n)+n)%n
Related terms
BigInteger
BigInteger is an arbitrary-precision integer type, not limited by a fixed word size, used for computations beyond the native integer range (such as cryptography and combinatorics). GLOSSARY
Prime Number
A prime number is a natural number greater than 1 divisible only by 1 and itself; it is the building block of number theory, and every integer factors uniquely into primes. GLOSSARY
GCD
The GCD (greatest common divisor) is the largest positive integer that divides two or more integers, computed efficiently with the Euclidean algorithm. GLOSSARY