Arbitrary powers

The signature of an arbitrary power can be computed as

$$S_n(a^b) = S_n(a)^{S_{\phi(n)}(b)}$$

where $\phi(n)$ is Euler's totient function or the number of divisors of n. This is necessary to guarantee that the relation S_n( a^b+c ) = S_n(a^b) S_n(a^c). It is a consequence of Fermat's little result, that $a^{\phi(n)} = 1 \pmod{n}$. The signatures of exponents will be computed mod $\phi(n)$, a value which may have some undesirable properties. E.g. $2 \vert \phi(n)$ for any n, and hence $S_n( a^{\frac{1}{x(x+1)}} )$cannot be computed.

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 $\phi(n)$, we test whether $S_n(a)^{\frac{\phi(n)}{k}} = 1 \pmod{n}$. If it is 1, then S_n(a) is a k^th power, and it will be a generator of at most $\phi(n)/k$ values. By trying all the primes factors of $\phi(n)$ we can find the maximum k for which $S_n(a)^{\frac{\phi(n)}{k}} = 1 \pmod{n}$. If $k \neq 1$ signatures of the exponents should be computed (mod $\frac{\phi(n)}{k}$). This is not only more efficient, but could remove unwanted factors from $\phi(n)$ which may otherwise prevent signature computation.