7.3.1 Finding the Group Exponent

As explained in Section 7.1.2, we recall that the exponent of a group is the smallest nonnegative integer ? such that x ^? = 1 for all x in the group (assuming that the group is multiplicatively denoted). For cyclic groups, the exponent is obviously the order of the group. For instance in Z _n (which is additively denoted), the exponent is n since n is the smallest x such that x.1 ? 0 (mod n) and we have n.x ? 0 (mod n) for any x ? Z _n.

In the case of , ? is denoted ?( n) as the Carmichael function. We can easily prove that if n = is the factorization of n, then

which should be compared to

Finding the exponent of is not easy. It is actually as hard as factoring n: obviously, the factorization of n allows to compute ?( n) by the above formula. The opposite is a little more subtle. Let us assume that we can compute ? = ?( n) and let us factorize n.

Let us first take an example with n = pq with p and q different primes such that p ? q ? 3 (mod 4). This way we have