Lucas Wiman on Thu, 14 Oct 1999 19:36:48 -0400 (EDT)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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


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

I see.  I didn't run that test in Pari, but in Calc (before I
discovered Pari).  I noticed this remark in the source when 
finding out if nextprime() was probabilistic. 

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

Could you post this list (of both 42, and 86)?

Thank you,
Lucas Wiman