Comments by "EebstertheGreat" (@EebstertheGreat) on "How Quantum Computers Break The Internet... Starting Now" video.

  1. Specifically, factoring n is sufficient to crack an RSA-encrypted message, but it is probably not necessary. In addition to n = pq, you are given the exponent e (often chosen to be 3 or 65537) and the encrypted message c = m^e (mod n). You want to compute m, which is the discrete log of c base e (over Z/(nZ)). So you can either factor the semiprime n or find the discrete log of m^e. Both of those are thought to be NP-complete, but neither has even been proven not to be in P. So as far as we know, these might be cracked one day even with conventional computers. And even if it does turn out to be the case that both problems are NP-complete (as suspected), then quantum computers could still crack them in polynomial time (at least in principle), either by factoring n using Shor's algorithm or a similar algorithm or by solving the discrete log problem.
    2