Exponentials, e^x

Next we will add exponentials to our repertoire of expressions for which we can compute signatures. The signature of e^x will be computed as

$$S_n(e^x) = S_n(e)^{S_{\phi(n)}(x)} \pmod{n}$$

where S_n(e) is arbitrarily chosen to be a primitive root (mod n) and $\phi(n)$ is Euler's totient function.

Over rational expressions of polynomials, the only relations that S(e^a) has to follow are: S(e⁰) = 1 and S(e^a+b) = S(e^a) S(e^b). These are satisfied with the above definition.

S(e^a) should also satisfy a negative condition, which is that there is no relation $e^x \neq P(x) / Q(x)$ for any finite-degree polynomials P(x) and Q(x). This can be proved over the reals by showing that the expansion of Q(x)e^x will have a term with degree higher than the degree of P(x), and hence for sufficiently large x, |Q(x)e^x| > |P(x)|.

This property should also be maintained over (mod n). To prove this we make use of the operator $\Delta P(x) = P(x+1)-P(x)$. Now, each time that we apply $\Delta$ to a polynomial, we reduce its degree by one. So

$$\Delta^{d+1} P(x) = 0$$

where d is the degree of P(x). $\Delta$ applied to powers (mod n) gives:

$$\Delta E^x = E^{x+1} - E^x = (E-1)E^x$$

or

$$\Delta^{d+1} E^x = (E-1)^{d+1}E^x \neq 0$$

Suppose that P(x) and E^x are claimed to be identical, then if the degree of P(x) is not higher than n-2, we compute the sequence P(0), P(1), ... , P(d+2). The $\Delta^{d+1}$ of this sequence is 0, and if it were equal to the sequence E⁰, E¹, ... E^d+1 it would be non-zero, so there cannot be a polynomial that has identical signatures to E^x. The extension to rational polynomials is by observing that the $\Delta^{d+1}(Q(x)E^x) \neq 0$ too.

Choosing S(e) to be a primitive root guarantees that the range of the signatures S(e^x) is as large as possible, i.e. there will be $\phi(n)$ different possible values for the signature. An extremely small range would force us to reconsider the probability bounds, in particular if we were computing with polynomials on exponentials.