Pseudo prime tests

[Torbjorn Granlund]

bodrato at mail.dm.unipi.it writes:

  You mean the BPSW primality test?

I wasn't aware of this "BPSW" suggestion.

What I am suggesting is similar, but I am not familiar with the Lucas
test.  I also think one should do more trial dividing, and let its
limits be operand dependent.

  Some months ago, David Cleaver did post some implementation for this or
  something similar. If he still is interested we might ask if he want to
  assign the copyright of his code to FSF and/or revise our code.
  
Good idea!

  I wrote a kind of implementation for the Lucas-Selfridge test, it computes
  three sequences. Lucas U, Lucas V, and Q^t, modulo. It should be slower
  than a plain Miller-Rabin, but I didn't test. It's attached, should be
  REDCfied.

Cool.  I suppose I need to read more about the maths to fully admire
your work.  :-)

  > properties.  Nobody can promise a specific likelihood that a number
  > passing this test is a prime (unless it is < 10^17, where this
  > likelihood is 1).
  
  If it is a test with fixed parameters, we obviously can't, but
  
That depends on the perspective.  If for a set of k integers, the test
is correct for all but f, I'd argue that a random integer from the set
have a likelihood of f/k to trigger a test failure.

  > 1. Do some trial dividing, return if factor found.
  > 2. Run a millerrabin test of, say, base 2, return of composite found.
  > 3. Recognise known-bad forms of composites for (say) k < 10
  >    (i.e., solve a quadratic equation using for each k).  Return if
  >    a factor found.
  > 4. Run much fewer millerrabin iteration than normally needed...
  
  I'd add 2b. Run Lucas (with fixed parameters? like MR with base 2?). With
  random parameters it should give at least a 4/15 contribution to
  probability (1/2 in the worst cases, but it can be avoided).
  
Perhaps.  It is not clear to me that that would be an improvement since
(1) we already don't know that test fails for any numbers and (2) we
will not be able to make stronger promises of the likelihood of
pseudoprime existence.

  An observation. My implementation of Lucas, detects if a number is in the
  form 2^s-1; it does not exploit the fact... but it shouldn't be difficoult
  to switch to Lucas-Lehmer, then give a "definitely" answer.

We could also identify 2^s and return 0 (when s != 1).  :-)

-- 
Torbjörn