### 24 releases

0.0.24 | Nov 9, 2023 |
---|---|

0.0.23 | Apr 4, 2023 |

0.0.21 | Feb 16, 2023 |

0.0.17 | Dec 1, 2022 |

0.0.0 | Dec 26, 2021 |

#**160** in Math

**32** downloads per month

Used in **2** crates

**MIT**license

305KB

7.5K
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.Published as number-theory on crates.io

Currently implements these functions

- Primality
- Factorization
- GCD, Extended GCD
- Carmichael,Euler & Jordan 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 symbol
- Jacobi symbol
- 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``)`

#### Dependencies

~1.5MB

~17K SLoC