Mathematical Foundations Summary

Cryptography · Axiom Academy

SUMMARY Mathematical Foundations Summary Key takeaways from the Mathematical Foundations unit in cryptography. Clock Math: Numbers wrap around after reaching the modulus (e.g., 15 mod 12 = 3) Finite Sets: All operations stay within a bounded set Z n = 0, 1, 2, ..., n-1 Wrapping Behavior: Enables periodic patterns crucial for encryption cycles Notation: a ≡ b (mod n) means n divides (a - b) GCD & Extended Euclidean Algorithm GCD: Greatest common divisor of two integers; found efficiently via Euclidean algorithm Extended Euclidean: Finds coefficients x, y where ax + by = gcd(a, b) Bézout Coefficients: These coefficients are essential for computing modular inverses Efficiency: Runs in O(log n) time, making it practical for large numbers Existence: a -1 (mod n) exists if and only if gcd(a, n) = 1 (coprime) Extended Euclidean Method: Directly computes the inverse from Bézout coefficients Fermat's Method: For prime p : a -1 ≡ a p-2 (mod p) Euler's Method: For general n : a -1 ≡ a φ(n)-1 (mod n) Definition: φ(n) counts integers from 1 to n that are coprime to n Prime Power: φ(p k ) = p k - p k-1 = p k-1 (p - 1) Multiplicative: If gcd(m, n) = 1, then φ(mn) = φ(m) × φ(n) RSA Crucial: φ(n) determines the size of the group used in RSA encryption Fermat's Little Theorem: If p is prime and gcd(a, p) = 1, then a p-1 ≡ 1 (mod p) Euler's Theorem: Generalization: If gcd(a, n) = 1, then a φ(n) ≡ 1 (mod n) Modular Exponentiation: Enables fast computation of large powers using repeated squaring

This is the written version of the interactive lesson above. See the full Cryptography course.