Crate num_prime

Expand description

This crate provides utilities for prime related functionalities and some basic number theoretic functions:

Primality testing
- Primality check
- Deterministic primality check of u64 integers (using a very fast hashing algorithm)
- Fermat probable prime test
- Miller-rabin probable prime test
- (strong/extra strong) Lucas probable prime test
- Baillie-PSW test
- Sophie Germain safe prime test
Primes generation and indexing
Integer factorization
Number theoretic functions
- Prime Pi function, its estimation, and its bounds
- Nth Prime, its estimation, and its bounds
- Moebius function

Usage

Most number theoretic functions can be found in nt_funcs module, while some of them are implemented as member function of num_modular::ModularOps or PrimalityUtils.

Example code for primality testing and integer factorization:

use num_prime::PrimalityTestConfig;
use num_prime::nt_funcs::{is_prime, factors};

let p = 2u128.pow(89) - 1; // a prime number
assert!(is_prime(&p, None).probably()); // use default primality check config
assert!(is_prime(&p, Some(PrimalityTestConfig::bpsw())).probably()); // BPSW test

let c = 2u128.pow(83) - 1; // a composite number
assert!(!is_prime(&c, None).probably());
let fac = factors(c, None); // use default factorization config
assert!(matches!(fac, Ok(f) if f.len() == 2)); // 2^83-1 = 167 * 57912614113275649087721

This crate is built with modular integer type and prime generation backends. Most functions support generic input types, and support for num-bigint is also available (it’s an optional feature). To make a new integer type supported by this crate, the type has to implement detail::PrimalityBase and detail::PrimalityRefBase. For prime generation, there’s a builtin implementation (see buffer module), but you can also use other backends (such as primal) as long as it implements PrimeBuffer.

Optional Features

big-int (default): Enable this feature to support num-bigint::BigUint as integer inputs.
big-table (default): Enable this feature to allow compiling large precomputed tables which could improve the speed of various functions with the cost of larger memory footprint.