### 1 unstable release

0.1.0 | Nov 11, 2020 |
---|

#**1416** in Algorithms

**MIT**license

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

if a factor `n`

of `p`

is `n`

. This means that all prime powers of `b-powersmooth`

are less than or equal to `p`

.`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

you want to factor and your guess for `n`

to the `b`

function. For example, if `factor`

is 299, it can be factored as follows:`n`

`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

in this case because 229 has a factor `b`

of 13, and `p`

is 12 which is 4-powersmooth (`p - 1`

`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

to choose `n`

, 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 `b`

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 `n`

the better.`b`

If the integer you'd like to factor is larger than a

, you can pass it to `u64`

using the `factor`

function from the ramp crate: `ramp ::`

`Int`from_str

`::``(`

`)`

`factor``(``ramp``::``Int``::`from_str`(``"`348242219231`"``)``,` b`)`

.#### Dependencies

~2MB

~37K SLoC