README
¶
BatchGCD
Go Library (and program) to perform pairwise gcd on large number of RSA moduli
This implements three different ways to perform pairwise GCD on a large number of RSA moduli.
-
Actual pairwise GCD
This performs n*(n-1)/2 GCD operations on the moduli. This is slow. Don't use this.
-
Accumulating Product
This iterates over all input moduli, performing a GCD of each one against the product of all previous. Once it finds a candidate, it scans all previous moduli to find out which ones it shared a factor with (either GCD or division, depending on whether one or both were found). The main scan cannot be done in parallel, and even though it seems like this is O(n), the increasing size of the accumulated product results it lots of long multiplication and long divison so it's still painfully slow for large numbers of moduli.
-
Smooth Parts
DJB's "How to find smooth parts of integers" http://cr.yp.to/papers.html#smoothparts This creates a product tree, then converts it to a remainder tree, then kablam you find common factors. This is largely the same as the one at https://factorable.net/resources.html This is the default, use this unless you're trying to burn in a new CPU or something.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BasicPairwiseGCD ¶
func LowMemSmoothPartsGCD ¶
Implementation of D.J. Bernstein's "How to find smooth parts of integers" http://cr.yp.to/papers.html#smoothparts
func MulAccumGCD ¶
This performs the GCD of the product of all previous moduli with the current one. This uses around double the memory (minus quite a lot of overhead), and identifies problematic input in O(n) time, but has to do another O(n) scan for each collision to figure get the private key back. If there are no collisions, this algorithm isn't parallel at all. If we get a GCD that is the same as the modulus, we do a manual scan for either colliding Q or identical moduli If we get a GCD lower than the modulus, we have one private key, then do a manual scan for others.
func SmoothPartsGCD ¶
Implementation of D.J. Bernstein's "How to find smooth parts of integers" http://cr.yp.to/papers.html#smoothparts
Source Files
Directories