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-fractions
  • 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)