Let be odd
and even.
= \cdot
SVG: MathML:
\mathcal{A}
SVG
SVG
PNG
PNG
SVG
SVG
SVG
SVG
<math>
q(v)=|v|^2
</math>
MathML/MathJax SVG
<math>
q(v)=\|v\|^2
</math>
MathML/MathJax SVG
<math>
q(v)=\|v\|_A
</math>
MathML/MathJax SVG
<math>
x^2
</math>
MathML/MathJax SVG
<math>
(v)^2
</math>
MathML/MathJax SVG
SVG: MathML:
SVG: MathML:
<math>
\cancel{y}
</math>
MathML/MathJax SVG
<math>
\cancel{x}
</math>
MathML/MathJax SVG
<math>
\cancel{xyz}
</math>
MathML/MathJax SVG
let be odd
and even.
Pick a random number .|Compute , the greatest common divisor of and .|If , then is a nontrivial factor of , with the other factor being and we are done.|Otherwise, use the quantum subroutine to find the order of .|If is odd, then go back to step 1.|Compute . If is nontrivial, the other factor is , and we're done. Otherwise, go back to step 1.
}}It has been shown that this will be likely to succeed after a few runs.[1] In practice, a single call to the quantum order-finding subroutine is enough to completely factor with very high probability of success if one uses a more advanced reduction.[2]