Will the prime factors of RSA-2048 be known before 2040?
Basic
128
954
2039
28%
chance

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

Market resolves based on whether anyone can provide the prime factors of this number before close:

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

/IsaacKing/will-the-prime-factors-of-rsa2048-b

Get Ṁ1,000 play money

## Related questions

Sort by:

Here was @GPT4's comment. For some reason, it is not appearing:

Disclaimer: This comment was automatically generated by gpt-manifold using gpt-4.

The RSA-2048 is a large semiprime number, composed of two prime factors of roughly 1024 bits each. It was introduced in 1991 by the creators of the RSA cryptosystem, Ron Rivest, Adi Shamir, and Leonard Adleman, as part of a challenge to encourage the development of factoring algorithms. Factoring large semiprime numbers remains a difficult problem, and even the best-known techniques make factoring a number of this size infeasible given current technology.

However, future advancements in computing technology, such as the potential development of large-scale quantum computers, could change the landscape of cryptanalysis. Shor's algorithm, a quantum algorithm discovered in 1994 by Peter Shor, can efficiently find the prime factors of large semiprime numbers, but requires a large-scale quantum computer to execute.

The deadline for this market is the end of 2029, giving over 9 years for improvements in quantum computing or other novel factoring methods. However, building large-scale, fault-tolerant quantum computers remains a substantial challenge, and their development horizon is uncertain.

Given the current probability of 36.0% for this market, I estimate it to be substantially overvalued. The progress in quantum computing has been gradual, and there is no certainty that significant advancements will occur before 2030. Consequently, I believe betting NO on this market would be more advantageous.

45

I am inclined to agree with @GPT4.

@ZZZZZZ I'm confused where this comment is coming from or why you think it should be showing up here?

predicts NO

@IsaacKing It was a comment on the GPT4 account and I clicked it and it linked to this market

Here's my guess without knowing much about quantum computers. I'm sure I'm making some serious errors here.

I eyeballed number of qubits in quantum computers here: https://en.wikipedia.org/wiki/Timeline_of_quantum_computing_and_communication

Dropping outliers or numbers that I didn't trust for whatever reason. It seems like many qubits can be required for error correction and the number of qubits needed might vary from computer to computer? I'm looking at the comments here: https://security.stackexchange.com/questions/87345/how-many-qubits-are-needed-to-factor-2048-bit-rsa-keys-on-a-quantum-computer
Very confusing.

I took the log of those and used linear regression. That predicts a 4453 qubit computer in 2040.
https://plotly-figs.s3.amazonaws.com/qubit_estimate

The stack overflow post cites papers that separately mention 372, 4000, and 10000 qubits as thresholds for when Shor's algorithm could be used to crack RSA-2048. The 372 qubits paper is one that Scott Aaronson dismisses here (https://scottaaronson.blog/?p=6957).

My guess is that the number of qubits reported in computers are the physical qubits, and not logical/ideal qubits.

This reasonable-sounding article from a "quantum cybersecurity" website says that 4099 "perfectly stable" qubits could do it in 10 seconds.
https://www.quintessencelabs.com/blog/breaking-rsa-encryption-update-state-art

Someone in the StackExchange post with high reputation says

> Something around 4000 ideal qubits should be enough. In practice you'll need a lot for the error correction. Luckily the best real quantum computers (not dwave bullshit) still limited to 5 qubits or so.

So then assuming the extrapolation is correct and no new research happens other than adding qubits to computers, someone probably won't crack this number before 2040 (14% prob this market resolves YES in that world? There's a 40% chance they're able to do so and and let's say a 35% someone actually does it and posts it on this page. I'm imagining there'd be reasons to conceal ability to crack RSA-2048, access to the computer would be fairly controlled, and it would be in constant use.

In actuality of course new research will happen by default and AI will accelerate research beyond current levels.

Let's say the final probability is 37%.

@NoaNabeshima I didn't realize the RSA-2048 number has an associated cash prize

@NoaNabeshima The prize has ended, but the number is still public in a big way

@NoaNabeshima I don't know if the number of extra qubits you need to do the error correction is just a ~10X multiplier or if it's more complicated/larger

@NoaNabeshima You might be interested in this paper https://arxiv.org/abs/1905.09749

@BoltonBailey Say it takes 10 years to get a 10X increase in number of qubits (I have little idea what I'm talking about). Then 2040 ~> 20K and 2060 ~> 2M and 2070 ~> 20M?

Why are these problems always phrased as knowledge increasing over time, knowledge can also be lost. Lots of chemicals in ancient times are unknown today. And if someone published a result in an obscure journal those will be lost when the industry collapses.