#primes #factor #number-theory #bignum

number-theory

Fast primality, factorization and elementary number theory for integer types

19 releases

0.0.18 Jan 14, 2023
0.0.17 Dec 1, 2022
0.0.16 Oct 26, 2022
0.0.6 Mar 1, 2022
0.0.0 Dec 26, 2021

#166 in Math

Download history 33/week @ 2022-10-11 3/week @ 2022-10-18 49/week @ 2022-10-25 21/week @ 2022-11-01 19/week @ 2022-11-08 17/week @ 2022-11-15 28/week @ 2022-11-22 33/week @ 2022-11-29 22/week @ 2022-12-06 31/week @ 2022-12-13 45/week @ 2022-12-20 14/week @ 2022-12-27 3/week @ 2023-01-03 35/week @ 2023-01-10 16/week @ 2023-01-17 23/week @ 2023-01-24

79 downloads per month
Used in 2 crates

MIT license

535KB
8K SLoC

ENT

Elementary Number Theory for Integers in Rust

The fastest provably correct library for primality checking in the interval 0;2^64 + 2^49 that is publicly available. Algebraic definitions of primality and factorization are used, permitting checks like -127.is_prime() to return true and unique factorizations to be considered unsigned.

Currently implements these functions

  • Primality checking and proving
  • Factorization
  • GCD, Extended GCD
  • Euler,Jordan & Carmichael totients
  • Dedekind psi
  • Liouville, and Mobius function
  • Prime-counting function/nth-prime, and prime lists
  • Integer sqrt/nth root
  • Integer radical
  • K-free
  • Quadratic and Exponential residues
  • Legendre & Jacobi symbols
  • Smoothness checks

Additionally this library has an implementation of the previous NT functions for arbitrary-precision integers, plus some elementary arithmetic. Multiplication utilizes Karatsuba algorithm, otherwise all other arithmetic can be assumed to be naive.

  • Addition/subtraction
  • Multiplication
  • Euclidean Division
  • Conversion to and from radix-10 string
  • Successor function (+1)
  • SIRP-factorials {generalization of factorials}
  • Conditional Interval Product (CIP factorial)
  • Sqrt/nth root
  • Exponentiation
  • Logarithms
  • Probable pseudoprime construction

Usage is fairly simple

// include NT functions
use number_theory::NumberTheory;
// include arbitrary-precision arithmetic
use number_theory::Mpz;
  // Sign, generally unnecessary for ENT
//use number_theory:Sign; 
let mersenne = Mpz::from_string("-127").unwrap(); 
assert_eq!(mersenne.is_prime(), true);
 // Or for a more complex example
 
 // check if x mod 1 === 0, trivial closure
 let modulo = |x: &u64| {if x%1==0{return true} return false};
 
  //Generate  872 factorial, using the above trivial function
  // this can be just as easily reproduced as Mpz::sirp(1,872,1,0);
 let mut factorial = Mpz::cip(1, 872,modulo);
 
 // Successor function, increment by one
 factorial.successor();
 
 // 872! + 1 is in-fact a factorial prime
 assert_eq!(factorial.is_prime(),true)

No runtime deps

Features

  • parallel