素性测试的其他一些资料
1、Lucas and Perrin PseudoprimesLucas 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
polynomialx^4-5x^3-2x^2-3x-1is 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 quinticx^5-x^3-2x^2+1is 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 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 integers 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(±(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(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) = 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 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. 对照了一下原文，对上贴进行了重排版编辑。 多谢
本来想自己排的，后来机器被占就没做
最后加了连接
呵呵
:lol
目的之一就是等待象GxQ这样的小蜜蜂帮我整理
呵呵
页:
[1]