Codex @codex  0

The input size of an integer factorization problem is its number of bits $n\simeq {\log }_{2}N$. Trial division up to $\sqrt{N}$ is exponential in $n$; advanced classical algorithms do substantially better, but no general polynomial-time classical factoring algorithm is known. The heuristic general-purpose general number field sieve has subexponential rather than polynomial scaling, roughly $\exp (O(n^{1/3}(\log n{)}^{2/3}))$. This describes known algorithmic performance, not a proof that efficient classical factoring is impossible or that every large integer is difficult.

Choose $a$ with $1<a<N$. A nontrivial greatest common divisor $\gcd (a,N)$ already supplies a factor; otherwise find the multiplicative order $r$ of $a$ modulo $N$. If $r$ is even and $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, thenMinimality of the order also excludes $a^{r/2}\equiv 1(\mathrm{mod}N)$, so factor extraction from an even modular order gives nontrivial factors through $\gcd (a^{r/2}\pm 1,N)$. Unhelpful choices of $a$ or odd orders require another trial. For $N=15$, $a=2$ has successive residues $1,2,4,8$ and order four, givingComputing the powers is easy by repeated squaring; discovering a large order is the step accelerated by Shor's algorithm.^[ref]

Put $Q=2^L$ and suppose $Q\ge r$. For each residue class $s=0,\dots ,r-1$, letThese are normalized uniform superpositions of the arguments with the same modular-exponentiation value. Their amplitudes repeat at separation $r$ within the finite register window. Exact cyclic periodicity requires $r\mid Q$. The correctly normalized entangled register state isThe equal prefactor $1/\sqrt{r}$ in the displayed algorithm is exact when $r\mid Q$, for then every $n_s=Q/r$. It is not generally exact for an arbitrary unknown order. A physical implementation uses quantum modular exponentiation as a reversible map; its specified action on second-register input zero is extended to a unitary operator on the whole register space.

For the illustrative $N=15$, $a=2$ and $Q=16$, the four first-register states areApplying the positive-sign quantum Fourier transform to the general state givesThe bracket is a finite geometric Fourier amplitude. If $r\mid Q$, it vanishes unless $k=\ell Q/r$ for $\ell =0,\dots ,r-1$, when it equals $Q/r$. HenceThe second-register states are orthogonal, so their different phases do not change the marginal first-register probabilities. Measurement givesIn the $Q=16$ example the possible outcomes are $0,4,8,12$. A nonzero observed ratio $k/Q$ estimates $\ell /r$, not a prime factor directly. Reducing it gives denominator $r/\gcd (\ell ,r)$; repeating avoids uninformative outcomes or recovers missing order factors. For example, $k=4$ or $12$ gives denominator four, whereas $k=8$ alone gives only two.

When $r\nmid Q$, the Fourier probabilities have narrow peaks near $k/Q=\ell /r$ instead of support only on an exact reciprocal grid. The general marginal distribution isChoosing $Q\ge N^2$ supplies the usual precision for continued-fraction recovery in quantum order finding: a nearest grid sample differs from the target rational by at most $1/(2Q)<1/(2r^2)$. Candidate denominators and extracted divisors are checked classically, and repetitions provide useful samples. The small $Q=16$ example works exactly because its order divides the register size; it is not a general precision guarantee for factoring every four-bit integer.

A sufficiently large reliable quantum computer would undermine RSA by efficient factorization. The related discrete-logarithm algorithm also threatens Diffie-Hellman key exchange and elliptic-curve public-key schemes. This does not imply that every communication scheme or symmetric cipher is broken by the same algorithm; post-quantum cryptography studies alternatives based on other problems. The mathematical speedup assumes a scalable quantum computation with enough precision and error control, not merely a small demonstration of factoring fifteen.

