Module prime 

Implements probabilistic prime checkers.

Structs

BIG_1 🔒

BIG_2 🔒

BIG_3 🔒

BIG_64 🔒

Constants

INCR_LIMIT 🔒

NUMBER_OF_PRIMES 🔒

PRIMES_A 🔒

PRIMES_B 🔒

PRIME_BIT_MASK 🔒

Records the primes < 64.

PRIME_GAP 🔒

Functions

get_bit 🔒

Returns the i-th bit.

is_bit_set 🔒

Checks if the i-th bit is set

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.