# 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.

20 questions
Filter by
Sorted by
Tagged with
95 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 ...
155 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 ...
80 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 ...
69 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 ...
154 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 ...
595 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 ...
190 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 ...
396 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. ...
8k 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?
234 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 ...
331 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 ...
2k 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$. ...
839 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 ...
493 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 ...
5k 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 $e$ ...
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 ...
611 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 ...
224 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 ...