Modular Arithmetic Référence
Référence pour modular arithmetic: operations, inverses, CRT, et applications.
Basic Operations
Modular arithmetic works with equivalence classes modulo n: a ≡ b (mod n) if n divides (a-b). Addition, subtraction, and multiplication are well-defined: (a op b) mod n = ((a mod n) op (b mod n)) mod n. Division requires modular inverse: a^(-1) mod n exists iff gcd(a,n) = 1, computed via extended Euclidean algorithm. Exponentiation uses fast powering (square-and-multiply) in O(log e) multiplications. Fermat's little theorem provides a shortcut: a^(-1) ≡ a^(p-2) mod p for prime p.
- add/mul
- Well-defined mod n
- inverse
- Extended Euclid
- fast exp
- Square-and-multiply
reduce after opgcd(a,n)=1O(log e)Chinese Remainder Theorem
The CRT states that if moduli n1,...,nk are pairwise coprime, the system x ≡ ai (mod ni) has a unique solution mod N = n1*...*nk. The solution is x = sum(ai * Mi * yi) mod N where Mi = N/ni and yi = Mi^(-1) mod ni. CRT enables RSA decryption optimization (compute mod p and mod q separately, then combine). CRT representation accelerates modular exponentiation by working with smaller moduli. The Garner algorithm efficiently converts CRT representation to standard form. CRT is fundamental to many cryptographic optimizations.
- CRT
- Simultaneous congruences
- RSA speedup
- Decrypt mod p and q
- Garner
- CRT to standard
pairwise coprimethen combineefficient conversion