Question about Sage's is_pseudoprime() function (Baillie-PSW)

[neomacdev]

Hi,

The is_pseudoprime() function in Sage apparently uses the Baillie-PSW probabilistic primality test. (I've read a lot about primality tests, etc, in the last 6-8 months, but haven't paid much attention to the probabilistic tests.) I've noticed that this is_pseudoprime() function sometimes returns very fast even for LARGE (million+ digit) numbers. However, sometimes it seems to never return.

For example, I wanted to test / sieve a bunch of numbers that are around three-quarters of a million digits long using a probabilistic primality test. And sometimes the is_pseudoprime() function returns basically immediately, but for other input numbers I've let it run for 6 or 8 hours and it never returns. I don't know if this is a problem in Sage, where it is hanging. Or if this Baillie-PSW probabilistic primality test algorithm itself is actually taking 6+ hours to run on a 0.75+ million digit number.

Can anyone shed any light on this for me?

One example of a number I am trying to do a probabilistic primality test on, where Sage's is_pseudoprime() didn't return after 6+ hours of running.

#-----------------------------------------------------------------------------------------------------------------------

import datetime

n = 6 * Integer(2618163402417*2^1290001-1) * Integer(4547148564885*2^1290000-1) + 1

print "# of digits in n: ", len(str(n))
print "begin Baillie–PSW primality test at", str(datetime.datetime.now())

if n.is_pseudoprime() == false:
print "composite"
else:
print "maybe prime"

print "end Baillie–PSW primality test at", str(datetime.datetime.now())
print "done"

#-----------------------------------------------------------------------------------------------------------------------

[paulunderwood]

Does Sage use FFT multiplication? It is a must for such large numbers. Note that BPSW is 1+3 or 1+2 "selfridges" depending on the implementation, where 1 selfridge is the time taken to do a PRP test.

[neomacdev]

Originally Posted by paulunderwood

Does Sage use FFT multiplication? It is a must for such large numbers. Note that BPSW is 1+3 or 1+2 "selfridges" depending on the implementation, where 1 selfridge is the time taken to do a PRP test.

Sage certainly has fast multiplication routines. Although I don't know if those routines are being used for the multiplications done as part of the is_pseudoprime() function (Baillie-PSW test).

[paulunderwood]

At 0.75M+ digits use a 1 selfridge PRP test using PFGW and for added peace of mind use its "-tc" (combined tests) to test Fermat+Lucas. It will be much quicker than Sage.

I can only think Sage is either not using FFT or its FFT is much slower than Woltman's. (GWNUM is used in PFGW.)

Sage most likely does some trial division in its is_pseudpirme test. Hence the quick return for some numbers.