2 ms·
so at what point does a quantum computer's ability to factor large number threaten RSA (since RSA relies on prime factorization being extremely cpu intensive)?
by viggity 9y ago
so at what point does a quantum computer's ability to factor large number threaten RSA (since RSA relies on prime factorization being extremely cpu intensive)?
- VikingCoder 9y agoWell, at a guess, you need at least as many qubits as there are bits in your key?
- ianai 9y agoFor at least one quantum computer you would need a way to encode the number in the qbit states as well as the algorithm, I think. It seems like something that may require a specially engineered quantum computer.
- vtomole 9y agoThat is not how Shor's algorithm works. To factor a number N, Shor's algorithm uses a classical computer to pick a random number a where a < N. A quantum computer is used to find the period of f(x) = a^x mod N. This Wikipedia entry [0] provides a good overview. [0]: https://en.wikipedia.org/wiki/Shor%27s_algorithm#Classical_part https://en.wikipedia.org/wiki/Shor%27s_algorithm#Classical_p...