Crate crypto_primes

Prime number tools for crypto-bigint

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

• Generating random primes and safe primes of given bit size;
• Sieving iterator;
• Miller-Rabin test;
• Strong and extra strong Lucas tests, and Lucas-V test.

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

Most users will be using the small set of functions exported from the top level, providing “pre-packaged” prime finding functionality with sane defaults.

Example

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

use crypto_bigint::U256;
let prime = crypto_primes::generate_prime::<U256>(196);
assert!(crypto_primes::is_prime(&prime));

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

use crypto_bigint::U1024;
let prime = crypto_primes::generate_safe_prime::<U1024>(64);
assert!(crypto_primes::is_safe_prime(&prime));

Advanced

Advanced users can use the hazmat module in the library to build a custom prime finding solution that best fit their needs, e.g. by picking different Lucas bases or running Miller-Rabin tests with particular bases.

Features

The following features are available:

• default-rng: Use the OS default CSPRNG, OsRng. Enabled by default.
• multicore: Enables additional parallel prime finding functions. Disabled by default.

Modules

hazmat

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

Structs

SieveIterator

A structure that chains the creation of sieves, returning the results from one until it is exhausted, and then creating a new one.

Traits

RandomPrimeWithRng

Provides a generic way to access methods for random prime number generation and primality checking, wrapping the standalone functions (is_prime_with_rng etc).

SieveFactory

A type producing sieves for random prime generation.

Functions

generate_primedefault-rng

Returns a random prime of size bit_length using OsRng as the RNG.

generate_prime_with_rng

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

generate_safe_primedefault-rng

Returns a random safe prime (that is, such that (n - 1) / 2 is also prime) of size bit_length using OsRng as the RNG.

generate_safe_prime_with_rng

Returns a random safe prime (that is, such that (n - 1) / 2 is also prime) of size bit_length using the provided RNG.

is_primedefault-rng

Probabilistically checks if the given number is prime using OsRng as the RNG.

is_prime_with_rng

Probabilistically checks if the given number is prime using the provided RNG.

is_safe_primedefault-rng

Probabilistically checks if the given number is a safe prime (that is, such that (n - 1) / 2 is also prime) using OsRng as the RNG.

is_safe_prime_with_rng

Probabilistically checks if the given number is a safe prime using the provided RNG.

sieve_and_find

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