Over rational expressions of polynomials, the only relations that S(ea) has to follow are: S(e0) = 1 and S(ea+b) = S(ea) S(eb). These are satisfied with the above definition.
S(ea) should also satisfy a negative condition, which is that there is no relation 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)ex will have a term with degree higher than the degree of P(x), and hence for sufficiently large x, |Q(x)ex| > |P(x)|.
This property should also be maintained over (mod n).
To prove this we make use of the operator
Now, each time that we apply to a polynomial, we reduce
its degree by one.
Choosing S(e) to be a primitive root guarantees that the range of the signatures S(ex) is as large as possible, i.e. there will be 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.