1.0 Basic Propositions on Symmetric Pseudoprimes 

1.1 Nomenclature and Definitions 

Let Z[x] denote the set of polynomials (of finite degree) with integer coefficients. For any given monic polynomial f(x) Î Z[x] of degree d, let Z[x]_{f} denote the elements of Z[x] modulo f. This signifies that two elements u(x), v(x) of Z[x] are equivalent in Z[x]_{f} if and only if u(x)  v(x) is divisible by f(x). 

Proposition 1: Each element of Z[q]_{f} has a unique expression of degree d1. 

Proof: Letting the modulus polynomial f(x) be 

_{} 

we see that any power of x greater than or equal to d can be expressed in terms of lower powers of x while preserving equivalence in Z[x]_{f} by making the substitution 

_{} 

Thus, every element of Z[x]_{f} can be reduced to a polyomial of degree £ d1. The reduced polynomial is unique because if any two (distinct) such polynomials were equivalent, it would imply that their difference, a nonvanishing polynomial of degree d1, is divisible by f(x), which is impossible. à 

Thus each element of Z[x]_{f} can be expressed in the form 

_{} 

where a_{i} Î Z. If the coefficients a_{k} are considered as elements of Z_{n} (that is, the integers modulo n), then the set of polynomials of this form is denoted as Z_{n}(x)_{f }. For any u,v Î Z[x] and n Î Z, the notation u = v (mod f,n) signifies that u(x) and v(x) are equivalent elements of Z_{n}[x]_{f} . 

The following generalization of Fermat's Little Theorem is the basis for the definition of a symmetric pseudoprime: 

Proposition 2: If p is a prime, then f(x^{p}) = 0 (mod f,p). 

Proof: Raising both sides of the congruence f(x) = 0 (mod f,p) to the power p, noting that all crossproduct coefficients in the multinomial expansion are divisible by p, and that c_{j}^{p} = cj (mod p), we have the result. à 

Definition 1: A positive composite integer N such that f(x^{N}) = 0 (mod f;N) is called a symmetric pseudoprime relative to f. 

An alternative definition in terms of symmetric functions is discussed in Section 1.3. 


1.2 Basis Sequence Computations 

For any nonnegative integer n there is a unique set of integers b_{k}(n) such that 

_{} 

For each k the sequence of integers b_{k}(n) (n = 0,1,2,...) is called a basis sequence of f. Each basis sequence satisfies the fundamental recurrence relation of f 

_{} 

with the initial values 
_{} 

for j = 0, 1,.., d1. 

Proposition 3: For any nonnegative integers n_{1}, n_{2},..., n_{j} and r, and for k = 0, 1,.., d1, we have the identity 

_{} 

where summation from 0 through d1 is implied over each a_{i}. 

Proof: By direct multiplication of the basis representations of each power of x we have 

_{} 

where B_{g} equals the sum of all products of the form 

_{} 

with a_{1} + a_{2} + ... + a_{j} = g. Substituting the representation for each power of x on the right side of the previous expression, the coefficient of x^{k} in the representation of _{} is given by 

_{} 

Clearly, this equality still holds if the argument of the left hand side and of the first term in the summation are both increased by any integer r. à 

Notation: Throughout this paper, whenever a Greek symbol appears both as a sequence index and in a sequence argument in a single product, summation over that symbol from 0 through d1 is implied. Similarly, whenever a Latin symbol appears both as an index and an argument in a given product, summation over that symbol from 0 through d is implied (except when other summation limits are explicitly specified). 

For computational purposes, a useful special case of (2) can be expressed using the indexargument convention as 

_{} 

By applying this formula log_{2}N times, with r equal to either 0 or 1 at each step according to the binary bits of N, we can efficiently compute the basis elements b_{j}(N) (j = 0, 1,.., d1). The quantities b_{j}(a+b+r) are fixed constants for any given recurrence, so the only full multiplications required in each evaluation of (3) are the d(d+1)/2 distinct products of the form b_{a}(n)b_{b}(n). 

Once the basis elements b_{j}(N) have been determined, the basis representations of x^{2N}, x^{3N},.., x^{dN} can be found by applying the formula 

_{} 

with k = 2, 3,.., d. With these we can determine whether N satisfies the congruence f(x^{N}) = 0 (mod f,N), which is equivalent to the set of congruences 

_{} 

If N satisfies (4), then either N is a prime or N is a symmetric pseudoprime relative to f. 


1.3 Elementary Symmetric Functions 

