# Period of modulo exponentiation function from factors

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.

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$$.