Pari uses the Baillie-Pomerance-Selfridge-Wagstaff primality test, which at its heart is the observation that very few numbers are both (Fermat) strong pseudoprimes base 2 and Lucas pseudoprimes for x^2+P*x +1 where P is the smallest positive integer such that P^2 - 4 is not a quadratic residue (for the specific number being tested). There are no such pseudoprimes less than 10^13 which can be verified by consulting the list of fermat strong pseudoprimes base 2 at: http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
In some sense this is not a probabilistic test as described in textbooks since the (unknown) probability is fixed. One could supplement BPSW with Rabin-Miller, but tests during the GAP implementation showed that even a single trial of Rabin-Miller was ridiculously slow given the fact that not a single composite BPSW pseudoprime has ever been found. The pari implementation contains speedups for small integers and integers with small factors. It also contains a clever optimization to use GCD instead of trial division to handle testing many factors at once. There is a relatively simple calculation to show when GCD is faster than trial division. The pari implementation is in basemath/ifactor1.c lines 390-508 in the functions BSW_psp and the machine integer version uisprime. Pari does allow calling Rabin-Miller using the ispseudoprime(N,1) function, but this is not done in nextprime() which uses direct calls to BSW_psp(N) and a simple stepping procedure similar to the one in SAGE, but using prime residues mod 210 instead of mod 2. This is line 637-675 of the same file. I recommend patching SAGE to increment using nextprime rather than n +=2, partially because pari's code is currently more optimizied and more likely to continue to be optimized, and partially because there is less I/O between the two processes; let pari have the entire tight loop, don't communicate during the tight loop. On Jun 7, 3:28 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > On 6/7/07, Michel <[EMAIL PROTECTED]> wrote: > > > > > I guess you mean the opposite. > > Yes, I meant the opposite -- I wrote that in an extreme hurry > before getting to lunch. > > > The pseudoprimetest > > used internally by pari should never declare a prime number > > to be composite. Most likely they use Miller Rabin which > > has this property. I will check. > > Yes, please do. > > William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
