From: [Permission pending]
Newsgroups: sci.math
Subject: Lucas Pseudoprimes and Generalizations
Date: 21 Nov 1994 03:22:17 GMT

DT = Don Taylor (dont@agora.rdrop.com)
DT>  I would greatly appreciate anyone showing some pseudocode (or even 
DT>  real code) to do the Lucas Pseudoprime test, outlined for example 
DT>  in 'The Pseudoprimes to 25*10^9', Math. of Computation, V 35, N 151,
DT>  Jul 1980, pp1003-1026.

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. 

==============================================================================
[My response to the poster seems to have been lost but may be deduced
from the parts included below -- djr]
==============================================================================
Date: Tue, 22 Nov 1994 01:52:44 -0500 (EST)
From: [Permission pending]
Subject: Re: Lucas Pseudoprimes and Generaliz
To: rusin@math.niu.edu

>I really enjoyed your post. Perhaps I would've enojyed it more if I
>hadn't just spent several weeks recreating the general theory.

Oddly enough I had the same experience with this subject...developed it
quite extensively, and then stumbled across some papers that covered a 
lot of the same ground, so I sort of dropped it.

>(In my formulation, the test for primality of n is to see if the nth 
>term in each of several sequences subject to a linear recurrences is
>divisble by  n. The nth term of the kth sequence turns out to be the sum 
>of the (kn)th power of the roots of the polynomial. Is this the usual
>interpretation?)

I'm not sure there is a "usual" interpretation; the literature seems 
quite varied in the ways different authors approach it.  I worked with 
two main approaches: congruence conditions on the sum of the (kn)th 
powers of the roots, and congruence conditions on the elementary symmetric 
functions of the nth powers of the roots.  I believe they are essentially
equivalent, but I ended up preferring the symmetric function condition
because then I could express the generalized Fermat's Little Theorem by
saying, for any monic polynomial f with integer coefficients, if p is a
prime then f(z^p)=0 (mod p) for every root z of f. Then a symmetric
pseudoprime relative to f is a composite integer c such that f(z^c)=0 
(mod c).

>Naturally I am interested in references for your comments about other
>polynomials. 

I'd suggest the following papers:

   "Strong Primality Tests That are Not Sufficient", Adams and Shanks,
    Math of Comp, v39, n159, July 1982, pages 255-300.

   "Fast Primality Tests for Numbers Less than 50*10^9", Kurtz, Shanks,
    and Williams, Math of Comp, v46, n174, April 1986, pages 691-701.

   "A Note On Perrin Pseudoprimes", Steven Arno, Math of Comp, v56, n193,
    January 1991, pages 371-376.

   "Pseudoprimes for Higher Order Linear Recurrence Sequences", S. Gurak,
    Math of Comp, v55, n192, October 1990, pages 783-813.

   "An Efficient Formula For Linear Recurrences", C. Fiduccia, SIAM J Comp,
    v14, n1, February 1985, pages 106-112.

   "Theorie Des Fonctions Numeriques Simplement Periodiques", E. Lucas,
    American Journal of Math, v1, 1878, pages 184 ff. (see pages 230-231.)

>I had already worked considerably with x^3-3x-1 and found the composite
>~26million. In my interpretation, however, I saw no intrinsic value in 
>using polynomials with larger galois groups (rather than simply 
>polynomials of larger degree). Can you comment on this connection?

The main result in this area is Cheboterov's density theorem (see page
129 of Algorithmic Algebraic Number Theory by Pohst and Zassenhaus, 
Cambridge University Press, 1989).  Essentially, it's very difficult 
to construct a pseudoprime out of anything except "splitting primes", 
i.e., primes p such that the polynomial f splits into linear factors in 
the field Z_p.  For a polynomial of degree d with the fully symmetric 
group S_d, the proportion of all primes that are splitting primes is
1/(d!).  For any given degree, the larger the group, the lower the
proportion of splitting primes, and so the more rare pseudoprimes tend 
to be.  

>Incidentally, it is perhaps of some value to note that collectively, the
>primality tests afforded by all polynomials are sufficient to distinguish
>all composites from primes. 

What I'd really like to know is whether a FINITE SUBSET of all polynomials
is sufficient to distinguish all composites from primes.

>As far as I can tell, the effectiveness of any given set of tests for a
>particular  n  depends on the distribution of primitive roots mod  n, 
>about which, of course, not enough is ever known.

Most people have focused on the Jacobi symbols for n, and checked to see
that the "signature" of n matches it's Jacobi symbol.  I don't think I
recall seeing anyone relate the robustness of a test to the distribution
of the primitive roots, so you may have something unique there.  

Well, best of luck! 

==============================================================================

Date: Sat, 26 Nov 94 11:23:12 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Lucas Pseudoprimes and Generaliz

You wrote a very helpful letter to me regarding pseudo-primes of Lucas and 
other types; I'm not sure I ever mailed you a thank-you note I had begun:...

>I'd suggest the following papers:
Thanks! I'll have a look.

