Tag Info

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. ...
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 ...
• 24.1k

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 ...
• 148k

• 148k

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 ...
• 24.1k

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 ...
• 148k

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 ...
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 ...
• 148k

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 ...
• 48.7k

• 93.2k

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.3k
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.7k

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 ...
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 ...
• 148k
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 ...
• 24.1k
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 ...
• 24.1k

• 148k

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 ...
• 148k

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