Factoring
- given a natural $
N = pq > 0$ it is hard to discover $p$ and $q$ from just $N$
-
[[quantum-computing]]
- given $
a \in_R \left[3, N-1\right)$
- define a function $
f_a\left(x\right) = a^x \mod N$
-
reduction from factoring to [[order-finding]]:
-
if we use the QFT to naively period-find:
- the resulting period might be large (only bounded by $
N$) so we might not have enough input to get a frequency out
- resolve this by taking $
M \geq N^2$ as our input size, which means we will get a clean frequency out (at least $N$ periods)
- what we measure ($
z$) divides $\left(p-1\right)\left(q-1\right)$, not $N$ or $M$, which means our resultant frequency windows are truly windows and not discrete points (in [[discrete-logarithm]], the period divides the input size), and this window is exponentially large wrt $n$ (i.e. no better than classical) due to the order of $pq - \left(p-1\right)\left(q-1\right)$
- this is because the frequency of our function is rational (not integral) in $
M$-space
- so if we want to find the true value, we can use [[continued-fraction]]s
- if $
a$ is picked uniformly at random, the chance that the period is a nontrivial factor is $\geq \frac{1}{4}$
- factoring $
\left(p-1\right)\left(q-1\right)$ allows us to factor $pq$
- the actual $
M$ needed is just $N\log N$ (nontrivial to prove)