3 ms·
I don't believe "quantum computing" will get us any step closer to breaking RSA. Similar how complex number theory didn't allow us to draw a square with area of
by uuidgen 6y ago
I don't believe "quantum computing" will get us any step closer to breaking RSA. Similar how complex number theory didn't allow us to draw a square with area of -1.
To break RSA-N you need a superposition of all the numbers up to 2^N, AFAIK there is even not a hint how to approach it physically.
- danbruc 6y agoA superposition of all n bit integers is no big deal, extracting useful information when performing a measurement is. If you start with a uniform distribution of all n bit integers, you also get each result with equal probability unless you manage to manipulate the system in such a way that the probability of the correct result gets amplified. This is the hard part, finding and implementing operations that selectively boost the probability of the correct result while reducing the probabilities of all other results.
- uuidgen 6y ago> A superposition of all n bit integers is no big deal Is it? How do you do it? The papers I've seen so far shown that given enough measurements we can conclude that the qbits ware in superposition in many cases. I still haven't seen any way to have superposition of all numbers from 0 to 2^n. What you're describing in the rest of your comment is solved by Shor's algorithm. It is quite straight-forward. If we can get the superposition as an input and have working quantum gates it would work. Similar how all we need to draw a square with -1 area is to take a line segment with a length of i, the rest is simple.
- perl4ever 6y agoDidn't I read somewhere that quantum computing basically gets you a factor of 2, like 2^(N-1)? It's a lot but at the same time it's just a bit.