4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Since $41$ is prime, the order must be a factor of $40$ $\endgroup$
    – Empy2
    Nov 17, 2014 at 6:49
  • $\begingroup$ 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? $\endgroup$
    – Trogdor
    Nov 17, 2014 at 6:51

3 Answers 3

9
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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