where is Euler's totient function or the number of divisors of

For this reason it is important to find out if *S*_{n}(*a*) is a
primitive root or not.
This can be done with an efficient test.
For every prime factor *k* of , we test whether
.
If it is 1, then *S*_{n}(*a*) is a *k*^{th} power, and it will
be a generator of at most values.
By trying all the primes factors of we can find
the maximum *k* for which
.
If signatures of the exponents should be computed
(mod
).
This is not only more efficient, but could remove unwanted factors
from which may otherwise prevent signature computation.