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, cN = 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 104 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 2n + 3n = 2 + 3 even though 2n 2 and 3n 3 (mod n). All such n less than 106 are listed in Table 2. (The values listed in parentheses are those divisible by 2 or 3). Also shown are the values of 2n3n (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 106 relative to f(x) = (x - 2)(x - 3)(x - 5), excluding those that are pseudoprimes relative to all three of the individual polynomials x-2, x-3, and x-5. 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 s1(N) = s1(1) and s2(N) = s2(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 s1(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) = x2 + c1x + c2 (ci Î 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) = -c1, and s(2) = c12 - 2c2, 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 co-prime to 2c1, 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 b0(2N) and b1(2N) in terms of b0(N) and b1(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 2b0 from equation (1) gives
where D = c12 - 4c2, the discriminant of f. Clearly, the congruence is satisfied if b1 = 1 (mod N), meaning that N divides b1 - 1. On the other hand, if N and b1 - 1 are relatively prime, then we can divide the preceding congruence by b1 - 1 to give
In this case, assuming D is coprime to N, we have b1 = -1 (mod N). Now, since (1) gives b0 = (c1/2)(b1 - 1), it follows that for any prime or symmetric pseudoprime N co-prime to 2c1D, and assuming that N either divides or is co-prime to b0(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(2c1D,N) = 1 and gcd(b0(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 ZN (which implies that D is a square modulo N), and that equation (4) is satisfied if f is irreducible in ZN (which implies that D is not a square modulo N).
To illustrate the preceeding topics, consider the familiar "Fibonacci polynomial" f(x) = x2 - 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 106 are listed in Table 4, along with the values of b0(N) and b1(N) (mod N), and gcd(N, b0(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, b0(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 106, 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 b0((N-1)/2) and b1((N-1)/2). In a binary algorithm these two elements are always computed in the second-to-the-last step, so it's convenient to use these elements to strengthen the test. Letting m = (N-1)/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,c2) = 1 for primes N > c2) we have
Since N is assumed prime, it follows that either N divides b1(m) or else gcd(N, b1(m)) = 1. If N divides b1(m), then clearly
On the other hand, if gcd(N, b1(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 b0((N-1)/2) and b1((N-1)/2) for this case. Again letting m = (N-1)/2, we can rearrange the terms of (6) and then square to give
Also, if we multiply (8) by c1 and multiply (7) by c2, we can eliminate the term -2c1c2b0(m)b1(m) from these two equations to give
Multiplying through by 4c2b1(m)2, we can then substitute from equation (7) to yield the following quadratic in b1(m)2:
Solving this for b1(m)2 gives the two possible values
which correspond to
Section 3.1 describes how the Legendre symbols [c2/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 co-prime 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 c3 = 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 c1 = 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((N-1)) (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((N-1)) 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 cd = -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 c0(n) = 1 and c1(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 log2(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 d-1 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 non-reversible 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 non-negative 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) = sPerrin'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 non-reversible 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 co-prime 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 S4, 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 {14}) 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 bk(p) = bk(1) (mod q) and bk(q) = bk(1) (mod p).
An example of a non-reversible 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 {1131} 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 {41} 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 co-prime 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 S5, 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(log2N) 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 = -c5(1) = 1. The part first comes directly from Warring's formula for c2(n), which also gives s1(4n) = s1(2n)2 - 2s2(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 s1(3n) in terms of s1(2n) and s1(n) and s2(n). Likewise we can set k = 4 to give an expression for s1(4n) in terms of s1(3n), s1(2n), s1(n), and s2(n). Then we eliminate s1(3n) from thes two equations and substitute s1(2n)2 - 2s2(2n) for s1(4n), and s1(n)2 - 2s2(n) for s1(2n), to give the second part. The other equations needed to compute terms of the form s1(2n+1) and s2(2n+1) can be developed in the same way, although they involve a large number of elements from the s1(k) and s2(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 p-1 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 (x2 + ux + v)(x3 + Ax2 + 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 x2 + 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 n1 linear factors, we automatically get n1(n1-1)/2 non-primitive quadratic factors, so to give the number n2 of primitive quadratic factors we must subtract n1(n1-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 - n1 - 2n2. Clearly this must be an irreducible factor of degree 3, 4, or 5, so the numbers n3, n4, and n5 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 2131, which means that f(x) factors into a quadratic and a cubic in the field Z11[x]f. Specifically we have f(x) = g(x)h(x) where
As discussed in Section 1.7, it follows that the sequence x, x11, x121... has period 6 in Z11[x]f, but the period is 3 in Z11[x]h, and the period is 2 in Z11[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 15) 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.