Post
Topic
Board Development & Technical Discussion
Re: Researcher Claims to Crack RSA-2048 With Quantum Computer
by
j2002ba2
on 05/11/2023, 10:33:30 UTC
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory.

Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits.


This is correct only with ideal noiseless qubits and gates. Shor's algorithm fails when exponentially small noise is present. That is, it needs noise levels of the order 2-n. The same is true for ECDLP. Good luck achieving noise level 2-256.

It is very easy to figure out why that happens. We start with qubits which are independent, each representing only 1 bit of information. But before reaching the final result it is not yet clear which of the 2n possibilities are the correct ones. So midway of the quantum computation, qubits have to represent 22n states at the same time. This enormous amount of information vanishes with any noise present.

Read the last sentence in this section https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_implementation.