#prime #number-theory #big-int #primality-test

num-prime

Generic and optimized primality test, factorization and various number theoretic functions with arbitrary precision based on num

17 releases

0.4.4 May 6, 2024
0.4.3 Dec 23, 2022
0.4.2 Oct 10, 2022
0.4.1 May 24, 2022
0.3.0-alpha Mar 3, 2022

#88 in Math

Download history 5115/week @ 2024-03-04 5662/week @ 2024-03-11 6722/week @ 2024-03-18 6195/week @ 2024-03-25 5268/week @ 2024-04-01 8075/week @ 2024-04-08 8188/week @ 2024-04-15 10446/week @ 2024-04-22 14768/week @ 2024-04-29 10938/week @ 2024-05-06 8916/week @ 2024-05-13 10181/week @ 2024-05-20 12381/week @ 2024-05-27 14162/week @ 2024-06-03 15052/week @ 2024-06-10 14297/week @ 2024-06-17

57,372 downloads per month
Used in 15 crates

Apache-2.0

440KB
7K SLoC

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).

Dependencies

~3.5MB
~64K SLoC