num-prime

Crates.io	num-prime
lib.rs	num-prime
version	0.4.4
created_at	2022-01-08 04:40:19.256443+00
updated_at	2024-05-06 16:16:04.413893+00
description	Generic and optimized primality test, factorization and various number theoretic functions with arbitrary precision based on `num`.
homepage
repository	https://github.com/cmpute/num-prime
max_upload_size
id	510087
size	470,770

Jacob Zhong (cmpute)

documentation

https://docs.rs/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: 96