Gerhard Niklasch on Fri, 15 Oct 1999 01:05:40 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: SPRP's, and miller(n,k) |
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