1 unstable release
0.1.0 | Nov 11, 2020 |
---|
#1416 in Algorithms
7KB
57 lines
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)
.
Dependencies
~2MB
~37K SLoC