Skip to main content
53 votes
Accepted

Largest integer factored by Shor's algorithm?

wondering what the largest integer is which they were able to factor with a small quantum computer This answer starts with stunt records. See final paragraph for the the largest meaningful record. ...
27 votes
Accepted

Will IBM's Condor quantum processor run Shor's Algorithm to crack a 256-bit Elliptic Curve key?

No. The issue here is the distinction between physical qubits and logical qubits. The back of the envelope estimate for Shor's algorithm for a 256-bit elliptic curve is 512 logical qubits, but a more ...
Daniel S's user avatar
  • 24.1k
19 votes

How will the world learn that Q-Day has arrived?

How will the world learn that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived? Well, one thing to note is that cryptanalysis is not the only thing a ...
poncho's user avatar
  • 148k
14 votes

Using Shor's algorithm to solve the discrete logarithm problem

Shor's method relies on a period finding routine on a quantum computer. A function $f: (x_1, \dots, x_n) \mapsto f(x_1, \dots, x_n)$ is periodic, of period $(\omega_1, \dots, \omega_n)$, if $f(x_1 + \...
user94293's user avatar
  • 1,779
11 votes

How will the world learn that Q-Day has arrived?

Frame challenge: "Q-Day" is a mental shortcut for what is not actually a sudden event. Quantum computing, nuclear fusion, AI, flying cars - there's a number of technologies that have been &...
Tom's user avatar
  • 402
10 votes
Accepted

Can Shor's algorithm compromise RSA when both the public and private key are secret?

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$. We know that $P^e = C \bmod N$; that's equivalent to $P^e ...
poncho's user avatar
  • 148k
8 votes

How could ECDSA be broken with prime factorization through Shor's Algorithm?

I'm going to give a more detailed version of @poncho's answer. Let me know if you'd like more detail on any point and I can make it still longer. Ideas that you might need to read additional ...
Daniel S's user avatar
  • 24.1k
7 votes

Shor's Algorithm Values

What would be the result if $r/2$ was -1? I assume you meant "how does this work if $a^{r/2} \equiv -1$? Yes, that does not give us a factorization; however there's an easy fix - use a different ...
poncho's user avatar
  • 148k
7 votes

How can Shor's Algorithm be applied to ECC?

Section 2.2 of the following paper details how to apply Shor's algorithm to ECDLP: https://eprint.iacr.org/2017/598.pdf The process is similar to DLP, except that we need different circuits to ...
user44248's user avatar
6 votes
Accepted

Why can't we just increase the bit length to counteract shor's algorithm?

if shor's algorithm has a complexity of roughly n^3 why cant we just increase the bit size until the time for the algorithm to run is unfeasible on a quantum computer The problem is that the amount ...
poncho's user avatar
  • 148k
6 votes

Shor's algorithm for elliptic curve discrete logarithm problem

Could one adapt Shor's algorithm to solve the DLP? Yes: Shor's original paper (arXiv preprint) explains how, in ยง6 on p. 321. Could one adapt Shor's algorithm to solve the ECDLP? Yes. Researchers ...
Squeamish Ossifrage's user avatar
6 votes

Can Shor's algorithm factor multi-prime numbers?

Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod ...
Squeamish Ossifrage's user avatar
6 votes
Accepted

Can Shor's algorithm factor multi-prime numbers?

Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to: If $n$ is a product of more primes, say $...
Maarten Bodewes's user avatar
  • 93.2k
6 votes

Can Shor's algorithm factor multi-prime numbers?

Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in this Wikipedia article which describes how the algorithm takes an odd integer and ...
forest's user avatar
  • 15.3k
6 votes
Accepted

Explaining RSA to non-scientists

This should be the flow of the description of RSA RSA is a public key crypto system that everyone in the room who doesn't live in a cave uses pretty much every day. If you are using a computer to get ...
mikeazo's user avatar
  • 38.7k
6 votes

How will the world learn that Q-Day has arrived?

I'm a professional cryptographer for a major financial company, and I've been doing crypto professionally for 37 years. If anyone can develop a QC capable of factoring big key-moduli, it'll be a ...
Don Davis's user avatar
5 votes
Accepted

Is RSA-OAEP secure against Shor's factoring algorithm

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA? Well, remember that the assumption in the original question was that we kept ...
poncho's user avatar
  • 148k
5 votes
Accepted

Why doesn't this factoring to order-finding reduction work?

Aaronson's notes discuss finding $p$ and $q$ if we know $\phi(N)$ by solving the quadratic equation $X^2-(N-\phi(N)+1)X+N=0$ whose roots are $p$ and $q$. This only works if $N$ is the product of two ...
Daniel S's user avatar
  • 24.1k
5 votes
Accepted

Period finding for Quantum Computers

There are a few limitations on the function that you may or may not consider obvious. The image of the function $f$ has to be a finite set. The function $f$ has to be computable and the efficiency ...
Daniel S's user avatar
  • 24.1k
4 votes

Period finding for Quantum Computers

Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function? Well, the function has to be periodic; that is, we have, for some $c > 0$, $...
poncho's user avatar
  • 148k
4 votes
Accepted

Negative time complexity?

The big O notations describes the complexity when $N$ approaching infinity, it is not a formula giving you exact running time for all $N$. Roughly, let $f(N)$ be the function for the running time of ...
Changyu Dong's user avatar
  • 4,188
4 votes

Largest integer factored by Shor's algorithm?

According to L. Zyga et al, N. Dattani and N. Bryans factored $56\,153 = 233 \cdot 241$ in November 2014, using a 4-qubit minimization (adiabatic quantum computation?) algorithm. Researchers believe ...
Dave Schulman's user avatar
4 votes
Accepted

Are some RSA moduli more resistant than others to Shor's factorization algorithm?

Does there exist a semi-prime integer $n$ (e.g., an RSA modulus) such that the order of every element in the multiplicative group modulo $n$ is equal to the order of the full group modulo $n$? No, ...
poncho's user avatar
  • 148k
3 votes

Why can't we just increase the bit length to counteract shor's algorithm?

The main reason is because any such technique has at best a polynomial gap between the effort honest parties must spend to compute the cryptosystem, and the effort adversaries must spend to break the ...
Mark Schultz-Wu's user avatar
  • 13.5k
3 votes

What is the best strategy to avoid getting even orders in Shor's algorithm?

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor. Not really; to factor, all you need is a value $e$ ...
poncho's user avatar
  • 148k
3 votes

How could ECDSA be broken with prime factorization through Shor's Algorithm?

I am researching about how could Shor's Algorithm end up breaking ECDSA, but I do not find what the relationship is between this cryptographic algorithm and prime factorization. Well, Shor's ...
poncho's user avatar
  • 148k
3 votes

Would it be technically possible to use hundreds of computer processors together to work on an algorithm like the Shor's algorithm and break RSA?

This is routinely done for the largest factorization records of RSA-type moduli (two primes of roughly the same size), although using a classical algorithm called the Number Field Sieve. Out of its ...
swineone's user avatar
  • 880
3 votes

Are Schnorr's algorithm really subject to q-computer attacks?

The quantum Fourier transform is more powerful than a black box that returns the period of a cyclic group. A more general application is the hidden abelian subgroup problem. In the case of discrete ...
Daniel S's user avatar
  • 24.1k
3 votes

How will the world learn that Q-Day has arrived?

How do we know it hasn't already? Perhaps I have a working quantum computer in my basement that is currently breaking a thousand RSA keys a second? Can you prove that I have not? Well, the public will ...
Philipp's user avatar
  • 621

Only top scored, non community-wiki answers of a minimum length are eligible