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)?
Best Answer
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.