Computing $$\varphi (N)$$ for an RSA module with a single quantum query
Luis Victor Dieulefait, Jorge Jiménez Urroz · Quantum Information Processing · 2025
Abstract In this paper, we give a polynomial time algorithm to compute $$\varphi (N)$$ φ ( N ) 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 }}$$ 1 - 1 N 1 / 2 - ϵ , where $$\epsilon $$ ϵ is any small positive constant.