|
Symmetric Pseudoprimes |
|
|
|
Fermat's Little Theorem states that for any integer c, if p is a prime, then cp c is divisible by p. This is a necessary but not quite sufficient condition for primality, because there are (rare) composites that satisfy this type of test for certain values of c. For example, 2341 2 is divisible by 341, even though 341 is composite. This is why 341 is called a pseudoprime relative to the base 2. There are even composites, called Carmichael numbers, that are pseudoprimes relative to every integer base. The smallest Carmichael number is 561. |
|
|
|
Another way of stating Fermat's Little Theorem is that, given a polynomial of the form f(x) = x c, if p is a prime, then the sum of the pth powers of the roots of f is congruent to the sum of the first powers (mod p). Since f has just the single root c, this may seem like a trivial re-statement of the previous one, but it can be immediately generalized to polynomials of any degree, yielding much stronger primality tests. For example, consider the Fibonacci polynomial x2 x 1, and let a,b denote the roots. The nth term of the Lucas sequence is just Ln = an + bn, and so, since a + b = 1, it follows from Fermat's Little Theorem that Lp = 1 (mod p) for every prime p. A composite number c such that Lc = 1 (mod c) is called a pseudoprime relative to the polynomial x2 x 1. The smallest such number is 705. |
|
|
|
Most discussions of generalized psuedoprime tests have imposed just the congruence condition on the sum of the nth powers of the roots, i.e., on the first symmetric function of the roots. A better generalization is to impose the appropriate congruence condition on all symmetric functions of the roots. This is based on the following generalization of Fermat's Little Theorem: |
|
|
|
For any monic polynomial f with integer coefficients, if θ is a (complex) root of f and p is a prime, then f(θp) = 0 (mod p). |
|
|
|
Lucas considered this generalization, observing that if s(k) denotes the sum of the kth powers of the roots of f then we have s(np) = s(n) (mod p) for any integer n and prime p. In particular he gave the (insufficient) primality criterion s(N) = 0 (mod N) for the polynomial f(x) = x3 x 1. This criterion was also discussed by Perrin, and again by Shanks and Adams, who defined an "acceptable composite" as a composite integer N such that the six quantities s(±N), s(±(N+1)), and s(±(N1)) satisfy certain congruence conditions (mod N). They reported that, at least for integers up to 50(10)9, the congruences involving s(±(N+1)) and s(±(N1)) were superfluous, so the test essentially consisted of the requirement s(±N) = s(±1) (mod N). Although this "two-sided" test can easily be applied to polynomials of higher degree, it does not fully embody the primality criterion implicit in a given polynomial of degree greater than 3 (or of cubics for which the constant coefficient is not equal to ±1). In general, we expect a polynomial with d distinct roots to represent d non-redundant primality conditions, one for each root. |
|
|
|
Accordingly, a symmetric pseudoprime relative to f is defined as any composite integer c such that f(θc) = 0 (mod c) for every root θ of f. In other words, given a monic polynomial f with integer coefficients, a symmetric pseudoprime relative to f is defined as a 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. |
|
|
|
Equivalently, we could define symmetric pseudoprimes in terms of Newton's sums for the roots of a polynomial. Let f denote a monic polynomial of degree d with integer coefficients, and let s(k) denote the sum of the kth powers of the roots of f. Lucas observed that if p is a prime then s(pk) = s(k) (mod p) for every integer k. A composite integer c such that s(ck) = s(k) (mod c) for every positive integer k is a symmetric pseudoprime relative to f. For example, the smallest symmetric pseudoprime relative to f(x) = x2 is 341 = (11)(31). The relative rarity of these pseudoprimes, along with the fact that s(N) (mod N) can be evaluated in O[log(N)] multiplications modulo N, makes them useful for primality testing. |
|
|
|
Symmetric pseudoprimes tend to be more rare relative to polynomials with larger Galois groups. The Galois group of the quintic polynomial |
|
|
|
|
|
|
|
is the fully symmetric group S5. The smallest symmetric pseudoprime relative to this polynomial that is the product of two splitting primes is |
|
|
|
|
|
|
|
In the sections listed below, basic propositions and computational techniques associated with general linear recurrences and symmetric pseudoprimes are presented, along with specific examples relative to selected polynomials of degrees 1 to 5. The final section describes complete congruence conditions on the terms of arbitrary linear recurring sequences. |
|
|
|
3.0 Congruence Conditions On the Terms of Linear Recurring Sequences |
|
|
