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

111–120 of 146 posts

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

#111

Post by ledauphin »

antepodius wrote: post #63
azatris wrote: post #56

Earlier quoted context omitted.

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?

In a classical computer, every bit of information in the system is in a definite state- 1 or 0. In a quantum system with such definite possible states, what you actually have most of the time of the system in some interpolation of the possible states- so in the quantum computer case each bit is usually in a state a 1 + b 0, where a and b are complex numbers such that |a^2|+|b^2| = 1. Most of the time, the 'weight' fl…

this is the most comprehensible entry-level description of quantum computers I've ever read. thank you.

(qubits I've seen explained many times, but setting things up so that qubits are probabilistically correlated is the part I've never understood anyone else to be saying)

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

#112

Post by SAI_Peregrinus »

dfox wrote: post #50
marcosdumay wrote: post #27

Earlier quoted context omitted.

> you should not be using RSA today Also, always remember that ECC is believed to be just as weak against quantum computers as RCA. So you'll probably want some fusion of pre and post-quantum algorithms. Or, anyway, get your perfect forward secrecy working and don't rely on asymmetric crypto for confidentiality. Yeah, PFS is very hard to get on some use cases, but it's really the best way to solve this problem.

PFS still involves asymmetric cryptography. And in fact in essentially every modern cryptography stack (ie. (EC)DLP-based) the "PFS primitive" (Diffie-Hellman, ie. scalar multiplication/exponentiation) is the one thing that everything else is derived from. RSA is in fact somewhat notable for being the only widely used asymmetric cryptosystem where the underlying operation is block cipher-ish encryption primitive and…

> RSA is in fact somewhat notable for being the only widely used asymmetric cryptosystem where the underlying operation is block cipher-ish encryption primitive and not key agreement primitive.

Debatable. It's sort of true of RSA-OAEP. That's not true of RSA-PSS (signatures), nor of RSA-KEM (key encapsulation). Really it's the OAEP that's block-cipher like, and the fundamental RSA operation (modular exponentiation) isn't "encryption" or "signing" or "decryption" or "encapsulation" or anything else cryptographic on its own.

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

#113

Post by klodolph »

fractionalhare wrote: post #81
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.

The research in this field proceeds under the umbrella and framework of physics, yes. But it's not clear that it's possible to scale up to the number qubits required do anything nontrivial. It's plausible there are hard engineering limits on error correction which make it asymptotically more difficult with each order of magnitude more qubits involved. It might not look that way because there's a lot of (relatively) m…

I thought the Quantum threshold theorem said that it was possible to scale up quantum computers as much as you like? Or am I misinterpreting it?

https://en.wikipedia.org/wiki/Quantum_threshold_theorem

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

#114

Post by thesz »

robocat wrote: post #102
dcow wrote: post #97

Earlier quoted context omitted.

CPU cost is not dominated by the cache size is the problem, I think.

But I think that cache is roughly 50% of marginal production cost of the silicon chip die by mm2. https://cdn.wccftech.com/wp-content/uploads/2020/11/AMD-Ryze... https://images.anandtech.com/doci/16214/Zen3_arch_19.jpg

Cache is not memory, it is more complex - LRU and all that, often with several access ports (quadratic space dependence). SRAM is memory that is on-die and it is much cheaper.

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

#115

Post by alacombe »

jakozaur wrote: post #70

One day you can start calculating private keys based on public keys. This is the biggest crypto puzzle: find private key of Sathoshi Bitcoin wallet with 1 mln bitcoins. Over $50 Bln prize for one crypto puzzle. This would be AlphaGo moment of quantum computing if you could make that one attack successful even while paying huge price (e.g. years of quantum datacenter work).

ECC is totally different than RSA principles discussed here.

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

#116

Post by renata »

Invictus0 wrote: post #77
unilynx wrote: post #71

Earlier quoted context omitted.

Cashing out and actually getting $50B may be as much of a challenge as finding the private key

Hypothetically, you could publicly announce that you'll sell the stash at the rate of 1% per year, to demonstrate faith in the continued growth of bitcoin in order to finance and reassure the market that it won't massively crash.

And you could even sign the announcement with one of Satoshi's wallet keys.

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

#117

Post by oldgradstudent »

reikonomusha wrote: post #83
fractionalhare wrote: post #81

Earlier quoted context omitted.

The research in this field proceeds under the umbrella and framework of physics, yes. But it's not clear that it's possible to scale up to the number qubits required do anything nontrivial. It's plausible there are hard engineering limits on error correction which make it asymptotically more difficult with each order of magnitude more qubits involved. It might not look that way because there's a lot of (relatively) m…

I think it’s reasonable to be more optimistic than you put it. Qubit counts and qubit fidelity have been increasing at a remarkable rate. Just five years ago we could barely eek out a handful of qubits, and when we did, they’d be bad. Google’s quantum supremacy result is a testament to that. (At this stage, whether they actually demonstrated the “supreme” part of supremacy is, imho, irrelevant. They’ve demonstrated a…

> They’ve demonstrated a much larger, controllable, programmable quantum computer

No they didn't. Not in any meaningful sense.

How exactly what that machine does can be called a "computation"? in what sense is it "programmable"?

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

#118

Post by jMyles »

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

I don't think I understand this metaphor.

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

#119

Post by haltingproblem »

I fear it is my obligation to point out this excellent screed by Scott Lockin: "Quantum computing as a field is obvious bullshit". A beautiful excerpt from the article:

When I say Quantum Computing is a bullshit field, I don’t mean everything in the field is bullshit, though to first order, this appears to be approximately true. I don’t have a mathematical proof that Quantum Computing isn’t at least theoretically possible. I also do not have a mathematical proof that we can or can’t make the artificial bacteria of K. Eric Drexler’s nanotech fantasies. Yet, I know both fields are bullshit. Both fields involve forming new kinds of matter that we haven’t the slightest idea how to construct. Neither field has a sane ‘first step’ to make their large claims true.

.....

“quantum computing” enthusiasts expect you to overlook the fact that they haven’t a clue as to how to build and manipulate quantum coherent forms of matter necessary to achieve quantum computation. A quantum computer capable of truly factoring the number 21 is missing in action. In fact, the factoring of the number 15 into 3 and 5 is a bit of a parlour trick, as they design the experiment while knowing the answer, thus leaving out the gates required if we didn’t know how to factor 15. The actual number of gates needed to factor a n-bit number is 72 x n^3; so for 15, it’s 4 bits, 4608 gates; not happening any time soon.

[1]: https://scottlocklin.wordpress.com/2019/01/15/quantum-comput...

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

#120

Post by TheRealPomax »

haltingproblem wrote: post #119

I fear it is my obligation to point out this excellent screed by Scott Lockin: "Quantum computing as a field is obvious bullshit". A beautiful excerpt from the article: When I say Quantum Computing is a bullshit field, I don’t mean everything in the field is bullshit, though to first order, this appears to be approximately true. I don’t have a mathematical proof that Quantum Computing isn’t at least theoretically pos…

except we already use qubits in the real world, and we already use entangled pairs in banking, so it's not really all that bullshit anymore. Quantum computers with a significant number (e.g thousands, but really, millions) of qubits, however, are still quite a ways away. But clearly not in the realm of bullshit anymore.
Post reply on HN