Let q_{1}, q_{2},... q_{d} denote the complex roots of f, let f_{n} denote the monic polynomial whose roots are the nth powers of the roots of f, and let c_{j}(n) denote the coefficient of x^{dj} in f_{n}(x). The jth elementary symmetric function of the roots of f_{n} is defined as the sum of all products of the roots taken j at a time, and is denoted by s_{j}(n). (For convenience we define s_{0}(n) = 1 for all n.) It follows that 

_{} 

Hereafter, whenever s(n) is written without subscript, it is understood to signify the first symmetric function, i.e., the sum of the kth powers of the roots of f_{n}. 

The indexargument summation convention previously defined for basis sequences also applies to both of the sequences s_{j}(n) and c_{j}(n), and to combinations of these sequences. For example, s(a)b_{a}(n) signifies the sum 

_{} 

Proposition 4: The integer N is a prime or a symmetric pseudoprime relative to f if and only if s_{j}(N) = s_{j}(1) (mod N) for j = 0, 1, .., d. 

Proof: The condition s_{j}(N) = s_{j}(1) (mod N) for j = 0, 1,.., d implies that the coefficients of f and f_{N} are congruent (mod N). Therefore, since each x^{N} is a root of f_{N}, we also have f(x^{N}) = 0 (mod f,N), proving that N is a symmetric pseudoprime relative to f. Conversely, if N is a symmetric pseudoprime relative to f, we have f(q_{i}^{N}) = 0 (mod f,N) for each root q_{i}^{N} of f_{N}, which implies that the coefficients of f are congruent to the coefficients of f_{N} (mod N). à 

In view of Proposition 4 we have the following alternative definition of symmetric pseudoprimes: 

Definition 1': Given a monic polynomial f of degree d with integer coefficients, a symmetric pseudoprime relative to f is defined as a positive composite integer N such that every elementary symmetric function of the Nth powers of the roots of f is congruent (mod N) to the same function of the first powers. 

We will occassionally compare symmetric pseudoprimes with "ordinary" pseudoprimes, defined as follows: 

Definition 2: Given a monic polynomial f of degree d with integer coefficients, an ordinary pseudoprime relative to f is defined as a positive composite integer N such that the sum of the Nth powers of the roots of f is congruent (mod N) to sum of the first powers. 

For example, if q_{1}, q_{2}, q_{3} are the roots of a cubic polynomial f, then an ordinary pseudoprime relative to f is a composite integer N coprime to 6 and such that 

_{} 

whereas a symmetric pseudoprime relative to the same cubic f is a composite integer N such that 

_{} 

Proposition 5: If N is a prime or a symmetric pseudoprime relative to f, we have s_{j}(kN) = s_{j}(k) (mod N) (j = 0, 1, .., d) for every positive integer k. 

Proof: The elementary symmetric functions of q_{i}^{k} (i = 1, 2,.., d) can be expressed as polynomials in the elementary symmetric functions of the values q_{i}. Similarly, the elementary symmetric functions of q_{i}^{Nk} (k = 1, 2,.., d) can be expressed by the same polynomials in the elementary symmetric functions of the values q_{i}^{N}. By Proposition 4 each elementary symmetric function of the q_{i} is congruent (mod N) to the same function of the q_{i}^{N}, so the elementary symmetric functions of the values q_{i}^{k} are all congruent (mod N) to the same functions of the values q_{i}^{Nk}. à 

Proposition 6: A positive composite integer N coprime to d! is a symmetric pseudoprime relative to f if and only if s(kN) = s(k) (mod N) for k = 1, 2,.., d. 

Proof: The necessity of the condition follows immediately from Proposition 5. To prove sufficiency, consider "Newton's relations" 

_{} 

for any integer n. Given the set of values s(n), s(2n),... s(dn) modulo some positive integer M, these relations uniquely determine the coefficients of f_{n} (mod M), provided that M is coprime to d! (to ensure that all the divisions by j are unique modulo M). Therefore, if s(kN) = s(k) (mod N) for k = 1, 2,.., d, it follows that the coefficients of f are congruent (mod N) to the coefficients of f_{N}, which proves that for any u Î Z[x] we have f(u) = f_{N}(u) (mod f,N). In particular, f(q^{N}) = f_{N}(q^{N}) = 0 (mod f,N), so N is a symmetric pseudoprime relative to f. à 


1.4 Reversible Sequences 

If the constant coefficient c_{d} of f equals +1 or 1, then the values of c_{1}(k) are integers for all integers k, positive and negative. In this case, the sequence c_{1}(k) and the polynomial f are both called reversible. 

Proposition 7: If N is a prime or a symmetric pseudoprime relative to f, and the coefficient c_{d} of f is coprime to N, then s_{j}(kN) = s_{j}(k) (mod N) (j = 0, 1,.., d) for every integer k, positive and negative. 

