Linked from

The 25 pages that link to RSA cryptosystem, each with the reason it gives.

• Prime factorizationRelated: Factoring the public modulus into its two prime factors would compromise its private key.

• Greatest common divisorRelated: RSA key generation uses coprimality and modular inverses.

• Euclidean algorithmRelated: RSA key generation uses gcd computations to test whether exponents are coprime.

• Chinese remainder theoremRelated: Implementations use the theorem to speed up private-key exponentiation.

• Fermat's little theoremRelated: Fermat's theorem helps explain exponent identities used in RSA, though Euler's theorem is more general.

• Integer factorizationRelated: Factoring the public modulus can reveal the prime factors used to construct an RSA key.

• Congruence (number theory)Related: Its operations encode messages as residues and use congruences to recover them.

• Coprime integersRelated: RSA chooses an exponent coprime to the totient of its modulus so decryption can invert it.

• Digital signatureRelated: RSA can support signatures, though its assumptions and operation differ from elliptic-curve schemes.

• Primality testRelated: Generating RSA keys requires finding large primes efficiently.

• Composite numberRelated: RSA public keys are built from products of large prime numbers.

• Shor's algorithmRelated: A sufficiently capable quantum computer could factor RSA moduli using Shor's algorithm.

• Unique factorizationRelated: Its keys are built from prime factors of a large composite integer.

• Extended Euclidean algorithmRelated: RSA key generation uses the algorithm to find a modular inverse for the private exponent.

• Adi ShamirRelated: Shamir co-invented RSA with Ronald Rivest and Leonard Adleman.