Crate num_prime

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
  • A naive implementation of the sieve of Eratosthenes
  • Unified API to support other prime generation backends
  • Generate random (safe) primes
  • Find previous prime / next prime
• Integer factorization
  • Trial division
  • Pollard’s rho algorithm
  • Shanks’s square forms factorization (SQUFOF)
  • Hart’s one line algorithm
  • Fast factorization of u64 integers
• 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, FactorizationConfig};
use num_prime::nt_funcs::{is_prime, factorize, 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 = factorize(c); // infallible factorization with default configuration
assert_eq!(fac.len(), 2); // 2^83-1 = 167 * 57912614113275649087721

let config = FactorizationConfig::strict();
let (fac, rem) = factors(c, Some(config)); // fallible factorization with customized configuration
assert!(fac.len() == 2 && rem.is_none());

Backends

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.

Modules

buffer

Implementations and extensions for PrimeBuffer, which represents a container of primes

detail

Implementation details for this crate.

factor

Implementations for various factorization algorithms.

nt_funcs

Standalone number theoretic functions

Structs

FactorizationConfig

Represents a configuration for integer factorization

PrimalityTestConfig

Represents a configuration for a primality test

Enums

Primality

This enum describes the result of primality checks

Traits

BitTest

This trait support unified bit testing for (unsigned) integers

ExactRoots

Extension on num_integer::Roots to support perfect power check on integers

PrimalityUtils

This trait implements various primality testing algorithms

PrimeBuffer

This trait represents a general data structure that stores primes.

RandPrime

Supports random generation of primes