# Order of element in multiplicative group modulo n, where n is not prime

I should calculate order of a givent element of multiplicative group modulo n. This n might, or might not be a prime.

I discovered that I can use algorithm 4.79 from Handbook of Applied Cryptography to do that:

The thing is, I need to know order of the group itself as input for this algorithm. For a group where n is prime, this is easy, the order is n-1. But what if n is a composite number? Do I really have to calculate the Euler totient function (as suggested here) to determine the order of the group and then use this algorithm to calculate the order of the element? Or am I somehow able to calculate the order of a given element based on just factorization of n (teacher suggested this should be possible)?

• Do you know how to compute $\varphi(n)$ from a factorization of $n$? The link you gave links to a page giving a general formula in terms of the factorization of $n$. – Eric Towers Nov 5 '16 at 16:10
• No, I don't, that's the thing. – Honza Kalfus Nov 5 '16 at 16:11

You link to the "Multiplicative group modulo n" page on Groupprops. That page references the "Euler-phi function" with a link to the "Euler totient function" page on Groupprops. That page has an "Explicit formula" section with $$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p} \right)$$ (although the cited page indicates "$p \mid n$" with the words "over all distinct prime factors of $n$").

Thus, the reference you give tells you how to compute $\varphi(n)$ from a prime factorization of $n$. The method given is relatively fast.

• Actually, the formula is different, but it is in the "Explicit formula" section of the page and it works! Thanks! – Honza Kalfus Nov 5 '16 at 16:31
• And over just p, not p|n :) – Honza Kalfus Nov 5 '16 at 16:33
• @arctictern : Fixed further. It is clearly time for me to back away from the keyboard... – Eric Towers Nov 5 '16 at 16:33
• @HonzaKalfus : '[T]he cited page indicates "$p \mid n$" with the words "over all distinct prime factors of $n$"'. – Eric Towers Nov 5 '16 at 16:34
• Ah, right, I get it :) – Honza Kalfus Nov 5 '16 at 16:36

Hint Use the Chinese Remainder Theorem.

By the CRT, if $$n=p_1^{e_1}...p_k^{e_k}$$ then the order of $a$ modulo $n$ is the least common multiple of the order of $a$ modulo $p_j^{e_j}$.