Finding the order of a given element in a cyclic group

Question

Following on from my own example question in one of my previous posts I now want to better understand how to find the order of an element in a cyclic group G.

So in my previous example we had the group $G = \mathbb{Z}_{59}^{\times}$

I want to work out the order of 11 in group G. How would one compute and calculate this?

So far, I assume that you do 11^1 mod 59, 11^2 mod 59, 11^3 mod 59,..., 11^n mod 59 = 0?

Would be amazing to see how this would be computed and what other capabilities cyclic groups have

Answer 1

If you just want to compute the order of $11\pmod {59}$:

Note that $58=2\times 29$ so the possible orders are $1,2,29,58$. Easy to see that $11^2\equiv 3 \pmod {59}$ so we just need to consider $11^{29}$.

To do that we remark that $$11^2\equiv 3\implies 11^4\equiv 9\implies 11^8\equiv 22$$

(all congruences $\pmod {59}$ of course).

Continuing we have $$11^{16}\equiv 22^2\equiv 12$$

And now we get $$11^{24}\equiv 11^{16}\times 11^8\equiv 12\times 22\equiv 28$$

And then $$11^{29}\equiv 11\times 11^4\times 11^{24}\equiv 11\times 9\times 28\equiv 58\equiv -1$$

Thus we have eliminated all the possible orders except $58$ so the order of $11\pmod {59}$ is $58$.

Note: there's nothing unique about the preceding calculations. This path looked short to me, but there might well be others as good or better.

Answer 2

To the general question: I don't think you're going to get an answer as simple as you want. For background, see Wikipedia: Multiplicative order .

For the complexity of a mature algorithm, see https://rosettacode.org/wiki/Multiplicative_order and this previous answer: Algorithms for finding the multiplicative order of an element in a group of integers mod m

Answer 3

Worth note: Shanks baby-giant step works in a group knowing only an order bound, e.g. $\!\!\bmod 59\!:$

$\qquad\,\ \begin{array}{c | c } r & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 11^{\large r}\! & 1 & 11 & 3 & 33 & 9 & \color{#0a0}{40} & 27 & \color{#c00}2 \end{array}\ $ via $\ 11^{\large\color{} 2}\equiv 3\,$ so $\!\!\begin{align}&\ \ 1\to \ \ 3\to\ 9\, \ldots\\ &\ \ \ \ \ \ 11\to 33\to 99\!\equiv\! \color{#0a0}{40}\,\ldots\end{align}$

$\qquad\ \ \, \begin{array}{c | c } q & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \color{#c00}2^{\large q} & 2 & 4 & 8 & 16 & 32 & 5 & 10 & 20 & \color{#0a0}{40} \end{array}\ $ as above, all trivial modular writhmetic.

Hence $\, 11^{\large 5} \equiv \color{#0a0}{40}\equiv 2^{\large 9}\equiv (11^{\large 7})^{\large 9}\,\Rightarrow\, \bbox[6px,border:1px solid #c00]{1\equiv 11^{\large 63-5}\equiv 11^{\large 58}}$

and $58$ is the least, else for smaller $\,7q\!-\!r\!:\ 11^{\large 7q-r}\equiv 1\,\Rightarrow\, 2^{\large q}\equiv 11^{\large r}$ contra table values.

This may be faster than the other methods since here all arithmetic is trivial $ $ [$2\cdot n\,$ or $\,3\cdot n$].

But generally this method will be less efficient than using divisibility constraints and/or deeper ideas (e.g. the Order Test implicitly used in lulu's answer or, by Euler's criterion $\,11^{\large 29}\!\equiv (11\,|\,58)\equiv -1\,$ by a quick Legendre symbol computation). However, the baby-giant step method is well-worth knowing since it proves useful in various contexts.

See here for general algorithms for order computation (some of which use this and related ideas).