factor-semiprime

半素数因式分解Pollard's rho算法的实现

为什么？

半素数（两个素数的乘积）在密码学中应用广泛，因为乘以巨大的素数比分解结果要快得多。此存储库包含一个尝试解决困难部分的算法：分解巨大的半素数。

如何使用？

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

如何生成半素数？

您可以使用 Symja 或 Mathics 生成随机素数并将它们相乘。以下是一个适用于两个项目的代码示例

(* 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];

它有多快？

$ 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
$