Pseudo prime tests
Torbjorn Granlund
tg at gmplib.org
Thu Jun 14 14:41:11 CEST 2012
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
More information about the gmp-devel
mailing list