Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

arxiv.org

Post reply on HN
Print view View original

51–60 of 146 posts

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#51

Post by MichaelMoser123 »

tbabej wrote: post #12

This paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).

interesting qeustions that is not related to the feasibility of this idea: would this news item cause some more fluctuations in the rate of digital currencies?

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#52

Post by gfody »

isolli wrote: post #44
BelenusMordred wrote: post #42

Earlier quoted context omitted.

> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real…

Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)

blockchain ledgers are open and public and you could think of the contents of any wallet as a bounty for cracking that wallet's private key. some of the wallets involved in early bitcoin transactions would make perfect targets - they havent moved in years and are presumed lost. the btc in them is worth billions.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#53

Post by gallerdude »

bdamm wrote: post #49
oldgradstudent wrote: post #45

Earlier quoted context omitted.

So magic computer could be more effective with more magic memory than with more magic processing power, right?

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

  ...would be like bringing mathematics to Mesopotamia.
Can you expound on this? What sort of breakthroughs are bottlenecked by developments in quantum computing?

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#54

Post by gfody »

BelenusMordred wrote: post #42
isolli wrote: post #31

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real…

this mightve been a cracked wallet https://cointelegraph.com/news/did-satoshi-just-move-his-coi...

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#55

Post by DebtDeflation »

CodesInChaos wrote: post #10
elephantum wrote: post #5

Earlier quoted context omitted.

Do I understand correctly, that largest quantum computer that exists today contains less than 100 qubits? Also it does not seem that there's an exponential grow in this area: https://www.statista.com/statistics/993634/quantum-computers... . They hit the wall in 2017. We should be safe for now :)

Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged…

>There are claims of bigger factored numbers, but they exploited special cases

Also, my understanding is that almost all of these factorizations utilize a "compiled" version of Shor's algorithm. Meaning that you need to know the factors in advance. So it's essentially "confirming" rather than "finding" the factors.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#56

Post by azatris »

bdamm wrote: post #49
oldgradstudent wrote: post #45

Earlier quoted context omitted.

So magic computer could be more effective with more magic memory than with more magic processing power, right?

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

I do not know much about quantum computing. But could you explain what makes these computers quantum? Is it the configuration of these transistors to invoke some quantum phenomena?

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#57

Post by Craighead »

gallerdude wrote: post #53
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

...would be like bringing mathematics to Mesopotamia. Can you expound on this? What sort of breakthroughs are bottlenecked by developments in quantum computing?

Temperature

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#58

Post by BelenusMordred »

lallysingh wrote: post #48
isolli wrote: post #44

Earlier quoted context omitted.

Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)

I think they're saying that we know nobody's using quantum computing to break crypto yet, because nobody's been draining bitcoin wallets.

Pretty much, it's not just bitcoin either, basically every cryptocurrency wallet is based on elliptical curve cryptography and any that have been used publicly are vulnerable to anyone on Earth having enough coherent qubits at their disposal to crunch the numbers in order to steal it.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#59

Post by CodesInChaos »

DebtDeflation wrote: post #55
CodesInChaos wrote: post #10

Earlier quoted context omitted.

Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged…

>There are claims of bigger factored numbers, but they exploited special cases Also, my understanding is that almost all of these factorizations utilize a "compiled" version of Shor's algorithm. Meaning that you need to know the factors in advance. So it's essentially "confirming" rather than "finding" the factors.

AFAIK factoring 21 is "compiled" Shor, so even that result simplifies the problem a bit.

According the first link in my post, the numbers bigger than 21 were chosen to have specific mathematical properties and attacked with algorithms even less realistic that compiled Shor.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#60

Post by rnestler »

bdamm wrote: post #49
oldgradstudent wrote: post #45

Earlier quoted context omitted.

So magic computer could be more effective with more magic memory than with more magic processing power, right?

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

> they're just very low power,

I guess you meant to write high power as in high electrical power consumption? Or low power in the sense of low processing power? Anyway: Performance per Watt is probably pretty bad for current quantum computers ;)

Post reply on HN