Computing $$\varphi (N)$$ for an RSA module with a single quantum query

Abstract In this paper, we give a polynomial time algorithm to compute $$\varphi (N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>φ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for an RSA module N using as input the order modulo N of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least $$1-\frac{1}{N^{1/2-\epsilon }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> </mml:mfrac> </mml:mrow> </mml:math> , where $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> is any small positive constant.