Prime number tools for crypto-bigint

This library implements prime number generation and primality checking for crypto-bigint integers.

At a high level, provides two primality tests that can be used by themselves or to generate random primes:

• The BPSW'21 test which improves on the commonly used BPSW'80, based on Baillie et al "Strengthening the Baillie-PSW primality test", Math. Comp. 90 1931-1955 (2021), DOI: 10.1090/mcom/3616;
• The test prescribed by the FIPS-186.5 standard, along with a function to calculate the required number of Miller-Rabin test iterations depending on the prime size and the bound on the probability of a false positive.

The generated primes can have additional constraints imposed on them, like having certain bits set, or requiring the primes to be safe.

Advanced users can use the primality test components from the hazmat module to build a custom prime finding solution that best fit their needs:

• Sieving iterator;
• Miller-Rabin test;
• Lucas test with a choice of base and a specific variation.

The library is no-std compatible and contains no unsafe code.

Example

Find a 196 bit prime returned in a 256-bit long crypto_bigint::U256:

use crypto_bigint::U256;
use crypto_primes::{Flavor, is_prime, random_prime};

let prime = random_prime::<U256, _>(&mut rand::rng(), Flavor::Any, 196);
assert!(is_prime(Flavor::Any, &prime));

Find a 64 bit safe prime returned in a crypto_bigint::U1024:

use crypto_bigint::U1024;
use crypto_primes::{Flavor, is_prime, random_prime};

let prime = random_prime::<U1024, _>(&mut rand::rng(), Flavor::Safe, 64);
assert!(is_prime(Flavor::Safe, &prime));

random_prime() returns primes with MSB set. If a different behavior is desired, it can be done by manually creating a sieve:

use crypto_primes::{
    Flavor,
    hazmat::{SetBits, SmallFactorsSieveFactory},
    is_prime, random_prime, sieve_and_find,
};
use crypto_bigint::U256;

let flavor = Flavor::Any;
let factory = SmallFactorsSieveFactory::<U256>::new(flavor, 256, SetBits::TwoMsb).unwrap();
let prime = sieve_and_find(
    &mut rand::rng(),
    factory,
    |_rng, candidate| is_prime(flavor, candidate)
).unwrap().unwrap();
assert!(is_prime(flavor, &prime));

Features

The following features are available:

• multicore: Enables additional parallel prime finding functions. Disabled by default.