19 lines
1.5 KiB
Markdown
19 lines
1.5 KiB
Markdown
|
|
# 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)
|