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]]:
    • $f_a$ is periodic ([[modular-exponentiation]], [[discrete-logarithm]])
    • the period of $f_a$ will divide $\left(p-1\right)\left(q-1\right)$
  • 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)