Questions tagged [shors-algorithm]
Shor’s algorithm is famous for factoring integers in polynomial time. Since the best-known classical algorithm requires superpolynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers.
32
questions
11
votes
4
answers
8k
views
How will the world learn that Q-Day has arrived?
I wonder how the world will come to know that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived. The day when this happens has been referred to as "...
- 289
3
votes
1
answer
680
views
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$? If so, ...
7
votes
0
answers
307
views
Noisy Quantum Gates Spoil Shor's Factorization Attack
Update:
In Lipton and Regan's blog, Scott Aaranson and Craig Gidney have commented that the results are not unexpected and also not a deal-breaker in that dealing with this type of noise is already ...
- 22.9k
-7
votes
1
answer
133
views
Are Schnorr's algorithm really subject to q-computer attacks?
I was wondering whether quantum-computers really break Schnorr's signature scheme. Schor's algorithm works via the quantum Fourier transform, which reveals the cycle time and thus phi. However, with a ...
user109154
0
votes
1
answer
104
views
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?
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?
I've been reading about the crazy amount of qubits ...
- 9
1
vote
3
answers
187
views
Why can't we just increase the bit length to counteract shor's algorithm?
I know that it sounds like a very stupid question but 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 ...
4
votes
2
answers
1k
views
How could ECDSA be broken with prime factorization through Shor's Algorithm?
could anyone help me understand how is ECDSA broken using Shor's Algorithm? All the papers I find are too complex to understand, and even though I feel I understand some concepts, some others are a ...
- 61
19
votes
1
answer
5k
views
Will IBM's Condor quantum processor run Shor's Algorithm to crack a 256-bit Elliptic Curve key?
Yesterday IBM announced that they have a 433 bit quantum computer, called Osprey. There is nothing in the press releases I can find that says whether it can or cannot run Shor's Algorithm.
They also ...
- 343
1
vote
1
answer
87
views
Can Shor's algorithm factor over finite fields/rings/groups?
Shor's algorithm can (efficiently) solve equations of the form:
$$n = pq$$
and
$$n = x^{2} + y^{2}$$
This question is simple: Can Shor's algorithm solve these equations in polynomial time when they ...
- 45
3
votes
1
answer
146
views
Can Shor's algorithm factor over the gaussian integers?
This is related to this question about solving the following expression:
$$x^{2} + y^{2}$$
This can be factored over the gaussian integers as
$$(x + iy)(x - iy)$$
If one could factor a sum of two ...
- 45
1
vote
1
answer
688
views
Shor's algorithm and ECDSA in Bitcoin - why is finding the private key still difficult when we know the base point?
I'm learning about Shor's algorithm and how it can be applied to break ECDSA. I've clearly missed something basic here - I thought I understood that the challenge ECDSA presented was to find the ...
- 13
1
vote
2
answers
401
views
Using Shor's algorithm to access RSA messages without factoring
Most of the time people forgot that the real aim of the adversary against encryption is accessing the message. For example, in the RSA case, we talk about the factoring of the modulus to reach the ...
- 49.1k
6
votes
2
answers
204
views
Why doesn't this factoring to order-finding reduction work?
Scott Aaronson likes to motivate the factoring-to-period-finding algorithm used inside Shor's algorithm as follows.
Now, I want you to step back and think about what this means. It means that, if we ...
- 63
4
votes
3
answers
389
views
Period finding for Quantum Computers
Shor's algorithm shows how a quantum computer (with sufficiently many qubits) can solve the factorization problem efficiently. Also the discrete logarithm problem can be solved efficiently with such a ...
- 317
2
votes
1
answer
138
views
Is RSA-OAEP secure against Shor's factoring algorithm
I've seen in this answer Can Shor's algorithm compromise RSA when both the public and private key are secret? that if textbook RSA is used (deterministic) the Shor's algorithm can reak it. However, if ...
- 276