Period of modulo exponentiation function from factors

Question

The calculation of the period of the "modulo exponentiation" function: $$ f_a(r) = a^r (mod \ N) $$ is a step of the quantum algorithm for factorizing $N$, where $a$ is a number chosen with some limitation. The quantum circuit is able to find the period of $f(r)$ in time polynomial in the number of bits of $N$. This allows us to calculate the factors of $N$ in polynomial time.

I'm looking for an inverse relation. Is it possible to find the period, from the knowledge of the factors of $N$ (or even $N-1$), with a classical calculation, in polynomial time? Here, "period" means the minimum $r$ satisfying the equation $a^r=1 (mod \ N)$.

If the factors are not enough, I would like to know if there is any other characterization of $N$ that allows us to calculate the period in polynomial time. This latter question is quite vague, since the period itself can be seen as a "characterization" of $N$; to make it more precise, I specify that I'm looking for a "characterization" in the form of a set of numbers $v_i$, depending on $N$ but not on $a$, such that the period of $f_a(r)$ can be calculated in polynomial time from $v_i$ and $a$.

I know that there are several results in number theory connected to this problem, e.g. if $N$ is prime then $r$ divides $N-1$, but I was not able to find a general recipe that always works in polynomial time, nor to show that it is not possible.

Answer 1

The quantity $r$ is known as the order of $a$ in the multiplicative group $\mathbb{Z}^*_N$. The order of the group is $\phi(N)$, which you can compute if you know the factorization of $N$. Next, you need to factor $\phi(N)$, say $\phi(N) = \prod_{i=1}^m p_i^{d_i}$. For each $i$, find the largest $e_i$ such that $a^{\phi(N)/p_i^{e_i}} \equiv 1 \pmod{N}$. The order of $a$ is then $\prod_{i=1}^m p_i^{d_i-e_i}$. This works since $\mathbb{Z}^*_N$ is an Abelian group which decomposes as a direct group of Abelian groups of orders $p_1^{d_1},\ldots,p_m^{d_m}$.

When $N$ is prime, $\phi(N) = N - 1$, and so all you need to know is the factorization of $N - 1$.