# Efficiently finding the maximum pairwise GCD of a set of natural numbers

Consider the following problem:

Let $S = \{ s_1, s_2, ... s_n \}$ be a finite subset of the natural numbers.

Let $G = \{$ $gcd(s_i, s_j)$ | $s_i, s_j \in S,$ $s_i \neq s_j \}$ where $gcd(x,y)$ is the greatest common divisor of $x$ and $y$

Find the maximum element of $G$.

This problem can be solved by taking the greatest common divisor of each pair using Euclid's algorithm and keeping track of the largest one.

Is there a more efficient way of solving this?

• You might want to take a look at Section 3.3 of Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices (Heninger et al, Usenix Security 2012). They describe an algorithm for computing pairwise gcd's in $O(n \lg n)$ gcd's, in a certain setting, using product trees and remainder trees. I don't know if it extends to your problem, though. – D.W. Jun 27 '14 at 23:22
• Have you tried anything with prime factorizations? – Ryan Jul 28 '14 at 12:51
• Suppose all the numbers are relatively prime but hard to factor (e.g. each $s_i$ is equal to $p_iq_i$ for large distinct primes $p_i,q_i$). Then it seems difficult to avoid checking all pairwise GCDs. (Say I tell you that after checking all pairs but $(s_{n-1},s_n)$ that all the pairwise GCDs are $1$. How could you guess $gcd(s_{n-1},s_n)$ without computing it?) – usul Jul 29 '14 at 10:29
• @usul D.W's link is exactly that problem. A huge number, say one billion, encryption keys should all be products of two distinct primes. But we suspect that some encryption keys have a prime factor in common (which would be the gcd of both keys, making both easy to factor). That algorithm lets you find the keys with common factor without calculating n(n-1)/2 gcd's for n = 1 billion. – gnasher729 Apr 16 '18 at 21:40

Here is an efficient algorithm (in Python). Please find the explanation below.

def max_gcd_pair(S):
# Assumption 1: S is the list of numbers
# Assumption 2: There are no duplicates in S

s = set(S)
m = max(S)

res = 0
i = m

while(i > 0):
a = i
cnt = 0
while (a<=m): # a maxed at max of the list
if a in s:
cnt += 1
a += i

if cnt >= 2:  # we have found the result
res = i
break

i = i -1

return res


### Explanation of the above code snippet :

We observe the following in this problem:

1. The result can not be more than max(S)
2. The result is a number, that has two or more multiples in this list S
3. In-fact the result is max of all such numbers with the property mentioned above.

With these observations, the program does the following:

1. Make a set of the list. As sets can be searched efficiently in O(log(n))
2. Find the max of the list and store it in the variable m.
3. Starting from m till 1, find the first number that has two or more multiples in the set. The first such number found is the result.

I hope this is clear. Please let me know if you need a more detailed explanation.

• Can you explain your algorithm in words? This is not a programming site. – Yuval Filmus Jul 18 '17 at 15:08
• @YuvalFilmus I have added the explanation. Hope this helps. – Subhendu Ranjan Mishra Jul 19 '17 at 17:58
• What if all elements are unique? This doesn't mean that the maximal GCD is 1. Consider for example the set $\{2,4\}$, where the maximal GCD is 2. – Yuval Filmus Jul 19 '17 at 18:01
• @YuvalFilmus for every i starting with m till 1 we check if two or more multiples of i are in the set. In this exmaple two multiples of 2 are in the set '2 and 4 . so the answer is 2. The inner while loop checks all the multples of i till m' as m is the masx of the list. – Subhendu Ranjan Mishra Jul 19 '17 at 18:24
• Well, this is a terrible algorithm. For an array of two numbers $x,y$ of length $n$ bits each, computing the GCD takes polynomial time, whereas your algorithm takes exponential time in the worst case (when the numbers are relatively prime). – Yuval Filmus Jul 19 '17 at 18:26