6个版本

0.3.0	2021年12月6日
0.2.1	2021年11月6日
0.2.0	2021年9月17日
0.1.2	2021年1月11日
0.1.1	2020年5月9日

#691 in 数学

277次每月下载
在 5 crates 中使用

Apache-2.0 OR MIT

40KB
256 行

Num-Primes: CSPRNG大合数、素数、安全素数生成器

此crate提供了用于在Rust中生成大、密码学随机、无符号整数的**精美简洁API**，包括但不限于**合数、素数和安全素数**。

充分利用了在**稳定Rust**上的num crate。

阅读关于
阅读许可
阅读贡献

注意

请注意，在此程序中存在一个关键的bug，我似乎无法修复，其中将一些素数标记为非素数。它位于miller-rabin实现中，我似乎无法修复它。如果有任何人愿意尝试，请随时查看问题标签页以获取有关bug的信息，并在找到修复方法时提交PR。

用法

将其添加到您的Cargo.toml

[dependencies]
num-primes = "0.2.0"

警告

当前在is_prime()和is_composite()中存在一个严重bug，使得一些值返回错误。例如，一个素数有时会被标记为合数，除非它是通过相同的测试生成的，因为它们使用相同的测试来测试素性。

如何使用

此库中包含三个主要结构体

结构体	描述
Generator	允许随机生成合数、素数和安全素数。
Verification	允许验证合数、素数、安全素数和非常平滑的数。
Factorization	允许将合数和素数分解为其最大的素数因子。

Generator

生成合数

此函数将生成一个n-bits的合数。

use num_primes::Generator;

fn main(){
  // Generate Composite of 1024 bits
  let composite = Generator::new_composite(1024);
}

生成素数

此函数将生成一个n-bits的素数。

use num_primes::Generator;

fn main(){
  // Generate two primes (p,q) of 512 bits each
  let p = Generator::new_prime(512);
  let q = Generator::new_prime(512);
  
  // Multiply to get the modulus (n)
  let n = p * q;
}

生成安全素数

此函数将生成一个n位的安全素数。此函数使用openssl使用的相同测试来生成安全素数，该测试为(n-1)/2。

此函数相当耗时，应避免用于大型尺寸。

use num_primes::Generator;

fn main(){
  // Generate Safe Prime of 64 bits | Uses (n-1)/2 to check
  let safe_prime = Generator::safe_prime(64);
}

生成大无符号整数

此函数将生成一个n位的大无符号整数。由于没有进行检查，此函数比生成合数或素数要快。

use num_primes::Generator;

fn main(){
  // Generate a Large Unsigned Integer of 1024 bits without running any checks
  let x = Generator::new_uint(1024);
}

Verification

警告：目前存在一个错误，导致某些素数的验证失败。在使用此功能时请小心。

验证合数

此函数将通过返回布尔值来验证BigUint类型是否为合数。

use num_primes::{Generator,Verification};

fn main(){
  // Generates Composite Number of 1024 bits
  let x = Generator::new_composite(1024);
  
  // Check if the number is a Composite Number
  let is_composite: bool = Verification::is_composite(&x);
  
  // Asserts that 'is_composite' is true
  assert_eq!(is_composite, true);
}

验证素数

此函数将通过返回布尔值来验证BigUint类型是否为素数。

use num_primes::{Generator,Verification};

fn main(){
  // Generates Prime Number of 1024 bits
  let x = Generator::new_prime(1024);
  
  // Check if the number is a Prime Number
  let is_prime: bool = Verification::is_prime(&x);
  
  // Asserts that 'is_prime' is true
  assert_eq!(is_prime, true);
}

验证安全素数

此函数将通过返回布尔值来验证BigUint类型是否为安全素数。

use num_primes::{Generator,Verification};

fn main(){
  // Generates a Safe Prime Number of 128 bits
  let x = Generator::safe_prime(128);
  
  // Check if the number is a Safe Prime Number
  let is_safe_prime: bool = Verification::is_safe_prime(&x);
  
  // Asserts that `is_safe_prime` is true
  assert_eq!(is_safe_prime, true);
}

[实验性] 验证VSN（光滑数）

实验性：请目前避免使用此函数

阅读Wolfram Alpha - 光滑数

阅读OEIS - P光滑数

阅读维基百科 - VSN和VSSR示例

此函数将验证一个数是否为非常光滑数。它接受以下三个参数：

m: &BigUint | 素数
n: f64 | 常数
c: u32 | 常数

它遵循以下方程

返回m的最大素数因子为p

如果p <= log(n)^c，则它是p光滑

如果p > log(n)^c，则它不是p光滑

