next up previous
Next: Complex numbers Up: Modular mappings Previous: Real numbers

Arbitrary powers

The signature of an arbitrary power can be computed as

\begin{displaymath}S_n(a^b) = S_n(a)^{S_{\phi(n)}(b)} \end{displaymath}

where $\phi(n)$ is Euler's totient function or the number of divisors of n. This is necessary to guarantee that the relation Sn( ab+c ) = Sn(ab) Sn(ac). 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 Sn(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 Sn(a) is a kth 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.


next up previous
Next: Complex numbers Up: Modular mappings Previous: Real numbers
Gaston Gonnet
1999-07-04