The paper only applies to "special integers" where the prime factors are known to only differ by two bits.
> When factoring this class of integers, their special properties will make the exponential-level solution space search problem in the factorization simplify to a constant-level solution space search problem, which greatly saves computational resources.
„We elected to solve a O(1) subset instead of the actual problem“
The discussion here where people explain in which ways it is misleading and thereby saving me lots of time reading this myself has a worth of itself IMHO.
Guess others might feel the same.
When people talk about the factoring problem or RSA, they generally don't mean the super easy cases. They mean the hard cases which you would actually use in crypto.
Anyways this paper factors numbers where the two factors are super close to each other. This is generally very easy to factor as you can just take the square root and try guesses around there. Its so easy that you could probably do it in 15 minutes with a paper and pencil if you were so inclined (and were familiar with how to hand calculate square roots)
[I didnt actually read the paper]
It's not. It's a factorization of the product of two 1024-bit numbers that are known to differ only in two bits (and the bit positions they differ may also be an input to the algorithm, not clear on that). The only relevance to RSA-2048 is that it's not technically a lie that they factored a 2048-bit integer.
Here, they picked artificially constructed numbers that are designed to be easy to factor. Something classical computers could do far more efficiently mind you, but hey, maybe some guy won't read the article and invest a few extra bucks in D-Wave based on the headline, in which case it was all worth it. It only required further degrading the credibility of this clown industry.
I feel, and that may just be a feeling, like Shor's algorithm and its modern variants are the only serious applications so far.
You're right that most of the other algorithms are pretty useless. Shor and Grover are certainly fascinating intellectually, but i doubt would be particularly useful (shor because everyone will switch to pqc if qc ever becomes relavent and grover is too slow to ever be useful)
Moreover, D-Wave's quantum computers rely on quantum annealing, not Shor's algorithm. Quantum annealers are NOT gate-based machines. Only for the latter is there a theoretical exponential speedup over a classical computer. For the former, we still don't know if there is any speedup at all. And if there is, it probably is not applicable in general: getting lucky with a specific integer does not count.
rainsford•9mo ago
So as far as I can tell from some quick skimming, the paper's title is entirely clickbait. Regardless of the size of the numbers involved, this is not really "RSA-2048" because no one would construct an actual RSA-2048 key this way. And if they did, I think it would be susceptible to classical attacks like Fermat factorization, no "quantum computer" needed.
To be fair, the paper does eventually admit this has no real impact on actual RSA-2048, but it does still try to characterize this as some sort of looming threat.
sigotirandolas•9mo ago
A classical computer can factor those numbers in 0 milliseconds.
bawolff•9mo ago
brookst•9mo ago
Polizeiposaune•9mo ago