9
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Jun 27 '14 at 23:22
  • $\begingroup$ Have you tried anything with prime factorizations? $\endgroup$ – Ryan Jul 28 '14 at 12:51
  • $\begingroup$ 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?) $\endgroup$ – usul Jul 29 '14 at 10:29
  • $\begingroup$ @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. $\endgroup$ – gnasher729 Apr 16 '18 at 21:40
-2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you explain your algorithm in words? This is not a programming site. $\endgroup$ – Yuval Filmus Jul 18 '17 at 15:08
  • $\begingroup$ @YuvalFilmus I have added the explanation. Hope this helps. $\endgroup$ – Subhendu Ranjan Mishra Jul 19 '17 at 17:58
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 19 '17 at 18:01
  • $\begingroup$ @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. $\endgroup$ – Subhendu Ranjan Mishra Jul 19 '17 at 18:24
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Jul 19 '17 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.