#number-theory #primes #bignum #factor

number-theory

Fast primality, factorization and elementary number theory for primitive types, and arbitrary-precision integers

4 releases

Uses new Rust 2021

new 0.0.3 Jan 17, 2022
0.0.2 Jan 10, 2022
0.0.1 Jan 4, 2022
0.0.0 Dec 26, 2021

#209 in Math

Download history 20/week @ 2021-12-25 20/week @ 2022-01-01 31/week @ 2022-01-08 23/week @ 2022-01-15

94 downloads per month
Used in 2 crates

MIT license

240KB
4K SLoC

Currently the fastest library for factorization and primality checking in the interval 0;2^64 that is available in Crates.io and possibly in the entire Rust-lang ecosystem. 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
  • Factorization
  • Euler totient
  • Integer radical (not sqrt)
  • K-free
  • Modular exponentiation and quadratic residues
  • Legendre symbol

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
  • Sqrt/nth root
  • Exponentiation
  • Logarithms

Usage is fairly simple

// include NT functions
use number_theory::traits::NumberTheory;
// include arbitrary-precision arithmetic
use number_theory::arithmetic::mpz::Mpz;
  // Sign, generally unnecessary for ENT
//use number_theory::arithmetic::sign::Sign; 
// unsigned from string, defaults to Sign::Positive
let mersenne = Mpz::u_from_string("127"); 
assert_eq!(mersenne.is_prime(), true);

No runtime deps