Lib.rs

Pollard的p-1分解算法

这是Pollard的p-1分解算法的Rust实现。如果n的因子p是b-powersmooth的，则该算法可以快速分解整数n。这意味着p的所有质数幂都小于或等于b。

安装

在Cargo.toml文件中将它作为依赖项添加

pollard-p-minus-one = "*"

请注意，由于这个crate依赖于仅能在nightly上编译的ramp，因此您必须使用nightly构建才能使用此crate。

示例

将您要分解的整数n和您对b的猜测传递给factor函数。例如，如果n是299，它可以分解如下

use pollard_p_minus_one::factor;

let n = 299;
let b = 4;
println!("Found factor {}", factor(n, b).unwrap());

在这种情况下，4是b的好选择，因为229有一个因子p为13，而p - 1 是12，它是4-powersmooth（2^2 * 3^1 = 12），所有质数幂都小于或等于4）。如果选择一个太小或太大的b，将找不到因子。在这种情况下，b为3将不起作用，虽然从4到10的b都可以工作，但11或更高的b将不起作用。

显然，您不能依赖知道n的分解来选择b，因为整个目的就是找到那个分解。如果您猜测b的值太大（如2^32），此实现将尝试使用增量10000分解n，直到猜测值。这并不保证成功，并且会比正常速度慢一些，因此您越接近b的真实值，效果越好。

如果您要分解的整数大于 u64，可以使用来自 ramp 包的 ramp::Int::from_str() 函数将其传递给 factor 函数： factor(ramp::Int::from_str("348242219231"), b)。