> This study investigates a class of special integers that the factors differ by only two bits, and the difference is present only at the two bits with weights of 2 and 4.
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 · 20h ago
The difference is not only two bits, but "with weights of 2 and 4" is newspeak for the change only happening at second-to-last and third-to-last bits.
A classical computer can factor those numbers in 0 milliseconds.
bawolff · 20h ago
Skip the computer. A human can factor that by hand.
brookst · 20h ago
Yeah this is “new lockpick demonstrated that defeats high end locks with the special case of the key only having one bump”
Polizeiposaune · 20h ago
if it's really as simple as p = q xor 6 or even p|6 == q|6, I'd think that trial division starting with the first odd number less than the square root would get you there in a handful of trials.
jcranmer · 20h ago
From the title, I thought this was a factorization of the RSA-2048 integer (i.e., the one you get the prize for factoring). So I quickly skimmed to the results section to see what the factors where.
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.
bawolff · 20h ago
D-Wave continuing the trend of being so misleading it borders on fraud...
antimatter15 · 20h ago
Note that this doesn't represent a general break of RSA-2048, and doesn't affect the security of RSA-2048 as it's used anywhere.
The paper only applies to "special integers" where the prime factors are known to only differ by two bits.
formerly_proven · 20h ago
This is ridiculous clickbait even for quantum computing standards. It might actually cross the threshold of being flag-worthy…
> 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“
warpspin · 20h ago
> This is ridiculous clickbait even for quantum computing standards. It might actually cross the threshold of being flag-worthy…
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.
bawolff · 20h ago
Tl;dr: Factoring numbers is usually hard, but its only hard for some combinations of numbers. There are some types of numbers where its pretty easy. E.g. 15506 is easy to factor because it ends in a 6 which tells you its even and divisible by 2. So 2 is one of the factors.
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]
popol12 · 20h ago
Yup, I posted it for this reason.
drob518 · 20h ago
Yes, please.
thrance · 20h ago
Here we are treated to yet another clickbaity piece of quantum disinformation. Since the only tangible potential use case of this crackpot industry is cracking RSA encryption, its actors resort to misleading publications claiming success to part yet more money from clueless investors.
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.
bawolff · 20h ago
I'd take issue with it being the only use case. There are things QC is useful for beyond factoring. Its just that all the use cases (including actual factoring) are so far away from being reality that nobody would invest if they were being honest about the time horizons.
SAI_Peregrinus · 19h ago
And D-Wave's quantum annealers have no path to run either Shor's or Grover's algorithm, so far there's no evidence they're any faster than simulated annealing.
bawolff · 18h ago
Yeah, i'd consider dwave basically scammers at this point.
thrance · 10h ago
OK, to be fair I exaggerated a bit in my previous comment. Looking at lists of known quantum algorithms, I just don't see many that have practical use cases, and even less that could possibly be implemented in a reasonable time scale.
I feel, and that may just be a feeling, like Shor's algorithm and its modern variants are the only serious applications so far.
bawolff · 4h ago
Usually the best alleged application is using them to do physics simulations that wouldn't be possible on a normal computer. Its a bit unclear precisely what that will open up, but normal computers opened up a lot of applications by being able to simulate classical system, perhaps QC will do the same for quantum physics things.
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)
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.
A classical computer can factor those numbers in 0 milliseconds.
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.
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]
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)