Is there a better way of finding the order of a number modulo $n$? [duplicate]

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

Here we calculate the order of $2$ in $(\mathbb{Z}/{41}\mathbb{Z})^\times$.

Note: When calculating you can use the previous work to your advantage. To really cut down on the calculations, if you know the order is greater than or equal $10$, once you calculate $2^{10} \pmod{41}$ you are done,

$\quad 2^{10} \equiv 1 \pmod{41} \quad \text{order is } 10$
$\quad 2^{10} \equiv 40 \pmod{41} \quad \text{order is } 20$
$\quad \text{NOT }[2^{10} \equiv 1, 40 \pmod{41}] \quad \text{order is } 40$

Work Summary : $2^1 \equiv 2 \pmod{41}$.

The order of $2$ is one of $2,4,8,5,10,20,40$.

Work Summary : $2^2 \equiv 4 \pmod{41}$.

The order of $2$ is one of $4,8,5,10,20,40$.

Work Summary : $2^4 \equiv 16 \pmod{41}$.

The order of $2$ is one of $8,5,10,20,40$.

Work Summary : $2^5 = \equiv 32 \pmod{41}$.

The order of $2$ is one of $8,10,20,40$.

Work Summary : $2^8 \equiv 10 \pmod{41}$

The order of $2$ is one of $10,20,40$.

Work Summary : $2^{10} \equiv 40 \pmod{41}$

The order of $2$ is one of $20,40$.

Work Summary : $2^{20} \equiv 1 \pmod{41}$

The order of $2$ is equal to $20$.