Skip to content

Latest commit

 

History

History
24 lines (17 loc) · 1.21 KB

README.md

File metadata and controls

24 lines (17 loc) · 1.21 KB

Baillie-PSW

Python implementation of the Baillie-PSW primality test, based on the following papers:

Files in the repository are:

  • baillie_psw.py contains the implemetation of the algorithm

  • baillie PSW test suite.py has a suite of tests of the algorithm, using sieve and segmented sieve to generate test numbers

  • Compare pseudoprimes.py is a test suite to compare the performance and correctness of the standard and strengthened Lucas algorithms, using known pseudoprimes obtained from Pseudoprime Statistics, Tables, and Data (Fermat, Miller-Rabin, Lucas, Fibonacci, Pell, Frobenius, Baillie-PSW), Dana Jacobsen, 31 March 2020, http://ntheory.org/pseudoprimes.html

My implementation of the strengthened algorithm is slightly slower than the standard algorithm, so the standard algorithm is used in baillie_psw