Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
3  
There's a sketch of a method in Bach and Shallit. See Cohen as well. –  J. M. Oct 22 '11 at 18:41

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.