[netdog]

So what the researchers did, apparently, was to gather all the RSA public keys they could find (6 million or so) and then calculate the gcds of all pairs of keys.

Apparently not. The number of unique pairings among 6 million is 5,999,999 factorial. Which is a _really_ large number.

[wging]

Not so. Given a set of N elements from which you choose k (with order not mattering, since you only care whether a given two are the same) the number of pairs is N!/(k!(N-k)!). So it's (6000000!)/(2!(6000000-2)!).

We can take advantage of the cancellation properties of the factorial to write this as N\(N-1)\...\(N-k+1)/k! . If k=2 this resolves to N(N-1)/2.

You could also derive it like this: for ordered* pairs, you have N choices for the first and N-1 for the second (since you don't pair anything with itself but all other choices are permitted). This counts each pair exactly twice: each pair and its reverse are the same if you don't care about order. So N(N-1)/2.

Still trillions of combinations. Not 5999999! though.

[neolefty]

Isn't it 6 million squared? 36 x 10^12. Factorial would be the number of ordered sets that include all the elements.

[wging]

At the risk of redundancy (I wrote my post while you posted): you're double counting (since gcd(a,b) = gcd(b,a), you needn't compute both; either tells you whether a,b have a common factor. (a,b) and (b,a) having a common factor both account for the same problem) and you're including pairs of the same element (gcd(a,a)=a always, but this is meaningless for the data set we're considering--we don't care that a number has common factors with itself, only with other numbers)