Module prime

Implements probabilistic prime checkers.

Functions

next_prime

Calculate the next larger prime, given a starting number n.

probably_prime

ProbablyPrime reports whether x is probably prime, applying the Miller-Rabin test with n pseudorandomly chosen bases as well as a Baillie-PSW test.

probably_prime_lucas

Reports whether n passes the “almost extra strong” Lucas probable prime test, using Baillie-OEIS parameter selection. This corresponds to “AESLPSP” on Jacobsen’s tables (link below). The combination of this test and a Miller-Rabin/Fermat test with base 2 gives a Baillie-PSW test.

probably_prime_miller_rabin

Reports whether n passes reps rounds of the Miller-Rabin primality test, using pseudo-randomly chosen bases. If force2 is true, one of the rounds is forced to use base 2.