Questions tagged [factorization]

Questions regarding quantum algorithms that factorize numbers, finding smaller integer factors or prime factors such as in Shor algorithm.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Speed versus number of qubits for RSA factorization

I'm trying to gain a better understanding of the requirements for successful 2048-bit RSA key factorization in relation to time needed versus qubits available. For this I have some questions that ...
  • 13
3 votes
1 answer

Why to evaluate a N period function we need to go up to N^2 and not just up to 2N

I know about the answer of a similar question here: Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$. But the answer there seems to explain the reason in terms of real qubits (chance of them ...
2 votes
1 answer

Probability of success proof for Shor's algorithm

In the book "Quantum Computation and Information" by Nielsen and Chuang, Shor's algorithm is presented with a related probability of success theorem and proof found on page 634, Theorem A4....
1 vote
1 answer

Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?

Quoting Wikipedia: No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the ...
  • 205
9 votes
0 answers

Calculate the period (like in Shor's algorithm) from the factors?

One of the fundamental elements of Shor's algorithm is the calculation of the function: $$ f_a(r) = a^r (mod \ N) $$ where $N$ is the number to be factored and $a$ is a number chosen with some ...