A public-key cryptography algorithm which uses prime factorization as the trapdoor one-way function. Define n congruent p q for p and q primes. Also define a private key d and a public key e such that d e congruent 1 (mod ϕ(n)) (e, ϕ(n)) = 1, where ϕ(n) is the totient function, (a, b) denotes the greatest common divisor (so (a, b) = 1 means that a and b are relatively prime), and a congruent b (mod m) is a congruence. Let the message be converted to a number M. The sender then makes n and e public and sends E = M^e (mod n).

congruence | public-key cryptography | RSA number