2.0 Symmetric Pseudoprimes Relative to Selected Polynomials 

This section presents examples of symmetric pseudoprimes relative to selected polynomials of degrees 1 through 5. For degrees 1, 2, and 3 the discussion focuses on familiar polynomials (such as the Fibonacci polynomial of degree 2 and Perrin's polynomial of degree 3) to show how these well known cases fit within the context of symmetric pseudoprimes. For higher degrees there do not appear to be such well established examples, so we have focused on irreducible polynomials with small integer coefficients and a variety of splitting field structures. In particular, we exhibit a symmetric pseudoprimes relative to a fully symmetric quintic. 


2.1 Polynomials of Degree 1 

By Proposition 6, the symmetric pseudoprimes relative to any given first degree polynomial f(x) = x  c (c Î Z) are the integers N such that s(N) = s(1) (mod N), which is to say, c^{N} = c (mod N). Therefore, the symmetric pseudoprimes relative to f are identical to the ordinary pseudoprimes relative to f. 

All the symmetric pseudoprimes less than 10^{4} relative to the first degree polynomials f(x) = x  2, f(x) = x  3, and f(x) = x  5 are listed in Table 1. The entries listed in bold are Carmichael numbers, which are symmetric pseudoprimes relative to every first degree polynomial. The entries listed in parentheses are those divisible by c. 

The importance of imposing congruence conditions on all the symmetric functions (not just the sum) of the roots can be shown by considering products of first degree polynomials. For example, the ordinary pseudoprimes relative to the polynomial 

_{} 
include not only the integers that are pseudoprimes relative to both x  2 and x  3, but also the integers n for which 2^{n} + 3^{n} = 2 + 3 even though 2^{n} ¹ 2 and 3^{n} ¹ 3 (mod n). All such n less than 10^{6} are listed in Table 2. (The values listed in parentheses are those divisible by 2 or 3). Also shown are the values of 2^{n}3^{n} (mod n), demonstrating that of all these ordinary pseudoprimes only 15 is a symmetric pseudoprime; the others each satisfy the congruence condition on the first symmetric function (the sum), but not on the second summetric function (the product). 

Table 3 gives the ordinary pseudoprimes less than 10^{6} relative to f(x) = (x  2)(x  3)(x  5), excluding those that are pseudoprimes relative to all three of the individual polynomials x2, x3, and x5. Notice that 50721 and 811921 satisfy the required congruence conditions on the third as well as the first symmetric function. Similarly, the integer 49 (not shown) satisfies the second and third congruence but not the first. 

To complete the demonstration that no two of the congruences, for a general cubic, is sufficient to ensure that all three are satisfied, we need to show a case that satisfies the first two but not the third. We have not found such a case relative to f(x) = (x  2)(x  3)(x  5). However, relative to the polynomial 

_{} 

the composite integer N = 703 = (19)(37) satisfies the congruence s(kN) = s(k) (mod N) for k = 1 and 2, but not for k = 3. To prove this, we first form the Nth powers of the roots (mod N) as follows:

_{} 
The elementary symmetric functions of these powers are

_{} 
Since 498 = 205 (mod N), we see that s_{1}(N) = s_{1}(1) and s_{2}(N) = s_{2}(1) (mod N). However, 96 is not congruent to 12121 (mod N), so N is not a symmetric pseudoprime relative to f. This fact can also be shown in terms of the sequence of s_{1}(k) values (mod N) as follows 

_{} 
_{} 

Thus, the three congrunces together are a stronger test than just the first two. 


2.2 Polynomials of Degree 2 

The odd symmetric pseudoprimes relative to any given second degree polynomial f(x) = x^{2} + c_{1}x + c_{2} (c_{i} Î Z) are the composite integers N for which the congruences s(N) = s(1) and s(2N) = s(2) are both satisfied (mod N). Noting that s(0) = 2, s(1) = c_{1}, and s(2) = c_{1}^{2}  2c_{2}, equation (23) from Section 1 allows us to express the conditions s(N) = s(1) and s(2N) = s(2) as follows 

_{} 

_{} 

These and all other congruences in this section are understood to be (mod N) unless some other modulus is specified. Notice that if N is coprime to 2c_{1}, then equation (1) implies 

_{} 

where gcd(u,v) signifies the greatest common divisor of u and v. Now, using the basis sequence relations described in Part 1 we can express b_{0}(2N) and b_{1}(2N) in terms of b_{0}(N) and b_{1}(N) as follows

_{} 
_{} 

Substituting these expressions into (2) gives 

_{} 

where the argument of each basis sequence symbol, when not explicitly specified, is understood to be N for the remainder of this section. Multiplying through by 2 and substituting the expression for 2b_{0} from equation (1) gives 

_{} 

where D = c_{1}^{2}  4c_{2}, the discriminant of f. Clearly, the congruence is satisfied if b_{1} = 1 (mod N), meaning that N divides b_{1}  1. On the other hand, if N and b_{1}  1 are relatively prime, then we can divide the preceding congruence by b_{1}  1 to give 

_{} 

In this case, assuming D is coprime to N, we have b_{1} = 1 (mod N). Now, since (1) gives b_{0} = (c_{1}/2)(b_{1}  1), it follows that for any prime or symmetric pseudoprime N coprime to 2c_{1}D, and assuming that N either divides or is coprime to b_{0}(N), we have 

_{} 

or 
_{} 

Of course, the divisibility assumptions on N used in this derivation are not implied by the definition of a symmetric pseudoprime, so the congruences (3) and (4) are a stronger primality criterion. 

Definition 3: A symmetric pseudoprime N relative to a second degree polynomial f is called determinate if gcd(2c_{1}D,N) = 1 and gcd(b_{0}(N), N) = 1 or N. 

Clearly a determinate symmetric pseudoprime satisfies either (3) or (4). To further strenghten the criterion, we can specify which of these two conditions applies to any given N. If N is actually a prime, it follows from the discussion in Section 1.7 that equation (3) is satisfied if f splits into linear factors in the field Z_{N} (which implies that D is a square modulo N), and that equation (4) is satisfied if f is irreducible in Z_{N} (which implies that D is not a square modulo N). 

To illustrate the preceeding topics, consider the familiar "Fibonacci polynomial" f(x) = x^{2}  x  1. Since this is reversible, we know (by Proposition 8) that a composite integer N is a symmetric pseudoprime relative to f if and only if s(N) = s(1) (mod N). All 86 such composites N less than 10^{6} are listed in Table 4, along with the values of b_{0}(N) and b_{1}(N) (mod N), and gcd(N, b_{0}(N)). Nineteen of these symmetric pseudoprimes can immediately be distinguished from primes because they are not determinate (eleven being divisible by the discriminant D = 5, and eighteen having 1 < gcd(N, b_{0}(N)) < N ). Each of the remaining 67 symmetric pseudoprimes is determinate, but eleven of them (listed in parentheses) can be excluded because they exhibit the wrong congruences for their residue classes (mod 5). This leaves 56 composites which cannot be distinguished from primes based on any of the criteria discussed above. 

There are second degree polynomials that exhibit a much lower density of symmetric pseudoprimes than the Fibonacci polynomial. For example, the polynomial 

_{} 

has only 4 symmetric pseudoprimes less than 10^{6}, none of which is determinate. Notice that since this polynomial is not reversible, the single congruence s(N) = s(1) is not sufficient to ensure that N is a symmetric pseudoprime; we must also have s(2N) = s(2). 

The first three symmetric pseudoprimes relative to polynomial (5) are listed below. 



The next symmetric pseudoprime relative to polynomial (5) is 38503, which satisfies (3), making it the smallest determinate symmetric pseudoprime relative to (5). (In comparison, the Fibonacci polynomial has 18 determinate symmetric pseudoprimes less than 10000.) There are only 69 determinate symmetric pseudoprimes relative to polynomial (5) less than 8(10)^{7}, and these are listed in Table 5. Each of these satisfies the "splitting congruences" (3). It follows that congruence (4) (which is satisfied by half of all primes) is a sufficient primality criteria for integers less than 8(10)^{7}. 

The seven pseudoprimes appearing in parentheses in Table 5 can be distinguished from primes based on the values of the basis sequence elements b_{0}((N1)/2) and b_{1}((N1)/2). In a binary algorithm these two elements are always computed in the secondtothelast step, so it's convenient to use these elements to strengthen the test. Letting m = (N1)/2 we have 

_{} 
and 
_{} 

If N is a prime, it must satisfy either (3) or (4). If it satisfies (3) then (using the fact that gcd(N,c_{2}) = 1 for primes N > c_{2}) we have 

_{} 

Since N is assumed prime, it follows that either N divides b_{1}(m) or else gcd(N, b_{1}(m)) = 1. If N divides b_{1}(m), then clearly 

_{} 

On the other hand, if gcd(N, b_{1}(m)) = 1, it follows that 

_{} 

Since all of the psudoprimes in Table 5 satisfy (3), the above congruences are sufficient to exclude all 7 of the determinate pseudoprimes listed in parentheses. 

Although we have not found any composites relative to (5) that satisfy (4), they presumably exist, so we will derive the congruence conditions on b_{0}((N1)/2) and b_{1}((N1)/2) for this case. Again letting m = (N1)/2, we can rearrange the terms of (6) and then square to give 

_{} 

Also, if we multiply (8) by c_{1} and multiply (7) by c_{2}, we can eliminate the term 2c_{1}c_{2}b_{0}(m)b_{1}(m) from these two equations to give 

_{} 

Multiplying through by 4c_{2}b_{1}(m)^{2}, we can then substitute from equation (7) to yield the following quadratic in b_{1}(m)^{2}: 

_{} 

Solving this for b_{1}(m)^{2} gives the two possible values 

_{} 

which correspond to 
_{} 

Section 3.1 describes how the Legendre symbols [c_{2}/N] and [D/N] determine which of these two possible solutions applies for any given prime N. 


2.3 Polynomials of Degree 3 

By Proposition 6, a composite integer N coprime to 6 is a symmetric pseudoprime relative to the third degree polynomial 

_{} 

iff all three of the congruences 
_{} 

are satisfied. If the polynomial is reversible (meaning that c_{3} = ±1), then by Proposition 8 an odd composite integer N is a symmetric pseudoprime relative to f iff the two congruences 

_{} 

are satisfied. Moreover, if f is reversible, Proposition 9 shows that a composite integer N is a symmetric pseudoprime relative to f iff the two congruences 

_{} 

are satisfied. 

The third degree polynomial that has recieved the most attention with respect to pseudoprime tests is

_{} 

Following Shanks and Adams, we will refer to this as Perrin's polynomial. This particular polynomial seems to have been selected for study by Lucas and Perrin mainly because c_{1} = 0, so s(p) is divisible by p for every prime p. Perrin also remarked that the sequence grows more slowly than the Fibonacci sequence, making some manual computations easier. The author's attention was drawn to (9) because its characteristic recurrence corresponds to the spiral tiling of equilateral triangles, just as the Fibonacci recurrence corresponds to the spiral tiling of perfect squares. These are the only two ways of partitioning the plane into a geometric progression of regular polygons. 

Shanks and Adams found that, relative to Perin's polynomial, the smallest composite N such that s(N) ( 0 (mod N) is 271441. They also noted that Perrin's sequence is reversible, and that the primality test is strengthened by requiring the reverse congruence s(N) = s(1) (mod N). Composite integers N that satisfy s(±N) = s(±1) and four other congruences involving the terms s(±(N+1)) and s(±(N1)) (mod N) were called "acceptable composites". (It was reported in [4] that, at least up to 50(10)^{9}, the congruences involving s(±(N+1)) and s(±(N1)) did not strengthen of the test.) Based on the discussion in Section 1.4, it is clear that the composite integers N such that s(±N) = s(±1) (mod N) for a reversible cubic are precisely the symmetric pseudoprimes relative to that cubic. 

Shanks and Adams found that the smallest symmetric pseudoprime relative to Perin's polynomial is 27664033. Subsequently Shanks, et al, listed all 55 symmetric pseudoprimes less than 50(10)^{9} relative to Perin's polynomial. The algorithm used to compute these results can be deduced from the material presented in Section 1.4. Since Perrin's polynomial has d = 3 and c_{d} = 1, the relations between the coefficient sequences and the symmetric functions with k = 3 give 

_{} 

Noting that s(0) = 3, that Warring's formula gives c_{0}(n) = 1 and c_{1}(n) = s(n), and that 

_{} 
we have 
_{} 

which is equivalent to the "Doubling Rule" used by Shanks and Adams: 

_{} 

Furthermore, using the basis sequence relations from Section 1.2 with r = ±1, we have 

_{} 

These formulas are valid for all integers n, positive or negative, so they can operate on the "signature" 

_{} 

to compute s(N) and s(N) (mod N) in log_{2}(N) steps, where each step requires 6 full multiplications. 

The basis sequence algorithm described in Section 1.2 also requires d(d+1)/2 = 6 full multiplications per step, so in a sense the methods are equally efficient. However, for this particular case (reversible, third order) the "Doubling Rule" has the advantage of producing both s(N) and s(N), whereas the basis sequence algorithm must include one additional step to compute s(2N) so as to complete the pseudoprime test. Also, the test based on s(N) and s(2N) is strictly applicable to odd integers only, whereas the test based on s(N) and s(N) is applicable to all integers. On the other hand, the "Doubling Rule" has some drawbacks: (1) it requires manipulation and storage of 6 dynamic variables (the "signature"), versus only 3 for the basis sequence algorithm, (2) it applies only to reversible sequences, limiting it to recurrences with only d1 congruence conditions and only one test per discriminant, and (3) it becomes progressively more complicated when generalized to recurrences of higher order. (We will illustrate this last point by presenting the "Doubling Rule" for 5th order recurrences in Section 2.5.) In contrast, the basis sequence algorithm applies to nonreversible as well as reversible sequences, and to recurrences of any order. 

For Perrin's sequence, the forward congruence s(N) = s(1) alone is sufficient to exclude most composites other than the symmetric pseudoprimes. The only ordinary pseudoprimes less than the first symmetric pseudoprime are 



These numbers (which have a coincidental affinity for Mersenne prime factors) can be used to determine when certain summations take on integer values. This is based on the fact that the values of s(n) for Perrin's polynomial can be expressed in closed form as 

_{} 

where r = 0,1,.., or 5, and a,b are the least nonnegative integers such that a = r (mod 2) and b = r (mod 3). Clearly, the summation is an integer iff s(6N+r) = 0 (mod 6N+r). For example, the integer n = 16532714 = 6(2755452) + 2 satisfies the congruence s(n) = 0 (mod n), so 2755452 is the least positive integer N such that the summation 

_{} 

is an integer. 

Perrin's polynomial is the fundamental reversible cubic with discriminant 23 (which is the smallest negative discriminant for a cubic). As explained by Shanks, et al, there are 12 reversible cubics with discriminant 23, but the corresponding recurrences are all of the form s(k) = s_{Perrin's}(mk) with m = ±1, ±2, ±3, ±4, ±5, or ±9. Therefore, every symmetric pseudoprime relative to Perrin's polynomial is also a symmetric pseudoprime relative to each of the other reversible polynomials of discriminant 23. However, since we are not restricted to reversible sequences, we can consider other polynomials with discriminant 23, such as 

