Reference Request for Methods of the Calculation of Order

Question

What are the standard methods of calculation of the order modulo $n$ of an integer $a$ where $\operatorname{gcd}(a,n)=1$?

Answer 1

I'm not an expert, but I think there's a "baby step giant step" method, when $n$ is too large for brute force to be effective.

If you know the factorization of $\phi(n)$ already, though, then you can find the order by calculating $a^k$ modulo $n$ for increasingly small divisors $k$ of $\phi(n)$. For example, take $a=342$ and $n=803=73\cdot11$, so that $\phi(n) = 720 = 2^4\cdot3^2\cdot5$. We know the order of $342 $ must divide $720$, and indeed we compute that $342^{720}\equiv1\pmod{803}$. Now we start peeling of prime factors of the exponent one at a time: by the computations \begin{align*} 342^{360}&\equiv1\pmod{803}\\ 342^{180}&\equiv1\pmod{803}\\ 342^{90}&\equiv364\pmod{803}, \end{align*} we conclude that the order of $342$ divides $180$ but not $90$ (in other words, $2^2$ divides the order but $2^3$ doesn't). Similarly, $$ 342^{60}\equiv738\pmod{803} $$ shows that the order of $342$ divides $180$ but not $60$ (in other words, $3^2$ divides the order). Finally, $$ 342^{36}\equiv1\pmod{803} $$ shows that the order is a divisor of $36$ (in other words, $5$ doesn't divide the order). We have thus pinned down the order of $342$ modulo $803$ to be exactly $36$.

Answer 2

See this section from Computational Number Theory by Abhijit Das, 1.7.2. "We do not know any efficient algorithm for computing ${\rm ord}_m a$ unless the complete prime factorization of $\phi(m)$ is provided." He gives a pretty easy algorithm which I used as the basis for my C code. Note that you can use the Carmichael Lambda instead of the totient which will be more efficient.

Pari's implementation is in src/basemath/arith1.c. I'm not going to try to reverse engineer it, but the first step is factoring $n$ so it looks like it is doing something similar. Edit: it looks like it's doing more-or-less Algorithm 1.4.3 from Cohen (no surprise) though with some tweaks. Menezes's Algorithm 4.79 looks the same as Cohens.