素性测试的其他一些资料

无心人

1、Lucas and Perrin Pseudoprimes Lucas pseudoprimes are discussed in Ribenboim's "The Book of Prime Number Records" (Springer, 1988), along with the algebraic identities that can be used to compute the nth Lucas number in O(log(n)) steps. Incidentally, the table of Lucas pseudoprimes (of the second kind, corresponding to the quadratic x^2 - x - 1) on page 104 of the first edition purports to give the 25 such numbers less than 1E+5, but actually lists only 24 numbers. The missing pseudoprime is 67861. Extending the table a bit, there are 86 such pseudoprimes less than 1E+6. Of those symmetric pseudorpimes, 19 can be excluded because they are not determinate (eleven being divisible by the discriminant, and eighteen having 1 < gcd(N,b0(N)) < N). Eleven of the remaining pseudoprimes can be excluded because they have the wrong Jacobi symbol, so this leaves just 56 composites less than a million that cannot be distinguished from primes based on the quadratic x^2 - x - 1. Interestingly, there are quadratics that give a much stronger test for compositeness. In particular, the equation x^2 - 4x - 9 has only four determinate symmetric pseudoprimes less than one million, and only 80 less than 1E+8. It's also worth noticing that all 80 of these pseudoprimes masquarade as "splitting primes"; I've never found a pseudoprime of the "irreducible" type relative to x^2 - 4x - 9 (although I assume they exist). It follows that this test is both necessary and SUFFICIENT for establishing the primality of any "irreducible" integer less than 1E+8, which covers about half of all primes in that range. One reason that x^2-4x-9 is so much stronger than x^2-x-1 is that my definition of a SYMMETRIC pseudoprime requires that ANY symmetric function of the Nth powers of the roots must be congruent to the same function of the 1st powers. This implies that, in general, a quadratic pseudoprime test imposes two congruence conditions (corresponding to the two elementary symmetric functions of the roots). However, the Fibonacci polynomial is degenerate because it is "monic in both directions", so it imposes only one congruence condition. (Many authors try to strengthen the x^2-x-1 test by defining congruence conditions on both the Lucas sequence and the Fibonacci sequence, but that approach does not generalize well to higher degrees.) Even stronger tests are given by higher degree polynomials. For example, Shanks and Adams found the composite number 27664033, which in my terms is the smallest symmetric pseudoprime relative to x^3-x-1. (They called this "Perrin's polynomial" because Perrin wrote a brief note on the corresponding sequence in the 1890's; however, Lucas had already given a much better treatment (better than Perrin, not better than Shanks and Adams) in his 1876 paper.) There are 55 symmetric pseudoprimes less than 50 billion (i.e.,50E+9). Perrin's polynomial has discriminant -23 and is monic in both directions. Another cubic with the same discriminant is x^3+x^2-4x-5. There are only FOUR numbers less than 50 billion that are symmetric pseudoprimes relative to this polynomial AND Perrin's polynomial, and all four are Carmichael numbers. To show that's there's nothing particularly good about discriminant -23, the cubic x^3-9x^2+24x-15 has discriminant -135, and the smallest symmetric pseudoprime (equal to the product of two splitting primes) relative to this polynomial is 196049701. Generally, the larger the group of a polynomial, the stronger is the primality test based on that polynomial. The group of quartic polynomial x^4-5x^3-2x^2-3x-1 is the fully symmetric group S_4, and the smallest symmetric pseudoprime (equal to the product of two splitting primes) relative to this polynomial is 12282695011. Even better, the group of the quintic x^5-x^3-2x^2+1 is S_5, and the smallest symmetric pseudoprime relative to this quintic is 2258745004684033. This test can be carried out on an integer N using just 15*log_2(N) full-precision multiplications. For a more detailed discussion of pseudoprimes based on arbitrary polynomials, see Symmetric Pseudoprimes.

无心人

http://www.mathpages.com/home/kmath003/kmath003.htm Symmetric Pseudoprimes Fermat's Little Theorem states that for any integer c, if p is a prime, then c^p - 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, 2³⁴¹ - 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 integers of any degree, yielding much stronger primality tests. For example, consider the Fibonacci polynomial x² - x - 1, and let a,b denote the roots. The nth term of the Lucas sequence is just L_n = aⁿ + bⁿ, and so, since a + b = 1, it follows from Fermat's Little Theorem that L_p = 1 (mod p) for every prime p. A composite number c such that L_c = 1 (mod c) is called a pseudoprime relative to the polynomial x² - 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) = x³ - 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(±(N-1)) 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(±(N-1)) 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(θ^p) = 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(p^k) = 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) = x-2 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.

$f(x) = x^5 - x^3 - 2* x^2 + 1$

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

N = 2258745004684033 = 27439297 * 82317889

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.

gxqcn

对照了一下原文，对上贴进行了重排版编辑。

无心人

多谢 本来想自己排的，后来机器被占就没做 最后加了连接 呵呵 目的之一就是等待象GxQ这样的小蜜蜂帮我整理 呵呵