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

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

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.