mirror of
https://github.com/uutils/num-prime.git
synced 2026-10-16 03:24:22 -07:00
Jacob Zhong
3b8ab4676a
Drop the temporary [patch.crates-io] section: dashu-int 0.6.2 publishes the num-modular integration this backend is built on (Reducer<UBig> for MontgomeryRepr, ModularSymbols for UBig, Pow<u32>, CheckedAdd, and the Integer::mod_floor fix). dashu-base stays at 0.6.1 - its content is unchanged in the 0.6.2 release, and dashu-int 0.6.2 itself depends on ^0.6.1.
num-prime
This crate provides utilities for prime number related functionalities:
- Primality testing
- Deterministic primality check of
u64integers (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
- Deterministic primality check of
- 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
u64andu128integers - Factorization beyond
u128, with Pollard's rho over Montgomery arithmetic
- 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 crates and most functions are decently optimized with pre-computed tables (see benchmark results here).