←back to thread

Why haven't quantum computers factored 21 yet?

(algassert.com)
335 points ingve | 3 comments | 31 Aug 25 12:14 UTC | HN request time: 0.672s | source
Show context
AceJohnny2 ◴[31 Aug 25 14:24 UTC] No.45083369[source]▶
What does this mean about the size (and thus feasibility) of a circuit required to factor a cryptographically interesting number, say, to be generous, RSA1024?
replies(3): >>45083384 #>>45083585 #>>45085971 #
Davidzheng ◴[31 Aug 25 14:50 UTC] No.45083585[source]▶
Off topic, but are cryptographers convinced that on the new gigawatt data centers RSA1024 is infeasible to factor? I gather that the fastest known algorithms are still too slow to factor it in reasonable time. But is consensus that there will not be improvements to these algorithms in near future?
replies(5): >>45083630 #>>45083640 #>>45084065 #>>45084254 #>>45087766 #
rwmj ◴[31 Aug 25 14:56 UTC] No.45083640[source]▶
Number Field Sieves are still the best method, and the techniques are three or more decades old with only incremental improvements. (Of course there might be an incredible breakthrough tomorrow.)
replies(1): >>45083688 #
tiahura ◴[31 Aug 25 15:01 UTC] No.45083688[source]▶
best published method
replies(2): >>45084217 #>>45084376 #
consp ◴[31 Aug 25 16:06 UTC] No.45084217[source]▶
Are the bitcoins in the first wallets gone? No? I will assume it's still the best method without any irrefutable evidence.
replies(2): >>45084251 #>>45084273 #
tripplyons ◴[31 Aug 25 16:11 UTC] No.45084273{3}[source]▶
Bitcoin uses ECDSA to sign transactions, not RSA.

In addition, selling information to a government on how to break either system would be more valuable than the amount of bitcoin you would able to sell before exchanges stop accepting deposits or the price crashes.

replies(3): >>45084418 #>>45084444 #>>45085452 #
1. cyberax ◴[31 Aug 25 18:11 UTC] No.45085452[source]▶
A method to efficiently factor large numbers will also break the ECDSA.
replies(1): >>45086256 #
2. CamperBob2 ◴[31 Aug 25 19:26 UTC] No.45086256[source]▶
No, ECDSA relies on the hardness of the discrete logarithm problem. Nothing to do with factoring, at least not in the classical sense.

On a quantum computer, my understanding is that Shor's algorithm could potentially target both problems, though.

replies(1): >>45086695 #
3. cyberax ◴[31 Aug 25 20:19 UTC] No.45086695[source]▶
Both systems are an example of a hidden Abelian subgroup problem. That is also why Shor's algorithm equally applies to both: https://en.m.wikipedia.org/wiki/Shor%27s_algorithm#Shor's_al...

So a hypothetical classic algorithm that breaks the RSA is also highly likely to break the ECDSA.