Skutecznie znajdując maksymalny GCD parami zestawu liczb naturalnych

Rozważ następujący problem:

Niech będzie skończonym podzbiorem liczb naturalnych. $S = \{ s_1, s_2, ... s_n \}$

Niech | gdzie jest największy wspólny dzielnik z i $G = \{$ $gcd(s_i, s_j)$ $s_i, s_j \in S,$ $s_i \neq s_j \}$ $gcd(x,y)$ $x$ $y$

Znajdź element maksymalny w . $G$

Problem ten można rozwiązać, biorąc największy wspólny dzielnik z każdej pary za pomocą algorytmu Euclid i śledząc największy.

Czy istnieje bardziej skuteczny sposób na rozwiązanie tego problemu?

algorithms number-theory

— Tommy
źródło

Warto przyjrzeć się sekcji 3.3 Mining Your Ps and Qs: Detection of Powespread Weak Keys in Network Network (Heninger i in., Usenix Security 2012). Opisują algorytm obliczania parą gcd w gcd, w określonym ustawieniu, przy użyciu drzew produktów i drzew reszt. Nie wiem jednak, czy dotyczy to twojego problemu.

O (n \lg n)

$O(n \lg n)$

— DW

Czy próbowałeś już czegoś z pierwszymi faktoryzacjami?

— Ryan

Załóżmy, że wszystkie liczby są względnie pierwsze, ale trudne do uwzględnienia (np. Każdy jest równy dla dużych różnych liczb pierwszych ). Trudno zatem uniknąć sprawdzenia wszystkich par GCD. (Powiedzmy, że powiem ci, że po sprawdzeniu wszystkich par, ale że wszystkie pary GCD to Jak możesz zgadnąć bez obliczania go?)

s_{i}

$s_i$

p_{i} q_{i}

$p_iq_i$

p_{i}, q_{i}

$p_i,q_i$

(s_{n - 1}, s_{n})

$(s_{n-1},s_n)$

1

$1$

g c d (s_{n - 1}, s_{n})

$gcd(s_{n-1},s_n)$

— usul

Link @usul DW jest właśnie tym problemem. Ogromna liczba, powiedzmy miliard, kluczy szyfrowania powinna być produktami dwóch różnych liczb pierwszych. Podejrzewamy jednak, że niektóre klucze szyfrowania mają wspólny czynnik główny (który byłby gcd obu kluczy, dzięki czemu oba byłyby łatwe do uwzględnienia). Algorytm ten pozwala znaleźć klucze ze wspólnym współczynnikiem bez obliczania n (n-1) / 2 gcd dla n = 1 miliarda.

— gnasher729

-2

Oto wydajny algorytm (w języku Python ). Poniżej znajdziesz wyjaśnienie.

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

Objaśnienie powyższego fragmentu kodu:

W tym problemie obserwujemy:

Wynik nie może być większy niż max(S)
Wynikiem jest liczba, która ma dwie lub więcej wielokrotności na tej liście S
W rzeczywistości wynikiem są maxwszystkie takie liczby z wyżej wymienioną właściwością.

Dzięki tym obserwacjom program wykonuje następujące czynności:

Zrób setz listy. Ponieważ zestawy można efektywnie przeszukiwaćO(log(n))
Znajdź maksimum listy i zapisz ją w zmiennej m.
Zaczynając od mkasy 1, znajdź pierwszą liczbę, która ma dwa lub więcej wielokrotności w zestawie. Pierwszy taki znaleziony numer jest wynikiem.

Mam nadzieję, że to jasne. Daj mi znać, jeśli potrzebujesz bardziej szczegółowych wyjaśnień.

— Subhendu Ranjan Mishra
źródło

Czy potrafisz wyjaśnić swój algorytm słowami? To nie jest strona programistyczna.

— Yuval Filmus,

@YuvalFilmus Dodałem wyjaśnienie. Mam nadzieję że to pomoże.

— Subhendu Ranjan Mishra

Co jeśli wszystkie elementy są unikalne? Nie oznacza to, że maksymalny GCD wynosi 1. Rozważmy na przykład zestaw , gdzie maksymalny GCD wynosi 2.

{2, 4}

$\{2,4\}$

— Yuval Filmus

@YuvalFilmus za każdy irozpoczynający się maż 1sprawdzamy, czy dwie lub więcej wielokrotności z iznajdują się w zestawie. W tym przykładzie dwie wielokrotności liczby 2 znajdują się w zestawie „2 i 4”. więc odpowiedź brzmi 2. Wewnętrzna whilepętla sprawdza wszystkie wielokrotności itill m' as m` jest masx listy.

— Subhendu Ranjan Mishra

To okropny algorytm. Dla tablicy dwóch liczb o długości bitów każda, obliczenie GCD zajmuje czas wielomianowy, podczas gdy twój algorytm zajmuje czas wykładniczy w najgorszym przypadku (gdy liczby są względnie pierwsze).

x, y

$x,y$

n

$n$

— Yuval Filmus,