Lib.rs

Pollard's p-1 Factoring Algorithm

A Rust implementation of Pollard's p-1 factoring algorithm. This algorithm can quickly factor an integer n if a factor p of n is b-powersmooth. This means that all prime powers of p are less than or equal to b.

Installation

Add it as a dependency in your Cargo.toml file:

pollard-p-minus-one = "*"

Note that because this crate depends on ramp which only compiles on nightly, you must use a nightly build to use this crate.

Example

Pass the integer n you want to factor and your guess for b to the factor function. For example, if n is 299, it can be factored as follows:

use pollard_p_minus_one::factor;

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

4 is a good choice for b in this case because 229 has a factor p of 13, and p - 1 is 12 which is 4-powersmooth (2^2 * 3^1 = 12, all prime powers are less than or equal to 4). If you choose a b that's too small or too large, no factors will be found. A b of 3 won't work in this case, and while a b from 4 to 10 will work, 11 or higher won't work.

Obviously, you can't rely on knowing the factorization of n to choose b, since the whole point is to find that factorization. If you guess a large value for b (like 2^32), this implementation will attempt to factor n using increments of 10000 up to your guessed value. This isn't guaranteed to work and will be a little slower than normal, so the closer you can get to the real value of b the better.

If the integer you'd like to factor is larger than a u64, you can pass it to factor using the ramp::Int::from_str() function from the ramp crate: factor(ramp::Int::from_str("348242219231"), b).