Average number of different roots

The probability of a random polynomial (mod n) of degree k having i roots is $\frac{D_{k,i}}{k!}+O(1/n)$. D_k,i are called the rencontre numbers. D_k,1/k! is the limiting value when n grows of the number of polynomials which will have a single root, and hence suitable for computing signatures. A description of these numbers can be found in [2] pp. 65. The exponential generating function for them is

$$\frac{e^{-x}(1+x^3)}{(1-x)(1-x^2)} = \sum_{k=0}^{\infty} \frac{D_{k+1,1}x^k}{k!}$$

The limiting value, when the degree of the polynomial grows, is $\lim_{k \rightarrow \infty} \frac{D_{k,1}}{k!} = e^{-1}$. In other words, for random polynomials of high degree and for large size fields, 36.79% of the time these polynomials will have a single root suitable for use as a signature.

If we have more than one linear factor for all the values of n that we are prepared to try (notice that for polynomials of degree 2 we either have two linear factors or none), then we have multiple choices. Whenever we have multiple choices we have to compute all signatures arising from them. So if we have a square root and an algebraic number which factors in no less than 3 linear terms we will have to compute $2 \times 3 = 6$ signatures.

If all the signatures are $S_n(e) \neq 0$ the expression is not zero. If all S_n(e)=0 then the expression is identically zero with some probability of error. Else we cannot decide and the procedure fails.

Example. Let $\alpha$ and p(x) be defined as before. The following is a standard normalization of a rational expression containing algebraic numbers:

$$\frac{\alpha^5-1}{\alpha^2-2} = -4/5\alpha^2+21/5\alpha-5$$

To compute the signature of these expressions, we need to find an n for which p(x) factors with only one linear factor. n=5 will fail to compute some fractions on the right hand side. For n=7, p(x) does not factor. For n=11,

$$p(x) = (x+5)(x^2+6x+1) \pmod{11}$$

has a single linear factor and we decide to use it. So we set $S_{11}(\alpha)=6$ and

$$\frac{6^5-1}{6^2-2} = -4/5 \times 6^2+21/5 \times 6-5 = 9 \pmod{11}$$

as expected.