_{} 

Even though the prime types relative to this polynomial are identical to the prime types relative to Perrin's polynomial, the only symmetric pseudoprimes less than 50(10)^{9} relative to both Perrin's polynomial and (10) are the four Carmichael numbers listed in [4]. This is because the periods of the two sequences modulo a given prime are not necessarily equal. The smallest symmetric pseudoprime relative to (10) of the form pq where p and q are both splitting primes is 3042763501 = (27581)(110321). 

To give an example with a different discriminant, consider the nonreversible cubic 

_{} 

which has discriminant 135. Relative to this polynomial the smallest symmetric pseudoprime equal to the product of two splitting primes is 196049701 = (9901)(19801). 

In Section 2.1 we gave an example of a cubic polynomial relative to which the integer 703 satisfies the first and second congruences but not the third. That polynomial was reducible, having the integer roots 17, 23, and 31. The same example can be given for an irreducible cubic by simply taking the coefficients modulo 703. Thus, relative to the irreducible polynomial 

_{} 

the integer 703 satisfies the first and second congruences but not the third. 


2.4 Polynomials of Degree 4 

Consider the quartic polynomial 

_{} 

By Proposition 8, a composite integer N coprime to 6 is a symmetric pseudoprime relative to this polynomial if and only if 
_{} 

