Your submission is now in Draft mode.

Once it's ready, please submit your draft for review by our team of Community Moderators. Thank you!

Submit Essay

Once you submit your essay, you can no longer edit it.

Pending

This content now needs to be approved by community moderators.

Submitted

This essay was submitted and is waiting for review.

Date Quantum Algorithm Factors RSA Number

Question

Quantum computing has shown remarkable advancements in the past decade. In that time, quantum processors went from being almost purely theoretical devices to arguably achieving computational supremacy over classical computers in a limited scope.

Among the most promising capabilities of any sufficiently powerful quantum computer is their ability to factor very large numbers, the difficulty of which underlies many current cryptography systems. One of the best known quantum algorithms, known as Shor's algorithm, has the potential to run almost exponentially faster than the most efficient known classical factoring algorithm.

That being said, we’re currently quite a ways away from being able to use it in practice. As of writing, the largest number factored via Shor's algorithm is still only 21, achieved back in 2012. While current state-of-the-art quantum processors possess on the order of dozens of qubits, it is estimated that in order to factorize semiprimes on the same scale as those used in modern RSA cryptography would take thousands of qubits.

In order to encourage research into the problem of factoring large integers and potentially cracking RSA keys, RSA Laboratories put forward their RSA Factoring Challenge in 1991. Though the challenges officially ended in 2007, they’re still used as a common benchmark for factoring to this day. The largest number factored so far, RSA-240, was publicized only last December. The full list of numbers, including all known factorizations, can be found here.

When will a quantum computer running Shor's algorithm (or a similar one) be used to factor one of the RSA numbers for the first time?

This question will resolve on the date that it is publicly announced that a quantum computer running Shor's algorithm (or a similar one) has successfully factored a previously unfactored RSA number. Credible media reports and public release of the prime factors will suffice as a source. The factored RSA number must be one that previously had no publicly known factorization; a factorization of RSA-100 for example will not suffice. This question will resolve as "ambiguous" if every RSA number is factored via classical computers first.

Make a Prediction

Prediction

Note: this question resolved before its original close time. All of your predictions came after the resolution, so you did not gain (or lose) any points for it.

Note: this question resolved before its original close time. You earned points up until the question resolution, but not afterwards.

Current points depend on your prediction, the community's prediction, and the result. Your total earned points are averaged over the lifetime of the question, so predict early to get as many points as possible! See the FAQ.