Martin Rubey <[email protected]> writes: >> AFAIK such cases are extremally rare, it is almost impossible to find >> such case via random search and systemtic methods to find them >> are quite heavy. > > right. I just found Davenports report, and > > 56897193526942024370326972321 > > is such a number. Moreover, I found that > > 1195068768795265792518361315725116351898245581 > > is considered prime after my modification, which is not true. I'll put > these numbers (and any others I can find in Davenport's paper) into the > testfile.
I just asked a colleague to explain the two “maximal 2-part” test from Primality Testing Revisited by Davenport http://portal.acm.org/citation.cfm?id=143290 to me. I think I should put it into the documentation. Short explanation: count2Order(k) counts the number of b such that b^((n-1)/2) = -1 (mod n). If n is prime, then b^((n-1)/2) is just the Legendre symbol legendre(b, n), and -1 for exactly half of the b's. Of course, if n is not prime, we might still get some -1, which explains why we should first do some checks disregarding count2Order. We could not see why one tests count2Order(k) = 0, and does not require count2Order(k) to exceed a proportion of the number of tests, but that's certainly only tuning. It is also unclear why Davenport collects more information than needed... Well, that's it for the moment. Martin
-- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
