"Even though Euclid’s GCD algorithm is highly efficient, running it on all possible pairings of keys would be a strain. There’s an ingenious shortcut, based on the observation that if Y is relatively prime to each of X1,X2,…,Xn, then it also has no factor in common with the product X1×X2×⋯×Xn. Thus it’s possible to detect the presence of shared factors with just n GCD operations, instead of n2."
Well, suppose we have 4 moduli, N1, N2, N3, N4. The naïve way to find all pairwise GCDs is to compute GCD(N1, N2), GCD(N1, N3), GCD(N1, N4), ...., GCD(N3, N4). That's (n^2 - n)/2 GCD computations.
The shortcut is to compute P = N1 * N2 * N3 * N4, GCD(N1, P / N1), GCD(N2, P / N2), GCD(N3, P / N3), GCD(N4, P / N4) --- n GCD computations . This works if all you want to know is whether there exist shared primes among those moduli. Suppose N1 = p1 * p2, and N2 = p2 * p3. N2 * N3 * N4 has the factorization p2 * p3 * p4 * p5 * p6 * p7 --- whatever the other primes are, that product still has the p2 factor in common with N1.
Note that unlike that naïve approach, this does not tell you which exact modulus has the prime in common with (say) N1. One idea is to take p2 and divide every candidate modulus by it until you find a match. This is computationally suboptimal; the better approach is to use product and remainder trees, as nicely explained in the Heninger et al paper [1, §3.3].
1. Multiply all of the keys together: Y= X1 * X2 * ... * Xn.
2. For each key, Xi, use Euclid's algorithm to find the gcd of Xi and (Y/Xi). If the gcd of Xi is greater than 1, then you've factored Xi.
Even taking into account the arbitrary-size int arithmetic, this is more efficient then performing Euclid's algorithm on each pair (Xi, Xj) because gcds are so much more expensive then multiplications. N multiplications and n gcds on enormous ints is faster than n^2 - n gcds with 1024 bit ints.
Someone please correct me if I'm wrong, but I guess the shortcut is something like this:
Z = X[1] * X[2] * X[3] * ... * X[n];
for i in (1..n-1) {
Z = Z/X[i];
g = GCD(X[i], Z);
if (g > 1) {
// check each other key to see which have g as a factor
for j in (j+1..n) {
if (X[j] % g == 0) {
log that keys i & j have g as a common factor;
}
}
}
Rather than having to run the inner loop for every iteration of the outer loop, it only has to run in the case where there is a common factor.
For instance, to check for common factors in [4, 13, 10] we initially compute Z = 4 * 13 * 10 = 520. Then we start with the first key, 4. Divide Z by 4 yielding 130. Do 4 and 130 have a common factor? gcd(4,130) = 2, so yes they do. We now check each remaining key individually (13 & 10) for divisibility by 2 and report which one(s) match, (in this case, 10). Then we continue with the second key, 13. Divide Z by 13 yielding 10. Do 13 & 10 have a common factor? No, they don't, and there are no more keys left to check, so we're done.
Yes that's correct, however you need not actually "log that keys i & j have g as a common factor;"
if g > 1 then just add x[i] to a list, after checking all in x, then just go through that much smaller list. ( even better would be to just group x[I] in a dictionary based on g)...
good example though.
Rather than doing n^2 comparisons (ie. every key individually GCD compared against every other key individually = (n keys)x(n-1 other keys) combinations), you can instead do n total GCD comparisons - every key GCD factored a single time against <large product of every other key> (which works out to (n keys)x(1 big product) GCD comparisons)
"Even though Euclid’s GCD algorithm is highly efficient, running it on all possible pairings of keys would be a strain. There’s an ingenious shortcut, based on the observation that if Y is relatively prime to each of X1,X2,…,Xn, then it also has no factor in common with the product X1×X2×⋯×Xn. Thus it’s possible to detect the presence of shared factors with just n GCD operations, instead of n2."
Can someone explain that shortcut in more detail?