ENT

Rust 中整数初等数论

目前公开可用的区间 0;2^64 + 2^49 中素性检验最快的证明正确的库。使用素性和因式分解的代数定义，允许进行如 -127.is_prime() 返回 true 以及将唯一因式分解视为无符号的检查。作为 number-theory 发布在 crates.io 上

当前实现以下功能

• 素性
• 因式分解
• 最大公约数，扩展最大公约数
• Carmichael, Euler & Jordan 同余数
• Dedekind psi
• Liouville 和 Möbius 函数
• 素数计数函数/nth-prime，以及素数列表
• 整数平方根/nth 次方根
• 整数根号
• K-free
• 二次和指数剩余
• 勒让德符号
• Jacobi 符号
• 光滑度检查

此外，此库还实现了以前 NT 函数的任意精度整数实现，以及一些基本的算术。乘法使用 Karatsuba 算法，其他所有算术可以假设为朴素。

• 加法/减法
• 乘法
• 欧几里得除法
• 转换为和从十进制字符串转换
• 后继函数（+1）
• SIRP 因子（阶乘的推广）
• 条件区间积（CIP 阶乘）
• 平方根/nth 次方根
• 指数运算
• 对数
• 可能的伪素数构造

使用相当简单

// 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)