Put $d=2^N$ and $\lambda =e^{2\pi i/d}$, with nonnegative integer $N$ so the register exists. The geometric sum satisfiesConsequently the matrix $F_{+}$ with entries $d^{-1/2}{\lambda }^{jk}$ has $F_{+}^{\ast }{F}_{+}=I$. This proves unitarity andFor a binary output string $j={\sum }_{r=1}^N{j}_r{2}^{N-r}$, expansion of the printed tensor product gives coefficientThus the printed product is exactly $F_{+}|k⟩$. It is a correct product decomposition of a Fourier phase state, but the printed recovery identity has inconsistent signs:by the square of the quantum Fourier transform. To recover $f(j)$ instead, use $F_{-}=F_{+}^{\ast }$, replacing every product phase by its complex conjugate. Equivalently one may reverse the sign in the definition of $\hat{f}$. The discrepancy is visible for $d\ge 4$ by taking $f$ concentrated at $1$: the printed expression returns the basis vector at $d-1$. The recovery display also uses $k$ as the summation variable on its right while its summand uses $j$; that dummy variable should be $j$.

For factorization first check $\gcd (3,91)=1$. Successive residues areThe first return is $\boxed{r=6}$. Its half power is $3^3=27$, which is neither $1$ nor $-1$ modulo $91$. Therefore

In Shor's algorithm prepare a uniform exponent register of size $Q=2^n$, conveniently $91^2\le Q<2\cdot 91^2$, and reversibly compute $3^x\mathrm{mod}91$ into a second register. Measuring that second register, or tracing it out, leaves periodic exponent correlations of period $r$. Conditional on one measured residue, the first register is a superposition over an arithmetic progression of exponents separated by $r$. The quantum Fourier transform converts this periodic structure into peaks near $k/Q=s/r$. Continued fractions recover $s/r$; when $s$ is coprime to $r$, its denominator is $r$. Verify by modular exponentiation and repeat when the reduced denominator is insufficient. For this example $Q=16384$ is suitable, and useful peaks include those near $Q/6$ and $5Q/6$. Either transform sign gives the same period information, so the source's inverse-sign error does not invalidate the order-finding mechanism.

Put $d=2^N$ and $\lambda =e^{2\pi i/d}$, with nonnegative integer $N$ so the register exists. The geometric sum satisfiesConsequently the matrix $F_{+}$ with entries $d^{-1/2}{\lambda }^{jk}$ has $F_{+}^{\ast }{F}_{+}=I$. This proves unitarity andFor a binary output string $j={\sum }_{r=1}^N{j}_r{2}^{N-r}$, expansion of the printed tensor product gives coefficientThus the printed product is exactly $F_{+}|k⟩$. It is a correct product decomposition of a Fourier phase state, but the printed recovery identity has inconsistent signs:by the square of the quantum Fourier transform. To recover $f(j)$ instead, use $F_{-}=F_{+}^{\ast }$, replacing every product phase by its complex conjugate. Equivalently one may reverse the sign in the definition of $\hat{f}$. The discrepancy is visible for $d\ge 4$ by taking $f$ concentrated at $1$: the printed expression returns the basis vector at $d-1$. The recovery display also uses $k$ as the summation variable on its right while its summand uses $j$; that dummy variable should be $j$.

For factorization first check $\gcd (3,91)=1$. Successive residues areThe first return is $\boxed{r=6}$. Its half power is $3^3=27$, which is neither $1$ nor $-1$ modulo $91$. Therefore

In Shor's algorithm prepare a uniform exponent register of size $Q=2^n$, conveniently $91^2\le Q<2\cdot 91^2$, and reversibly compute $3^x\mathrm{mod}91$ into a second register. Measuring that second register, or tracing it out, leaves periodic exponent correlations of period $r$. Conditional on one measured residue, the first register is a superposition over an arithmetic progression of exponents separated by $r$. The quantum Fourier transform converts this periodic structure into peaks near $k/Q=s/r$. Continued fractions recover $s/r$; when $s$ is coprime to $r$, its denominator is $r$. Verify by modular exponentiation and repeat when the reduced denominator is insufficient. For this example $Q=16384$ is suitable, and useful peaks include those near $Q/6$ and $5Q/6$. Either transform sign gives the same period information, so the source's inverse-sign error does not invalidate the order-finding mechanism.

The Part C inverse-transform display also prints $j$ as its summation index while the summand uses $k$; that sum must be over $k$, as in the corrected inverse above.

Cryptography intended to remain secure against adversaries with quantum computers. It includes classical algorithms based on problems other than the integer factorization and discrete logarithm problems efficiently treated by Shor's algorithm. A candidate's security still depends on its precise construction, parameters and known attacks; the label alone is not a proof. It is distinct from requiring quantum hardware for quantum key distribution.