Modular order finding with rational reconstruction

Input. An integer $N\ge 3$, the standard representative $x\in \{1,\dots ,N-1\}$ of a unit class modulo $N$, and an integer $b\ge 1$ specifying target failure probability $\delta =2^{-b}$.

The representative is the unique one in $0\le x<N$ by For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$; unit membership is equivalent to $\gcd (x,N)=1$ by The unit group $(\mathbb{Z}\mathrm{/}n{)}^{\times }$ and Euler's totient $\phi (n)=\mid (\mathbb{Z}\mathrm{/}n{)}^{\times }\mid$ for $n\ge 1$ and For $n\ge 1$, $[a{]}_n$ is a unit if and only if $\gcd (a,n)=1$. The register ket $\mathrm{\mid }1⟩$ uses Dirac Notation Conversion. The superposition output law for applying the QPE gate list to this non-eigenvector input is supplied by Phase estimation on a superposition of eigenspaces.

Output. An accepted candidate, or FAIL.

Instructions. Set $n=\lceil {\log }_{2}N\rceil$, $m=2n+3$, $Q=2^m$, and $t=4(n+1)b$. The inequality $Q>4N^2$ follows from $N\le 2^n$. Compute the inverse constant by the following binary-integer loop. Initialize $(R,S,U,V):=(N,x,0,1)$. While $S>0$, use division with remainder to compute $q,r$ with $R=qS+r$ and $0\le r<S$, compute the least residue $h=(U-qV)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$, and simultaneously replace $(R,S,U,V)$ by $(S,r,V,h)$. Division and least residues use Division with remainder in $\mathbb{Z}$: for $a\in \mathbb{Z}$ and $b>0$ there are unique $q,r\in \mathbb{Z}$ with $a=qb+r$ and $0\le r<b$ and For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$; use schoolbook binary arithmetic for every update. When the loop stops, return FAIL if $R\mathrm{\ne }1$; otherwise set $b_0:=U$ and $a_0:=x$. The inverse identity, termination, and preprocessing bit cost are established in Gate and bit cost of modular multiplication and powering. For $j=0,\dots ,m-2$, compute $a_{j+1}=a_j^2<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ and $b_{j+1}=b_j^2<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$. Then $a_j=x^{2^j}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ and $b_j=a_j^{-1}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ for all $j<m$.

Repeat independently for samples $s=1,\dots ,t$. Initialize the system register to the valid residue $\mathrm{\mid }1⟩$ and apply the QPE phase-estimation circuit with phase-register length $m$. Its controlled $U_x^{2^j}$ gate is implemented by the explicit controlled modular-multiplication circuit for $a_j$ from Reversible modular multiplication by a unit. This procedure uses the QPE gate list on $\mathrm{\mid }1⟩$; it does not assert that $\mathrm{\mid }1⟩$ is an eigenvector. Measure the phase register to obtain $y$. Run Rational reconstruction from a phase sample with $(N,Q,y)$. If it returns FAIL, retain no denominator from this sample. If it returns $p\mathrm{/}q$, compute $x^q<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ as follows: set $v:=1$, $a:=x$, $e:=q$; while $e>0$, if $e$ is odd set $v:=va<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$, then set $a:=a^2<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ and $e:=\lfloor e\mathrm{/}2\rfloor$. Retain $q$ exactly when the final $v=1$.

After all samples, return the smallest retained positive denominator; return FAIL if none was retained. A passing candidate is not called the order unless it is minimal. The exact criterion $x^q=1$ iff the order divides $q$ is If $\mathrm{ord}(g)=n$ then $g^k=e$ iff $k$ is an integer multiple of $n$, the powers $g^0,\dots ,g^{n-1}$ are distinct, and $⟨g⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^j=g^k$ only for $j=k$. The separate item thm-qa-modular-order-finding-success proves the probability guarantee and the fact that every retained candidate is an order multiple.