Factoring ยท Algorithms

Order finding

Theorem statement

Suppose $N\ge 2$, $x$ is an integer with $\gcd(x,N)=1$, and $r$ is the least positive integer satisfying $x^r\equiv 1\pmod N$. Choose $t$ such that $N^2\le 2^t<2N^2$. Given access to a modular-exponentiation oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus x^a\bmod N}$, there exists a quantum algorithm that outputs $r$ with success probability at least $\varphi(r)/(3r)$, using one query to $U_x$, $t$ Hadamard gates, $t(t-1)/2$ controlled-phase gates, $\lfloor t/2\rfloor$ SWAP gates, and $\mathcal{O}(\operatorname{poly}(t))$ classical operations.
$$N$$
Integer modulus.
$$x$$
Integer base coprime to N.
$$r$$
Multiplicative order of x modulo N.
$$t$$
Phase-register bit length.
$$U_x$$
Modular-exponentiation oracle.
$$a$$
Exponent-register basis value.
$$y$$
Work-register basis value.
$$\varphi$$
Euler totient function.
$$\mathcal{O}$$
Asymptotic upper-bound notation in the unverified public target.

Sources

Lean context

Copy a short prompt with the import, theorem name, citations, and public source link.

Open Lean source