This package provides and implementation of bulk GCD (Greatest Common Divisor) algorithm by D. Bernstein.
GCD is useful for identifying weak keys in a large set of RSA keys. Such
sets were collected by researches (e.g. this paper). In order to
find weak keys a pairwise GCD has to be executed on all RSA moduli (i.e.
products of two primes P and Q, pertaining to each RSA private key).
However, each separate GCD computation takes considerable amount of time and the
naive pairwise process doesn't scale well (O(n^2)).
Instead of doing this search in a brute-force way, this module employs clever algorithm by D. Bernstein, that finds GCD of each moduli with a product of all other moduli. Through introduction of product and remainder trees, the computational cost becomes logarithmic instead of quadratic, which results in dramatic drop of the execution time.
```rust extern crate bulk_gcd; extern crate rug;
use rug::Integer;
let moduli = [ Integer::from(15), Integer::from(35), Integer::from(23), ];
let result = bulk_gcd::compute(&moduli).unwrap();
assert_eq!(result, vec![ Some(Integer::from(5)), Some(Integer::from(5)), None, ]); ```
bulk-gcd is available on crates.io. To use bulk-gcd in your crate,
add it as a dependency inside Cargo.toml:
[dependencies]
bulk-gcd = "^1.0.0"
You also need to declare it by adding this to your crate root (usually
lib.rs or main.rs):
rust
extern crate bulk_gcd;
Huge thanks to Michael Grunder for helping me make threads work in Rust.