use num::traits::FromPrimitive; use num_bigint::BigUint; use num_primes::Verification; fn main() { // Set BigUint To 7u64 let x: BigUint = BigUint::from_u64(7u64).unwrap(); // Verify Its A Smooth Number with parameters // m = 7 (&BigUint) // n = 31.0 (f64) // c = 5 (u32) let result: bool = Verification::is_very_smooth_number(&x,31.0,5); // Print What Type of Smooth Number It Is And Whether Or Not It Is Smooth println!("Is A {} Smooth Number: {}",x,result); // This problem should be 7-smooth assert_eq!(result, true); } Factorization 注意：分解仍在进行中。素数分解阅读GeeksforGeeks - 打印给定数字所有素数因子的有效程序此函数让您可以将合数和素数分解以找到它们的最大素数因子。 use num_primes::{Generator,Factorization}; fn main() { // Generates New Unsighed Integer of 32 bits let uint = Generator::new_uint(32); // Prime Factorization Returns Option<BigUint> let factor = Factorization::prime_factor(uint); // match the Option<BigUint> match factor { Some(factor) => println!("Largest Prime Factor: {}",factor), None => println!("No Prime Factors Found"), } } 如何工作以下列出了步骤，其中n是正在分解的输入数字首先使用素性检验来确定该数是否为素数。当n是偶数时，除以2 在第1步之后，n必须是奇数。 n_sqrt = 求n的平方根从i = 3循环到n_sqrt 当i / n 除以i 当i除以n失败时，将 i 增加 2 并继续如果 n 是一个质数且 2 > n 返回 n 关于质数生成设计质数生成及其部分代码基于 Snips-AI 的 Medium 博客关于生成质数。对判断一个数是否为质数进行了谨慎的尝试。该数经过生成阶段和 3 次测试以确定其是否为质数生成阶段将一个参数传递给生成函数，该参数指示质数应有多少位。用户空间 CSPRNG 由操作系统初始化，使用 rand crate 生成随机数。生成一个无符号整数，直到它通过质数测试。将数字发送到通过四个测试处理质数测试这些数字经过多次测试，以确定它们是合数还是质数。检查该数是否为偶数。使用前 2048 个质数的数组来检查该数是否能被数组中的任何质数整除。执行费马小定理执行 Miller-Rabin 质数测试，这是官方 RSA 文档和 NIST 推荐的生成质数的黄金标准，进行 16 次迭代，与苹果的加密系统相同。如果数字通过这些测试，则认为它有很高的概率是质数。您可以在 Wolfram Alpha 上通过简单地输入质数来验证它们。安全质数通过检查 (p-1)/2 是否是上述测试中列出的质数来生成安全质数。 OpenSSL-Prime 与 Num-Primes https://security.stackexchange.com/questions/176394/how-does-openssl-generate-a-big-prime-number-so-fast OpenSSL LTS (1.1.1) 有一个关于质数生成的文档页面，包括如何生成安全质数。由于它们的代码安全以及代码已经过审计，因此应首选 OpenSSL 进行严肃的加密实现。在某些情况下，如嵌入式系统或 OpenSSL 过度的情况下，Num-Primes 可能很有用。 OpenSSL-prime 使用 (n-1)/2 生成安全质数，但效率更高对质数执行默认的 20 检查。 Num-Primes 使用 (n-1)/2 生成安全质数，但出于未知原因需要更长的时间通过 4 种不同的质数测试对质数执行默认的 16 检查支持 #[no_std] 和稳定的 rust 在需要时可能很有用，比如在使用 OpenSSL 会过度的情况下。 num-primes 和 ramp-primes 之间的差异 ramp-primes 是使用 ramp 库实现的质数生成器的原始实现。 num-primes 是使用 num 库改进的实现，支持稳定版并提供无_std 支持。 num-primes (稳定版) 使用 num，这是一个纯 Rust 实现，用于数值类型和特性。 num 是稳定的，可以在默认、Beta 和 Nightly 分支上运行。 num 是用纯 Rust 编写的 num 实现了更多功能 num 约有 ~600万次下载 num 比 ramp 更发达。 num-primes 有更好的 API 和文档更多功能无_std 支持 ramp-primes (不稳定) 使用 ramp，这是一个用于处理比通常能处理的更大的数字的高性能多精度（也称为“大数”）库。 ramp 只在不稳定 Rust（nightly 分支）上运行。 ramp 用 Rust 和内联汇编编写（存在安全风险） ramp 通常更快 ramp 专注于多精度算术 ramp 约有 ~17,000 次下载 ramp 没有像 num 那么发达。 ramp-primes 是第一个实现通常在生成时更快功能较少仅在不稳定 Rust（Nightly 构建）上运行许可协议根据您的选择，受以下任何一个许可协议的约束： Apache License，版本 2.0 MIT 许可证。贡献除非您明确表示，否则根据 Apache-2.0 许可证定义的，您有意提交的任何贡献，只要包含在本作品中，都将按上述方式双许可，而不附加任何其他条款或条件。

依赖关系约 1.5MB 约 26K SLoC log num 0.4 num-bigint 0.2.6+rand num-traits rand 0.5.6