# Quick algorithm for computing orders mod n?

Is there a fast way to compute the order of $a \pmod n$ without computing potentially all the powers of $a$ up to $n-1$? For example, in computing the order of $87 \pmod {101}$, the naïve way could require computing up to $87^{100}$, which I want to avoid.

-
The order has to divide $\phi(n)$ where $\phi$ is the Euler totient function. That greatly reduces the number of potential powers for reasonably sized $n$. – Brandon Carter Oct 22 '11 at 18:24
There's a sketch of a method in Bach and Shallit. See Cohen as well. – J. M. Oct 22 '11 at 18:41

$\phi(101) = 100$, so the order of $87$ must be a factor of $100$: $2, 4, 5, 10, 20, 25, 50,$ or $100$. So you only have to compute up to $87^{50}$ to get your answer $-$ if none of these is $1$, then the order of $87$ must be $100$. But this simple method can be implemented more or less efficiently:

If you simply calculate $87^k$ for $2 \le k \le 50$, you need 49 multiplications mod $101$. But as you probably know, you can calculate powers much more efficiently by repeated squaring. If you keep track of things properly, you can calculate $87^2, 87^4, 87^5, 87^{10}, 87^{20}, 87^{25},$ and $87^{50}$ in a single repeated-squaring chain:

$x = 87$
$p_5 = p_{25} = x$
$x \leftarrow x^2 = 87^2 \mod 101$
$p_2 = p_{10} = p_{50} = x$ (now $p_2 = 87^2 \mod 101$)
$x \leftarrow x^2 = 87^4 \mod 101$
$p_5 \leftarrow p_5 \times x$ (now $p_5 = 87^5 \mod 101$)
$p_4 = p_{20} = x$ (now $p_4 = 87^4 \mod 101$)
$x \leftarrow x^2 = 87^8 \mod 101$
$p_{10} \leftarrow p_{10} \times x$ (now $p_{10} = 87^{10} \mod 101$)
$p_{25} \leftarrow p_{25} \times x$
$x \leftarrow x^2 = 87^{16} \mod 101$
$p_{20} \leftarrow p_{20} \times x$ (now $p_{20} = 87^{20} \mod 101$)
$p_{25} \leftarrow p_{25} \times x$ (now $p_{25} = 87^{25} \mod 101$)
$p_{50} \leftarrow p_{50} \times x$
$x \leftarrow x^2 = 87^{32} \mod 101$
$p_{50} \leftarrow p_{50} \times x$ (now $p_{50} = 87^{50} \mod 101$)

If I have that right, then instead of $49$ multiplications, we only need five squarings and seven multiplications. And this method generalises very well to large integers, with better and better speed-ups for larger and larger numbers.

-