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