Crate crypto_primes 

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.

Modules

fips

Functions implementing the functionality prescribed by FIPS-186.5 standard.

hazmat

Components to build your own primality test. Handle with care.

multicoremulticore

Prime-finding functions that can parallelize across multiple cores.

Enums

Error

Errors returned by the crate’s API.

Flavor

The specific category of primes.

Functions

is_prime

Checks if the given number is prime.

random_prime

Returns a random prime of size bit_length using the provided RNG.

sieve_and_find

Sieves through the results of sieve_factory and returns the first item for which predicate is true.