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

Luis Víctor Dieulefait, Jorge Urróz

In this paper we give a polynomial time algorithm to compute $\phi (N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer. This provides a new insi…