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 ...
- 26.4k
20
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 ...
- 151k
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 &...
- 402
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 ...
- 26.4k
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 ...
- 151k
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 ...
- 96
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 ...
- 151k
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 ...
- 49.5k
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 ...
- 38.9k
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 ...
- 49.5k
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 $...
- 94.5k
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 ...
- 15.5k
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 ...
- 61
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 ...
- 151k
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 ...
- 26.4k
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 ...
- 26.4k
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 ...
- 4,198
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 ...
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$, $...
- 151k
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, ...
- 151k
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 ...
- 26.4k
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 ...
- 880
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 ...
- 14.6k
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 ...
- 151k
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$ ...
- 151k
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 ...
- 621
2
votes
Period finding for Quantum Computers
With a register of qbits and a function implemented on a quantum computer, one would measure the function output for the usual "mixed" input. Measuring would result in a state fixing some ...
- 2,317
2
votes
Accepted
Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH
Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?
Quite applicable; Shor's algorithm treats the group operation as a blackbox, hence it treats an even ...
- 151k
2
votes
Accepted
Shor's algorithm for discrete log and periodic function
Knowing the period of the second function cannot help you, because you already know it (at least for common Diffie-Hellman setups)!
First note that the period $\omega$ of $f(x_1)=b^{x_1}\bmod p$ is ...
- 46.4k
Only top scored, non community-wiki answers of a minimum length are eligible