Module num_bigint_dig::prime

source ·
Expand description

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.