Algorithms for finding the multiplicative order of an element in a group of integers mod m What are some algorithms for finding the multiplicative order of an element in a group of integers mod m, besides the naive one?
 A: If the prime factorization of $\lambda(m)\;$ or $\varphi(m)\;$ is known there are effective algorithms, see e.g. 
Algorithm 1.4.3 in H. Cohen's book A Course in Computational Algebraic Number Theory. A better available source maybe Algorithm 4.79: Determining the order of a group element from Applied Cryptography  by A.J. Menezes et al. (you can download a pdf of ch. 4 from http://cacr.uwaterloo.ca/hac/).
A: Here is a solution, it seems to be very similar to the one in the book mentioned by user61216 . whether you want to do it for $m$ directly or for the prime power factors of $m$ separately and then just take the lcm of the orders is up to you, I will assume we do it for $m$ directly. Let the element be $g$.
Let $\lambda(m) = p_1^{a_1} \dots p_k^{a_k}$.
We will now determine $v_{p_i}(o(g))$ for each $i$.
To do this firstly calculate $a=g^{\lambda(m)/p_i^{a_i}}$ using exponentiation by squaring, and then, while $a\not \equiv 1 \bmod m$ continue to raise $a$ to the $p_i'th$ power again with exponentiation by squaring. The value of $v_{p_i}( o(g) )$ is equal to the number of times you had to raise to the $p_i'th$ power.
