num-prime

Crates.ionum-prime
lib.rsnum-prime
version0.4.4
sourcesrc
created_at2022-01-08 04:40:19.256443
updated_at2024-05-06 16:16:04.413893
descriptionGeneric and optimized primality test, factorization and various number theoretic functions with arbitrary precision based on `num`.
homepage
repositoryhttps://github.com/cmpute/num-prime
max_upload_size
id510087
size470,770
Jacob Zhong (cmpute)

documentation

https://docs.rs/num-prime

README

num-prime

This crate provides utilities for prime number related functionalities:

  • Primality testing
    • 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/next prime
  • Integer factorization
    • Trial division
    • Pollard's rho algorithm
    • Shanks's square forms factorization (SQUFOF)
    • Fast factorization of u64 and u128 integers
  • Number theoretic functions
    • Prime Pi function (number of primes under limit), its estimation and its bounds
    • Nth prime, its estimation and its bounds
    • Moebius function
    • Divisor Sigma function (in examples)
    • Prime Omega function (in examples)

It's based on the num creates and most functions are decently optimized with pre-computed tables (see benchmark results here).

Commit count: 94

cargo fmt