Modular arithmetic

Modular arithmetic treats integers as equivalent when they have the same remainder after division by a fixed positive integer called the modulus. Its operations use these equivalence classes, so calculations wrap around after reaching the modulus.

Congruence relation: An equivalence relation that groups integers whose difference is divisible by a fixed integer. It defines exactly when two integers count as the same value modulo a modulus.
Integer: A whole number that is zero, positive, or negative. Modular arithmetic is ordinarily defined on integers.
RSA cryptosystem: A public-key cryptosystem whose encryption and decryption rely on exponentiation modulo a product of two primes. RSA uses modular exponentiation to transform messages and recover them with a private key.
Ordinary arithmetic: Arithmetic on numbers without identifying distinct values by a fixed modulus. Unlike ordinary integer arithmetic, modular addition can wrap around to a residue already encountered.
Euclid: An ancient Greek mathematician whose Elements systematized geometry and number theory. The Elements presents foundational results about divisibility and the greatest common divisor.
Equivalence class: A set of elements related to one another by an equivalence relation. Each modular value is a class containing all integers with the same remainder.
Division algorithm: A theorem expressing an integer as a quotient times a positive divisor plus a unique remainder in a fixed range. It guarantees the unique remainders used to describe modular equivalence.
Diffie–Hellman key exchange: A protocol that lets two parties establish a shared secret using exponentiation in a finite group. Its common finite-field implementation performs powers modulo a prime.
Modular arithmetic modulo a prime: Modular arithmetic whose modulus is prime, making its residue classes a finite field. Prime moduli allow division by every nonzero residue, unlike composite moduli.
Sunzi Suanjing: A Chinese mathematical text, probably compiled between the third and fifth centuries, containing practical arithmetic problems. It includes an early problem now recognized as an instance of the Chinese remainder theorem.

Linked from 62 pages