This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author remi.lapeyre
Recipients jfine2358, mark.dickinson, remi.lapeyre, rhettinger, serhiy.storchaka, steven.daprano, tim.peters, trrhodes
Date 2020-05-05.09:53:22
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
>> Regardless, how can we best move forward with this idea?

> Provide a pull request.

Hi, I looked into what scientific programs where doing. Most of them uses a form of the Baillie–PSW primality test which is a probabilistic primality test that's never wrong up to 2**64 and for which their is currently no known pseudoprime.

This first version I wrote uses a deterministic variant of the Miller-Rabin test for n < 3317044064679887385961981. For larger n, a probabilistic Miller-Rabin test is used with s=25 random bases. The probabilistic Miller-Rabin test is never wrong when it concludes that n is composite and has a probability of error of 4^(-s) when it concludes that n is prime.

The implementations of next_prime() and previous_prime() are straightforward and factorise() uses the Phollard's rho heuristic which gives satisfactory results for numbers with small factors. It's a generator as it may hang when n has very large factors e.g. 2**(2**8)+1.

I implemented all functions Steven D'Aprano suggested but did not bother with the sieve as Tim Peters already provided one in the python-ideas thread. The code is in imath for now but I can move it.

Hopefully this is enough to bikeshed the API, if this proposal is accepted I will write more tests and fix any bug found.
Date User Action Args
2020-05-05 09:53:22remi.lapeyresetrecipients: + remi.lapeyre, tim.peters, rhettinger, mark.dickinson, steven.daprano, serhiy.storchaka, jfine2358, trrhodes
2020-05-05 09:53:22remi.lapeyresetmessageid: <>
2020-05-05 09:53:22remi.lapeyrelinkissue40028 messages
2020-05-05 09:53:22remi.lapeyrecreate