factor-semiprime

An implementation of the Pollard's rho algorithm for factoring semiprime numbers

Why?

Semiprimes (the product of two primes) are much used in cryptography, because multiplying huge primes is waaay faster than factoring the result. This repository contains an algorithm that attempts to do the hard part: factor huge semiprimes.

How to use?

sh $ cargo build --release $ echo 18851959175571007 | ./target/release/factor-semiprime 18851959175571007 = 160097647 * 117752881

How to generate semiprimes?

You can use Symja or Mathics to generate random primes and multiply them. Here is a code example that works on both projects: wl (* Replace the range bellow with the desired range *) r := RandomPrime[{10^8, 10^9}]; (* p is a pair of two random primes *) p = {r, r}; (* Print the primes *) Print[p]; (* Print the product of the two random primes *) Print[Times @@ p];

How fast is it?

```sh $ time echo 437 | ./target/release/fator-semiprime 437 = 23 * 19

real 0m0.008s user 0m0.003s sys 0m0.007s

$ time echo 64786756484626223 | ./target/release/fator-semiprime 64786756484626223 = 222522227 * 291147349

real 0m0.026s user 0m0.026s sys 0m0.002s $ ```