Re: SPRP's, and miller(n,k)

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to:
> Message-Id: <199910142117.RAA02600@tasam.com>
> Subject: SPRP's, and miller(n,k)
> From: Lucas Wiman  <lrwiman@tasam.com>
> Date: Thu, 14 Oct 1999 17:17:22 -0400 (EDT)
> 
> In the source code for PARI, it lists the result:
>  * Moreover, the four bases chosen at
>  *
>  * k == 16  (2,13,23,1662803)  will correctly detect all composites up
>  * to at least 10^12, and the combination at
> for the function miller().  Using Richard Pinch's list of strong
> psuedoprimes base 2, up to 10^13, I found that this is true for
> n<1122004669633=611557*1834669.

Yes.  However, this number would be caught as a composite by the
miller() implementation  (the function will note that there are
four square roots of -1 in the residue class ring).  The smallest
composite which will slip through this test is in fact
	3141703961467 = 886243*3544969
and the next are 4433977754251, 5867930920351, 6005270044507,
7928173529251, 9510594947587, 9924187357873 (and no further
ones below 10^13).

> Also, for 2,11,13,23,1662803 correctly detects all composites up
> to 10^13 (and possibly higher).  This is better than the successive
> primes result (for 5 Miller SPRP tests) by a factor of 4.6.

I have what I believe to be the complete list of 42 composites up
to 3*2^46 which would (wrongly) pass the miller() test for the four
bases chosen at k==16.  Without Atkin's `end-matching' check, there
would be 86 of them.  This will eventually find its way into an
implementation.  The combination of four bases and cheat sheet will
be faster than using five bases.

(And similarly, the thing to use between 2^16 and 2^32 is just bases
2 and 3 and a cheat sheet, and a 4Kbit table below 2^16.)

Enjoy, Gerhard