Quantum Computing and Public Key Cryptography

---

In 1994, Peter Shor developed a quantum algorithm called Shor’s algorithm that provides an efficient solution to the factoring problem.

• given a large enough quantum computer, can solve the problem
• thus RSA can be broken by factoring the modulus
  • RSA modulus is an integer where and are prime
• Quantum algorithms can efficiently solve the discrete logarithm problem, including the EC version
  • thus most public key algorithms would be broken in a post-quantum world
• there are several viable post-quantum cryptosystems that are secure
  • NTRU is a post-quantum public key algorithm
    • is based on the mathematical problem of finding the shortest vector in a lattice
    • currently there is no efficient quantum algorithm to solve this