# Questions tagged [factorization]

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

5 questions
Filter by
Sorted by
Tagged with
1 vote
53 views

### 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
73 views

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

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