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.
31
questions
3
votes
1
answer
671
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
196
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 ...
- 21.2k
-6
votes
1
answer
90
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 ...
0
votes
1
answer
97
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
159
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
632
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
79
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
133
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
529
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
339
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 ...
- 47.6k
6
votes
2
answers
178
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
3
votes
3
answers
334
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 ...
- 297
2
votes
1
answer
130
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
1
vote
1
answer
147
views
Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH
The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security ...
- 2,895
6
votes
1
answer
222
views
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. But is there a relationship between safe primes and ...
- 409
8
votes
3
answers
933
views
Can Shor's algorithm factor multi-prime numbers?
I know that Shor's algorithm can factor semi-primes ($N = p \times q \space, \{p, \space q \in \Bbb{P} \space \vert \space p, \space q \gt 0 \} $).
Assuming that all prime numbers are so large that ...
- 6,406
8
votes
0
answers
224
views
Time-memory tradeoffs in Shor's algorithm
Can a quantum computer with insufficient qubits to factor an integer of a given size make any progress in factoring it? For example, what if a quantum computer is only one qubit short of what is ...
- 15.1k
1
vote
1
answer
570
views
Negative time complexity?
Just finishing an investigation into Shor's algorithm, and the following equation,
$$
O\big(\big(\log N\big)^2 \big(\log \log N\big)\big(\log \log \log N\big)\big)
$$
is given for its time complexity. ...
- 175
33
votes
2
answers
11k
views
Largest integer factored by Shor's algorithm?
I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody have an idea about this?
- 463
2
votes
3
answers
299
views
Explaining RSA to non-scientists
I am to give a small lecture on quantum computing in a months' time and I want to shortly give intuition to the fact that Shor's algorithm shows that quantum computers will break RSA. Ideally, I would ...
- 61
2
votes
1
answer
616
views
Shor's algorithm for discrete log and periodic function
I am wondering about the following well-known problem:
Let $p$ is a prime number, $g$ is a generator of $(\mathbb{Z}/p\mathbb{Z})^\times$, $b \in (\mathbb{Z}/p\mathbb{Z})^\times$. Find $x$ - an ...
- 145
7
votes
1
answer
4k
views
How can Shor's Algorithm be applied to ECC?
I have not found a specific answer to this question on here.
Shor's algorithm can be used to factorize a large (semi)prime $N$ by reducing the task to period-finding of a function $f(x)=x^a$ mod $N$.
...
- 740
2
votes
1
answer
1k
views
Shor's algorithm for elliptic curve discrete logarithm problem
Could someone write Shor's algorithm for solving the discrete logarithm problem and how it could apply to elliptic curves in a few, easy to understand steps? I have a basic understanding of quantum ...
- 21
7
votes
1
answer
603
views
What does Shor's algorithm tell us about the complexity class of RSA and the DLP?
If quantum computers operate in BQP and (using Shor's algorithm) they are able to factor large integers and break the discrete log problem, what does that tell us about the complexity class of these ...
- 461
8
votes
1
answer
8k
views
Using Shor's algorithm to solve the discrete logarithm problem
I have read about Shor's algorithm and my understanding is that it can be used to factor large numbers efficiently. Can Shor's algorithm, though, be used to solve this problem:
Find the number $n$ ...
- 325
11
votes
1
answer
1k
views
Can Shor's algorithm compromise RSA when both the public and private key are secret?
If RSA is to create a public-private key pair and encryption is performed on plain test P to create ciphertext C, given P and C could Shor's algorithm be used to find either of the public and private ...
- 325
9
votes
1
answer
883
views
Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?
First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be ...
- 475
4
votes
1
answer
269
views
Shor's Algorithm Values
I'm studing Shor's algorithm, and I have a question regarding the following step:
$$a^r -1 = (a^{r/2}+1)(a^{r/2}-1)=0 \pmod n$$
What would be the result if ${r/2}$ was -1? This will mean it's going to ...
- 445
11
votes
1
answer
2k
views
What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithms?
There is a paper from Peter W. Shor from 1994: Algorithms for Quantum Computation: Discrete Logarithms and Factoring, and I have a question about it and the algorithms presented.
For integer ...
- 530
24
votes
1
answer
15k
views
In layman's terms, how does Shor's algorithm work?
I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't understand much about it, other than that it can factor semiprimes in polynomial time.
Could someone ...
- 3,527