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.
Quick algorithm for computing orders mod n?
5
$\begingroup$
number-theory
algorithms
modular-arithmetic
-
4The 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$. – 2011-10-22
-
3There's a sketch of a method in [Bach and Shallit](http://books.google.com/books?id=iJx1lP9ZcIkC&pg=PA337). See [Cohen](http://books.google.com/books?id=hXGr-9l1DXcC&pg=PA25) as well. – 2011-10-22