17 个版本
| 0.6.1 | 2023 年 8 月 31 日 |
|---|---|
| 0.5.1 | 2022 年 5 月 30 日 |
| 0.2.1 | 2022 年 3 月 30 日 |
#42 in 数学
109,043 每月下载量
用于 76 个 Crates (12 直接)
145KB
3.5K SLoC
num-modular
Rust 中整数除法和模算术的泛型实现。它提供基本的操作符和一个用于表示模环中整数的类型。具体支持以下功能：
- 常见模运算：
add、sub、mul、div、neg、double、square、inv、pow - Montgomery 形式的优化模运算
- 以伪梅森素数为模的优化模运算
- 快速的整数可除性检查
- 勒让德、雅可比和克罗内克符号
它还支持各种整数类型后端，包括原始整数和 num-bigint。请注意，此 crate 还支持 [no_std]。要启用与 std 相关的功能，请启用 crate 的 std 功能。
lib.rs:
此 crate 为各种整数类型提供高效的模运算，包括原始整数和 num-bigint。后者是可选的。
为了实现快速的模运算，请使用静态 new() 或关联的 [ModularInteger::convert()] 函数将整数转换为任何 [ModularInteger] 实现。一些内置的 [ModularInteger] 实现包括 [MontgomeryInt] 和 [FixedMersenneInt]。
示例代码
use num_modular::{ModularCoreOps, ModularInteger, MontgomeryInt};
// directly using methods in ModularCoreOps
let (x, y, m) = (12u8, 13u8, 5u8);
assert_eq!(x.mulm(y, &m), x * y % m);
// convert integers into ModularInteger
let mx = MontgomeryInt::new(x, &m);
let my = mx.convert(y); // faster than static MontgomeryInt::new(y, m)
assert_eq!((mx * my).residue(), x * y % m);
快速除法/模运算的比较
这些 crate 提供了几个快速除法/模运算技巧，它们的区别如下
- [PreModInv]：预计算除数的模逆，仅适用于精确除法
- Barret（待实现）：预计算除数的倒数（有理近似），适用于快速除法和模运算
- [Montgomery]：通过移位将被除数转换为特殊形式并预计算模逆，仅适用于快速模运算，但比 Barret 简化更快
- 【梅森固定化】在 2^127 下的模运算形式
2^P-K的专门化。
依赖关系
约 120KB