>The main result in this area is Cheboterov's density theorem (see page
Yeah, I should have thought about that.

>What I'd really like to know is whether a FINITE SUBSET of all polynomials
>is sufficient to distinguish all composites from primes.
Do you have any reason to think this could really happen? It would appear
to me that every combination of polynomials has a set of composites falsely
reported as primes -- a set with decreasing but non-zero density as the
range tested increases. I share your secret hope, but I have no optimism
that it can be true.

>>As far as I can tell, the effectiveness of any given set of tests for a
>>particular  n  depends on the distribution of primitive roots mod  n, 
>>about which, of course, not enough is ever known.
>
>Most people have focused on the Jacobi symbols for n, and checked to see
>that the "signature" of n matches it's Jacobi symbol.  I don't think I
>recall seeing anyone relate the robustness of a test to the distribution
>of the primitive roots, so you may have something unique there.  

I must have phrased this too mysteriously. If one knew, for example, that
there is a primitive root in Z_p among the set {2,3,...,[log p]} -- for
every prime  p  -- then tests based on Fermat's or Euler's methods
(e.g. the "Miller-Rabin test") could be used to test unambiguously for
primality with an upper bound on the number of tests needed. Some statement
of this type is quite likely to be true, but at present not possible to
prove (without, say, the GRH). I am just following here the perspective
Richard Pinch presented in a Notices article about a year ago.

Thanks again for your response. I'm looking up the references you gave
this weekend.

dave

==============================================================================

Date: Sat, 26 Nov 1994 17:04:07 -0500 (EST)
From: [Permission pending]
Subject: Re: Lucas Pseudoprimes and Generaliz
To: rusin@math.niu.edu

>> What I'd really like to know is whether a FINITE SUBSET of all 
>> polynomials is sufficient to distinguish all composites from primes.

>Do you have any reason to think this could really happen? It would 
>appear to me that every combination of polynomials has a set of 
>composites falsely reported as primes -- 

I agree, and the numerical evidence certainly supports this, i.e., a
pseudoprime generally turns up right about where one would expect based
on a probabilistic estimate (of the density of splitting primes).  On the
other hand, I'm not *quite* certain that the d congruence conditions (for 
a polynomial of degree d) fully capture everything that can be inferred 
from a given polynomial.  For example, consider the cubic 

                    x^3 - 5x^2 + 6x - 1

This is irreducible in terms of x, but it factors in terms of sqrt(x), 
i.e., letting y denote sqrt(x) we have

   y^6 - 5y^4 + 6y^2 - 1  =  (y^3 + y^2 - 2y - 1)(y^3 - y^2 - 2y + 1)

so from the original cubic we have these two other, related, cubics.  
It's interesting to compare the sets of splitting primes and pseudoprimes
relative to each of these cubics.  Similarly, it's interesting to combine
the tests based on a quartic and its resolvant cubic.  

Still, I agree that all such combinations would have their own 
pseudoprimes.  Some new idea would be needed to have any chance of 
excluding ALL composites based on just a finite set of polynomials. 
 
Another interesting question is whether/when a given polynomial is 
*sufficient* to establish primality, such as when the subject number 
has the "signature" of a prime relative to which the polynomial is
irreducible.  I'm impressed by the fact that even a simple quadratic 
like x^2 - 4x - 9 has no "irreducible" pseudos small enough for me to 
find.  An "irreducible" pseudo relative to an S_5 quintic would really 
be astounding.

I wonder if the situation with pseudoprimes may be considered a good 
model of "incompleteness" in the Goedelian sense?  Suppose I take as
an AXIOM that a number has no non-trivial factors iff it passes the
symmetric test based on some polynomial p(x).  If p(x) is, say, an S_5
quintic,  then my system of arithmetic will function pretty well and 
I'd be unlikely to produce a contradiction or notice any incompleteness, 
unless I specifically went looking for it.

But suppose one day I stumble across a pseudoprime, i.e., a number that
passes p(x) but that factors non-trivially.  Yikes!  My axiom system
leads to a contradiction!  But wait...don't panic...I'll just modify my
set of axioms with a new polynomial q(x), so the axiom now states that N
has no factors iff it passes both p(x) and q(x). All is well...apparently.
Of course, you and I know that no matter how many times I modify my 
axiom, there will always be numbers that defeat it.

But in a sense I'm no worse off with this type of axiom system than with
any other; there is always a point at which my system will reveal itself
to be either incomplete or inconsistent.  I suppose this is just another
way of looking at the argument for "probabilistic" proofs, but I think
it's interesting to consider the implications of an axiom such as 
{Passing p(x) implies primality}, and whether it leads to any 
contradictions other than the existence of pseudoprimes.

==============================================================================

Date: Sat, 26 Nov 94 23:02:03 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Lucas Pseudoprimes and Generaliz

Very interesting! I'll have to give it some thought. (I'm supposed to
be an algebriac topologist but I find number-theoretic problems to
be much more captivating. Too bad all the good questions are
really hard...)

dave