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