Proof: Since c_{d} is coprime to N, the fundamental recurrence relations can be solved uniquely for s(nd) and s(N(nd)) respectively, and the corresponding coefficients remain congruent (mod N). Therefore, since the two sequences have congruent initial values and congruent recurrence coefficients (mod N), the sequences are entirely congruent (mod N) in both directions, positive and negative. It follows from equation (5) that the coefficients of the polynomials f_{n} and f_{Nn} are congruent for all n, positive and negative. à 

In particular, Proposition 7 applies to every reversible sequence for any prime or symmetric pseudoprime N, because c_{d} = ±1 is obviously coprime to N. 

Proposition 8: If f is reversible, then an odd positive composite integer N coprime to (d1)! is a symmetric pseudoprime relative to f if and only if s(kN) = s(k) (mod N) for k = 1, 2,.., d1. 

Proof: The necessity follows from Proposition 7. To prove sufficiency, note that the d1 specified congruences, together with the trivial congruence s(0N) = s(0), provide a complete set of congruent "initial values" for the two sequences s(kN) and s(k). Also, by the same argument used to prove Proposition 6, "Newton's relations" uniquely determine the coefficients c_{1}( ) through c_{d1}( ) of the two recurrence relations. In addition, since c_{d} = ±1, we have c_{d}(k) = c_{d}(Nk) for every odd integer N. Thus, a complete set of initial values and all the recurrence coefficients of the two sequences are congruent (mod N), so we have s(k) = s(kN) (mod N) for every integer k. By Proposition 6, it follows that N is a symmetric pseudoprime relative to f. à 

In the following proposition and proof we use the symbol {x} signify the greatest integer less than or equal to x. 

Proposition 9: If f is reversible, then an odd positive composite integer N coprime to {d/2}! is a symmetric pseudoprime relative to f if and only if s(kN) = s(k) (mod N) for k = ±1, ±2,.., e{d/2}, where e = ±1 if d is odd and +1 if d is even. 

Proof: The coefficient c_{d}(n) of f_{n} is related to the roots of f by 

_{} 

Substituting (1)^{d}c_{d} for (q_{1}q_{2}...q_{d}) gives 

_{} 

Now, observing that the roots of f_{ n} are just the inverses of the roots of f_{n}, we have 

_{} 

Given the values of s(kN) (mod N) for k = ±1, ±2,.., e{d/2}, equation (5) uniquely determines the values (mod N) of c_{j}(N) and c_{j}(N) for j = 1, 2,.., {d/2}, provided that N is coprime to {d/2}! (to make the divisions by j unique (mod N)). Then by equation (6) we can use the c_{j}(kN) to compute the values of c_{j}(kN) (mod N) for j = {d/2} + 1, .., d. Thus, the two sequences s(k) and s(kN) have a set of d consecutive values congruent (mod N) (including the equality with k = 0), and their recurrence coefficients are all congruent, so the entire sequences are congruent (mod N). à 

For reversible sequences, the basis sequence formulas described in Section 1.2 can be extended to apply all integer arguments, positive and negative. 


1.5 Coefficient Sequences 

Although the basis sequence relations described in Section 1.2 provide an efficient and convenient means of evaluating the elements of the c_{1}(k) sequence for any given polynomial f, it is sometimes useful to have formulas expressed entirely in terms of the c_{1}(k) (or s(k)) sequence elements themselves. The fundamental recurrence for f_{n} can be written as 

_{} 

Since the value of k is arbitrary, we can set k = m + (r/n) for any integers m and r to give 

_{} 

Thus, the recurrence relation of f_{n} applies not only to the sequence c_{1}(nk) (k = 0, 1, 2,...), but also to the sequences c_{1}(nk+r) for any integer r. Furthermore, the coefficients of this recurrence relation can be expressed in terms of the c_{1}(nk) sequence elements by solving equation (5) explicitly for the c_{j}(n), which gives 

_{} 

