# Is there a better way of finding the order of a number modulo $n$?

Say I wish to find the order of 2 modulo 41.

The way I've been shown to compute this is to literally write out $2^k$ and keep going upwards with $0 \leq k \leq 41$, or until I observe periodicity in the sequence, and then state the order from there.

Is there a better way of deducing the order of a number with respect to some modulo?

This seems highly inefficient, especially if we are working with respect to some large modulo $N$ where it will take at most $N$ computations to determine when periodicity occurs.

• Since $41$ is prime, the order must be a factor of $40$ – Empy2 Nov 17 '14 at 6:49
• I did not know this, but thanks for that. Very useful. Perhaps a bad example, what if $n$ is NOT prime? Are there any results that can further 'filter' it out? Also, say we know the order must be a factor of 40, then is there a systematic way of computing the order without having to bash out any numbers? – Trogdor Nov 17 '14 at 6:51

## 2 Answers

For any $a$ and $N$ with $\gcd(a,N)=1$, the order of $a$ modulo $N$ must be a divisor of $\varphi(N)$. So if you know the prime factorization of $N$ (or $N$ is already prime) so that you can compute $\varphi(N)$ and also know the prime factorization of $\varphi(N)$, you can proceed as follows:

If we knwo an integer $m>1$ with $a^m\equiv 1\pmod N$ and know the prime divisors of $m$, for all primes $p$ dividing $m$ do the following: Compute $a^{m/p}\bmod N$ and if the result is $\equiv 1\pmod N$, replace $m$ with $m/p$ and repeat (or switch to the next prime divisor if $m$ is no longer divisible by $p$). When you have casted out all possible factors, the remaining $m$ is the order of $a$. Note that the computations $a^m\bmod N$ do not require $m$ multiplications, but rather only $O(\log m)$ multiplications mod $N$ if we use repeated squaring.

If $N$ is large and the fatorization of $\varphi(N)$ is known (and especially if you suspect the order of $a$ to be big), this is in fact a fast method.

Note that a couple of computations can be saved even beyon what is descibed above: In the case $p=2$, we may end up computing $a^m, a^{m/2}, a^{m/4},\ldots$ to cast out factors of $2$. But the later numbers were in fact intermediate results of computing $a^m$ by repeated squaring! Also, once we notice for some $p$ with $p^k\mid m$ that $a^{m/p}\not\equiv 1\pmod N$, we can save a few squarings and so speed up the task for the remaining primes if we replace $a$ with $a^{p^k}\pmod N$ and $m$ with $m/p^k$ - just remember to multiply the factor $p^k$ back into the final answer!

In your specific example, we know that $N=41$ is prime and that $\varphi(N)=40=2^3\cdot 5$. We check $p=5$ and note that $2^{40/5}=256\equiv 10\pmod{41}$, hence the factor $5$ cannot be eliminated. After that we check how many $2$'s we have to use: $2^5\equiv 32\equiv -9$, hence $2^{10}\equiv 81\equiv -1$, $2^{20}\equiv (-1)^2\equiv 1$. We conclude that $2$ has order $20$ modulo $41$.

The order must be one of $1,2,4,8,5,10,20,40$.

Calculate $2^2,2^4=(2^2)^2,2^8=(2^4)^2,...\\2^5=2^4*2,2^{10}=(2^5)^2,2^{20}=(2^{10})^2,2^{40}=(2^{20})^2$ which is seven calculations.

If 41 is not prime, say $41=a^2b^3c$,then

i) calculate the order of $2\pmod{a^2}$, and the order $\pmod{b^3}$ and the order $\pmod c$
ii) calculate the lowest common multiple of the separate orders.