Cryptography
RSA Correctness
Decryption recovers the plaintext: m^(ed) ≡ m (mod n) whenever ed ≡ 1 (mod φ(n)).
Diffie–Hellman
Alice and Bob derive the same shared secret g^(ab) from public keys g^a and g^b in any commutative group.
ElGamal Encryption
Decryption recovers plaintext because c2/c1^a = m·g^(ab)/g^(ab) = m in any commutative group.
Modular Exponentiation
Square-and-multiply computes a^n mod m in O(log n) multiplications, agreeing with naive exponentiation.
Miller–Rabin Primality Test
A Fermat witness a^(n-1) ≢ 1 (mod n) certifies compositeness; Carmichael numbers fool every base.
Merkle Tree
A binary hash tree commits to a dataset so that any leaf can be verified with O(log n) hashes.
Digital Signature (Schnorr)
A Schnorr signature (R, s) is valid iff g^s = R · y^c, verified by a single group equation.
One-Way Function
The discrete log f(x) = g^x mod p is easy to evaluate but conjectured hard to invert — a trapdoor that powers public-key cryptography.