In general, we have (Waring's formula) 

_{} 

where the summation is evaluated over all sets of m nonnegative integers a_{j} such that 

_{} 

These equations can be used to implement a log_{2}N algorithm for computing c_{1}(N). For example, we can compute the recurrence coefficients c_{k}(n) for n = 1, 2, 4, 8,.., 2s, where s = [log_{2}n], in a "bootstrap" procedure, and then use these coefficients to compute c_{1}(N). Algorithms such as this can be applied to polynomials of any degree, but they generally involve more full multiplications per step, and more elaborate bookkeeping, than the basis sequence algorithm described in Section 1.2. 

However, in some special cases it's possible to devise a coefficient sequence algorithm that is as efficient as a basis sequence algorithm. If the sequence is reversible, then the terms of c_{j}(n) in (7) can be replaced by ±c_{dj}(n) as given by equation (6). Thus, (7) can be expressed entirely in terms of the coefficient sequences c_{j}(±n) (or symmetric functions s_{j}(±n)) with j £ (d/2). This is particularly convenient for the case of a reversible cubic (see Section 1.3). 


1.6 Relations Between Basis Sequences and Symmetric Functions 

Given any sequence of values A(k) (k = 0, 1, 2,...) that satisfies the fundamental recurrence relation of f, we have 

_{} 

In particular, 
_{} 

Another expression for the first symmetric function s(n) is given by a "contraction" of the basis sequences 

_{} 

If we define the sequence of square matrices B_{n} (n = 0,1,2,..) with components given by B_{n}(i,j) = b_{j}(n+i), then s(n) can also be regarded as the trace of B_{n}. 

It follows directly from (8) that 

_{} 

If the symbols a and b are permuted in the arguments, we have the slightly less obvious identity 

_{} 

Equations (9) and (10) are just two special cases of the following proposition. 

Proposition 10: Let {i,j,..,k} be a permutation of {1,2,..,q} composed of the cyclic components C_{1}, C_{2}, .., C_{t}. Then 

_{} 

where _{} signifies the sum of all the n_{r} such that r is in the cycle C_{u}. 

Proof: Proposition 3 gives both 

_{} 

and 
_{} 

Substituting from (11) into (12) (with k = n or m) gives 

_{} 

which is just the rule of multiplication for the components of matrices. Thus, equation (12) is equivalent to the matrix product B_{n+m} = B_{n}B_{m} = B_{m}B_{n}. Setting a = b in (12) gives, by contraction, equation (9). Repeated substitutions of either (11) or (12) leads to the general result. à 

For example, the quantity 

_{} 

corresponds to the permutation [a,b,m] ® [m,b,a], the cyclic components of which are [a,m] ® [m,a] and [b] ® [b]. Thus, Proposition 10 gives the identity 

_{} 


1.7 Prime Types Relative to f(x) 

We will classify each prime p relative to the polynomial f according to how f factors in Z_{p}[x]. The type of each prime p will be denoted by a symbol of the form _{}, signifying that in the ring Z_{p} the polynomial f is the product of k_{1} irreducible factors of degree 1, and k_{2} irreducible factors of degree 2, and so on. If a subscript is zero, the term will normally be omited from the symbol. For example, if f is the product of one irreducible cubic factor and two linear factors in Z_{p}[x] we will say that p is a prime of type {1_{2}3_{1}} relative to f. 

The type of the prime p relative to f is also related to the general period of the characteristic recurrence of f (mod p), defined as the least positive integer n such that b_{j}(n) = b_{j}(0) (mod p) (j = 0, 1,.., d1). We will use the symbol t_{p} to signify the general period of f (mod p). 

Recall that Proposition 2 gives f(x^{p}) = 0 (mod f,p). By iterating the method of proof, this result can be extended to 

_{} 

for any nonnegative integer k. Thus, each number _{} is a root of f in Z_{p}[x]_{f}. 

Proposition 11: If f is irreducible in Z_{p}[x], then the sequence of values _{} (mod f,p) has a period of d, i.e., 

_{} 

Proof: If p is a prime, then Z_{p}[x]_{f} is isomorphic to the finite field of order p^{d}. It is well known that if f is irreducible in Z_{p}, then the proposition follows. à 

Since f is irreducible in Z_{p}[x], it follows that the ring of polynomials Z_{p}[x]_{f} possesses unique factorization, and therefore f has exactly d distinct factors in Z_{p}(q)[x]. 

Dividing (13) by x gives 

_{} 

This shows that t_{p} must divide p^{d1}. For some common special cases this can be further refined by noting that the values of _{} (k = 0, 1,.., d1) are the d roots of f in Z_{p}[x]_{f}. For example, since the product of the roots equals c_{d}, it follows that if c_{d} = (1)^{d}, then t_{p} divides 1 + p + .. + p^{d1} = (p^{d}  1)/(p  1). On the other hand, if c_{d} = (1)^{d}, then _{}, so t_{p} divides 2(p^{d}  1)/(p  1). 

If f is reducible in Z_{p}[x], then the general period of its recurrence divides the least common multiple of the periods of the irreducible factors. For example, if p is a prime of type {2,3} relative to f, then t_{p} divides lcm[(p^{2}  1), (p^{3}  1)]. Since p^{2}  1 and p^{3}  1 have the common factor p  1, it follows that t_{p} divides 

_{} 

In general, the sequence _{} has a period that divides the least common multiple of the degrees of the irreducible factors of f in Z_{p}[x]. Thus, we can write 

_{} 

where k_{p} is a divisor associated with the prime p. 

The number of distinct roots of f in Z_{p}[x]_{f} can exceed the degree of f if f is reducible, because then unique factorization does not hold. For example, if p is of the type {2_{1},3_{1}} relative to f, then each of the six values _{} is a distinct root of f in Z_{p}[x]_{f} . However, in related rings these six roots are not distinct. We have monic irreducible polynomials g and h of degree 2 and 3 respectively such that f = gh (mod p), and we find that the sequence _{} has period 2 in the ring Z_{p}[x]_{g} and period 3 in the ring Z_{p}[x]_{h}. Specifically we have 

_{} 

and 
_{} 

Letting a_{1},a_{2} denote the roots of g, and b_{1},b_{2},b_{3} denote the roots of h, we can say the prime p induces the permutation [a_{1},a_{2},b_{1},b_{2},b_{3}] ® [a_{2},a_{1},b_{2},b_{3},b_{1}] on the roots of f. This permutation has two cyclic components, a_{i} and b_{i}, with periods 2 and 3 respectively. The periods of the cyclic components of the permutation induced by a prime p determines the "type" of p (relative to f). Furthermore, the cyclic structure corresponding to each type determines the asymptotic proportion of primes of that type. If each of the d! possible permutations of the d roots of f is equally likely to be induced by any given prime, we can see immediately the expected asymptotic proportion of primes of each type, based on the proportion of the permutations that possess each of the cyclic structures, corresponding to the partitions of d. For example, with d = 5 there are seven possible cyclic structures: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1. The cyclic structure corresponding to "5" is just a single cycle of length 5, so the first element can go to one of four places, then one of three, then one of two, and then the one remaining place before it repeats. Hence there are 4! permutations with this cyclic structure, which implies that 4!/5! = 1/5 of all primes will be of type {5_{1}}. At the other extreme, the cyclic structure "1+1+1+1+1" is given by only one permutation, so only 1/5! = 1/120 of all primes would be splitting primes. In general, assuming each of the d! permutations is equally likely, the number of permutations for the prime type _{} is given by the multinomial coefficient 

_{} 

so the asymptotic density of each type is just 1 over the denominator. 

However, for many polynomials of degree d the set of possible permutations of the roots is more restricted. The most general polynomial of degree d allows all d! permutations, in which case we say the (Galois) group of the polynomial is the fully symmetric group S_{d} , but there are also polynomials of degree d whose Galois group is a subgroup of S_{d}. For example, a quintic that is the product of 5 linear factors in Z[x] will obviously split completely in every ring Z_{p}[x]. In this case the basic Galois group is just the trivial identity group, I, with only one element, so every prime will be of the type {1_{5}}. On the other hand, some polynomials have Galois groups G that are intermediate between the identity group I and the fully symmetric group S_{d}. In those cases we can compute the asymptotic density of each "type" simply by computing the fraction of the permutations contained in G that have the cyclic structure of the respective type. 


1.8 Recurrences Modulo Composites 

Given the general period of the recurrence of f for each prime in the factorization of _{}, the general period of the recurrence (mod n) is given by 

_{} 

where "lcm" signifies the least common multiple. For example, given the prime periods 

_{} 

relative to the polynomial f(x) = x^{3}  x  1, the general period of the composite integer 360 = (2)^{3}(3)^{2}(5) equals the least common multiple of 2^{2}(7), 3^{1}(13), and 5^{0}(24). Therefore, t_{360} = 2184. 

Using the equation above, we can determine highly "resonant" composite moduli relative to a given polynomial. For example, relative to x^{3}  x  1 we have t_{449} = 224 = 2^{5}(7), so the general period of the recurrence modulo 2^{6}(449) equals the least common multiple of 2^{5}(7) and 2^{5}(7), which is just 224. This shows that all the elements of any given sequence satisfying the recurrence A_{n} = A_{n2} + A_{n3} fall into no more than 224 of the residue classes modulo 28736, which is less than 1% of all the residue classes. 

To construct another example, we can begin with the fact that 

_{} 

and search for other primes whose periods divide this number. We find the following values 

_{} 

_{} 

_{} 

Therefore, all the elements of any given sequence satisfying the recurrence A_{n} = A_{n2} + A_{n3} fall into no more than 591360 distinct residue classes when evaluated modulo the number 

_{} 

which equals 
_{} 

In other words, the values of the sequence can fall into only 1 in (7.223)10^{29} of all the residue classes. 