(We could also use the congruences on s(N), s(N), and s(2N) to test any odd integer N.) The initial values of the coefficient sequences are as follows: 


The Galois group of (11) is the symmetric group S_{4}, so all 24 of the permutations of the roots are allowable, and the asymptotic proportion of prime types is as shown below. 


Using the basis sequence algorithm of Section 1.2, we searched the splitting primes (i.e., primes of type {1_{4}}) relative to (11), and found that the smallest symmetric pseudoprime equal to the product of two splitting primes is 
12282695011 = (78367)(156733) 

It's easy to show that if p and q are splitting primes then pq is a symmetric pseudoprime if and only if b_{k}(p) = b_{k}(1) (mod q) and b_{k}(q) = b_{k}(1) (mod p). 

An example of a nonreversible quartic is 

_{} 

Although this quartic is irreducible (according to Eisenstein's criterion), its Galois group is not the fully symmetric group. As a result, some root permutations are not allowable. Specifically, there are no primes of type {1_{1}3_{1}} relative to (12). The restricted nature of the roots of this polynomial also shows up in the fact that the general period of the prime type {4_{1}} always divides 

_{} 

This is because the four roots of (12) satisfy the relation 

_{} 

and so, noting that (12) is irreducible, we have 

_{} 

(The roots of (12) are discussed in Section 3. The resolvant cubic of this polynomial has one rational root, from which the permutation of the roots in the preceding expressions is determined.) 

A complete search of odd integers shows that the smallest symmetric pseudoprime relative to (12) is

5351537 = (1889)(2833) 

The next symmetric pseudoprime relative to (12) that is a product of two splitting primes is 

746331041 = (15773)(47317) 


2.5 Polynomials of Degree 5 

A composite integer N coprime to 120 is a symmetric pseudoprime relative to the fifth degree polynomial 

_{} 

if and only if all five of the congruences 

_{} 

are satisfied. In this section we will focus on the quintic polynomial 

_{} 

The discriminant of this polynomial is 4511 = (13)(347), which is the smallest magnitude for any fully symmetric quintic [7]. The initial values of the coefficient sequences for this polynomials are listed below. 



Since the Galois group of (13) is the fully symmetric S_{5}, all 120 of the root permutations are allowable, and all 7 of the prime types occur. Their asymptotic proportions are listed in the table below.


Relative to (13) the smallest symmetric pseudoprime equal to the product of two splitting primes is 

2258745004684033 = (27439297)(82317889) 

The search for this number was carried out using the basis sequence algorithm described in Section 1.2. With this algorithm the computation of s(N) (mod N) requires 15(log_{2}N) full multiplications (mod N). 

Since (13) is reversible, we could also have used a "Doubling Rule", analagous to that used by Shanks and Adams. For 5th order recurrences the basic doubling rule consists of the two formulas 

_{} 

where j = c_{5}(1) = ±1. The part first comes directly from Warring's formula for c_{2}(n), which also gives s_{1}(4n) = s_{1}(2n)^{2}  2s_{2}(2n). To deduce the second part, we can set k = 3 in the relevant equation from Section 1 (with appropriate substitutions) to give an expression for s_{1}(3n) in terms of s_{1}(±2n) and s_{1}(±n) and s_{2}(n). Likewise we can set k = 4 to give an expression for s_{1}(4n) in terms of s_{1}(3n), s_{1}(2n), s_{1}(±n), and s_{2}(n). Then we eliminate s_{1}(3n) from thes two equations and substitute s_{1}(2n)^{2}  2s_{2}(2n) for s_{1}(4n), and s_{1}(n)^{2}  2s_{2}(n) for s_{1}(2n), to give the second part. The other equations needed to compute terms of the form s_{1}(2n+1) and s_{2}(2n+1) can be developed in the same way, although they involve a large number of elements from the s_{1}(±k) and s_{2}(±k) sequences (corresponding to the the "signature"). 

The type of any prime p with respect to a given polynomial f(x) can easily be determined by checking the number of linear and quadratic factors of f(x) modulo p. To find the number of (distinct) linear factors, we simply count the number of residues u in the range from 1 to p1 such that f(u) = 0 (mod p). To find the number of quadratic factors, we count the number of residue pairs u,v such that (x^{2} + ux + v)(x^{3} + Ax^{2} + Bx + C) = f(x) modulo p for some integers A,B,C. This implies the conditions 

_{} 

Solving the first three for A, B, and C, and substituting into the last two, we have two necessary and sufficient conditions for x^{2} + ux + v to divide f(x) modulo p. For example, with respect to the polynomial (13) we get the two conditions 

_{} 

_{} 

Of course, if there are n_{1} linear factors, we automatically get n_{1}(n_{1}1)/2 nonprimitive quadratic factors, so to give the number n_{2} of primitive quadratic factors we must subtract n_{1}(n_{1}1)/2 from the number of distinct pairs u,v that satisfy the quadratic conditions. Once the linear and quadratic factors have been divided out, what remains is a polynomial of degree m = 5  n_{1}  2n_{2}. Clearly this must be an irreducible factor of degree 3, 4, or 5, so the numbers n_{3}, n_{4}, and n_{5} of primitive cubic, biquadratic, and quintic factors can immediately be inferred. 

With respect to the quintic f(x) given by equation (13) the prime p = 11 is of type 2_{1}3_{1}, which means that f(x) factors into a quadratic and a cubic in the field Z_{11}[x]_{f}. Specifically we have f(x) = g(x)h(x) where 

_{} 

As discussed in Section 1.7, it follows that the sequence x, x^{11}, x^{121}... has period 6 in Z_{11}[x]_{f}, but the period is 3 in Z_{11}[x]_{h}, and the period is 2 in Z_{11}[x]_{g}. The actual terms of this sequence are listed below: 

_{} 

The types of all the primes less than 2000 relative to polynomial (13) are listed in Table 6. Continuing on to determine the types for all 669 primes less than 5000, we find the following distribution: 



The relativity scarcity of splitting primes (i.e., primes of the type 1_{5}) requires us to examine a larger number of primes in order to get a meaningful estimate of the asymptotic density. We find that, of the 9592 primes less than 100000, there are 75 splitting primes relative to (13), compared with a predicted 79.9. This confirms that the asymptotic density of splitting primes relative to this irreducible quintic is 1/120. 
