Concepts6

The discrete logarithm problem asks for x such that g^x ≡ h (mod p) in a multiplicative group modulo a prime p.

Miller–Rabin is a fast primality test that uses modular exponentiation to detect compositeness with very high reliability.

A quadratic residue modulo an odd prime p is any a for which x^2 ≡ a (mod p) has a solution; exactly half of the nonzero classes are residues.

Euler’s Theorem says that if a and n are coprime, then a raised to the power φ(n) is congruent to 1 modulo n.

Fast exponentiation (binary exponentiation) computes a^n using repeated squaring in O(log n) multiplications.

Prime factorization expresses any integer greater than 1 as a product of primes raised to powers, uniquely up to ordering.