Pseudo prime tests

[bodrato at mail.dm.unipi.it]

Ciao,

Il Lun, 11 Giugno 2012 12:48 pm, Torbjorn Granlund ha scritto:
> Selfridge and Pomerance have noticed that an M-R test with base 2 plus
> a Fibonacci test (Fib_n + Legendre(n,5) == 0 (mod n)) seem to correctly

You mean the BPSW primality test?
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.

> (I think computing Fib_n mod n for the number n can be done at about the
...
> that we need to stick mod operatoons here and there.  But we should
> also perhaps use REDC residues.)

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.

> 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

> 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).

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.

Regards,
m

-- 
http://bodrato.it/software/strassen.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stronglucasselfridge_p.c
Type: text/x-csrc
Size: 4294 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120611/c8630ada/attachment.bin>