One of the fundamental elements of Shor's algorithm is the calculation of the function: $$ f_a(r) = a^r (mod \ N) $$ where $N$ is the number to be factored and $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$ and $N-1$, with a classical calculation, in polynomial time? (EDIT: here "period" means the minimum $r$ satisfying the equation.)
If not, 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.