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).

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] https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf