素数分解

程序用于将自然数 N（上限为 u128::MAX）分解为其素数因子的乘积。根据算术基本定理，每个大于1的自然数要么是素数本身，要么可以表示为素数的乘积，这些素数乘积唯一，只考虑这些素数的顺序。

整个分解算法包括使用前一千个素数的试除法、费马分解法以及使用苏山参数化的射影坐标的Lenstra椭圆曲线分解。在费马分解之后，在进入椭圆曲线分解步骤之前，会检查该数的可能素性，这取决于数字的大小，使用 Miller-Rabin 或强 Baillie-PSW 素性测试。后者在它所使用的数字范围（128位）中不是确定的，但尚未发现反例。

安装

要将作为依赖项（库目标）安装，请将以下内容添加到您的 Cargo.toml

[dependencies]
prime_factorization = "1.0.4"

对于二进制目标，运行命令 cargo install prime_factorization 并确保安装位置在 PATH 中（即 Rust 工具链已正确配置）。

使用

如下使用库

use prime_factorization::Factorization;

// Factorize following semiprime
let num: u128 = 3_746_238_285_234_848_709_827;

let factor_repr = Factorization::run(num);

// Check that the returned factors are correct
assert_eq!(factor_repr.factors, vec![103_979, 36_028_797_018_963_913]);

请注意，所有从 2 到 2^128 - 1 的整数都可以分解，但所使用的整数类型必须实现（以及一些其他）特性行为 From<u32>。

有时检查某个特定数字是否为素数可能就足够了

use prime_factorization::Factorization;

let num: u128 = 332_306_998_946_228_968_225_951_765_070_086_139;

// Use the `is_prime` convenience field
assert_eq!(Factorization::run(num).is_prime, true);

如果安装了二进制目标，CLI 可以如下使用

prime_factorization num [-p | --pretty]

其中参数 num 是必填的自然数，选项 -p 或 --pretty 是打印标志，当提供时，导致输出以正确的因子表示格式 $$p_1^{k_1} * ... * p_m^{k_m}$$。没有该标志，输出仅列出从最小到最大的所有素数因子。

备注

• 椭圆曲线因式分解必须使用操作系统线程以提高效率。线程数应设置为至少两个，最好低于CPU核心数以优化性能。在性能方面，较低值（2-5）似乎是最优，但根据基准测试，较大的128位半素数可以通过较大的线程数更快地分解。可以通过《factor》模块中的MAX_THREADS_常量更改线程数。

• Miller-Rabin和Baillie-PSW素性测试是概率性的，但在这个程序使用的数字范围内不包含反例。椭圆曲线因式分解使用曲线上的随机初始点，这可能导致执行时间有所偏差。

许可证

本程序受CC0v1许可。