gcd

20.11.2009

Omówiliśmy sobie Algorytm Euklidesa i parę jego zastosowań. Polecam gorąco artykuł Damiana Rusaka.

Kto się nie spóźnił, załapał się na wersję nie używającą dzielenia, znacznie prostszą w analizie złożoności czasowej:

int gcd(int a,int b){
  if(!(a|b))
    return a+b;
  else if(a&1)
    if(b&1)
      return a<b?gcd(a,b-a):gcd(b,a-b);
    else
      return gcd(a,b>>1);
  else if(b&1)
    return gcd(a>>1,b);
  else
    return 2*gcd(a>>1,b>>1);
}

Analiza opierała się o powiązanie danych wejściowych z pewną funkcją potencjału.

Przypomnieliśmy sobie też wersję z modulo i prosiłem, aby każdy w domu pomyślał nad podobnym dowodem dla tejże wersji. Przypominam, że powinno wyjść $O(\lg (a+b))$ . Pokazaliśmy sobie też przypadek wymagający $\Theta(\lg (a+b))$ .

Zaczęliśmy jednak od zagadki: jaka jest ostatnia cyfra ilorazu liczb naturalnych, kończących się odpowiednio na 6 i 2. Pokazaliśmy jak rozwiązać tę zagadkę gdy dzielimy przez liczbę względnie pierwszą z 10 i zobaczyliśmy, że przydaje się do tego Okrojony Rozszerzony Algorytm Euklidesa.

int inverse(int a,int b,int x=1,int y=0){
  if(!b)return x;
  return inverse(b,a%b,y,x-y*a/b);
}

Należy uważać, bo powyższy kod zwraca czasem ujemne wartości.

Obiecałem wyjaśnić, skąd wiemy, że dla 6 i 2, poprawnymi wynikami są akurat 3 i 8. Szerzej interesuje nas następujący problem. Dla zadanych A,B i N chcemy znaleźć wszystkie takie x, że

$x*A = B \pmod N$

Widzieliśmy, że jeśli A jest względnie pierwsze z N, to istnieje co najwyżej jedno takie x. Aby je znaleźć, najpierw znajdujemy inverse(A,N), czyli $A^{-1}$ , a następnie mnożymy obustronnie nasze równanie i otrzymujemy:

$x = x*A*A^{-1} = B*A^{-1} \pmod N$

Schody zaczynają się, gdy A nie jest zględnie pierwsze z N, czyli $gcd(A,N)=d \land d>1$ .

Sytuacja wygląda wtedy tak:

$x*(A/d)*d = B \pmod ((N/d)*d)$

Pierwsza obserwacja jest taka, że jeśli B nie dzieli się przez d, to nie ma szans, żebyśmy znaleźli jakieś x, spełniające tę równość. Pozostaje więc przypadek taki, w którym B również dzieli się przez d:

$x*(A/d)*d = (B/d)*d \pmod ((N/d)*d)$

Aż korci, żeby powiedzieć "no to podzielmy stronami przez d", ale niestety, akurat przez d nie umiemy dzielić, bo elementy odwrotne istnieją tylko dla liczb względnie pierwszych z N. Kto nie wierzy niech popatrzy na taki przykład:

$x*2 = 3*2 \pmod 5*2$

czy faktycznie x musi być równe 3? Czy nie może być 6?

Sytuacja nie jest jednak beznadziejna, gdyż to co możemy zrobić, to podzielić przez d również N. Otrzymamy wtedy:

$x*(A/d) = B/d \pmod (N/d)$

Żeby się przekonać, że to jest prawdą wyobraźmy sobie oś liczbową, na której ktoś zmienił podziałkę na d razy rzadszą. Udało nam się zatem zredukować problem do takiego, w którym możemy już skorzystać z inverse(A/d,N/d), bo te dwie liczby nie mają już wspólnych dzielników.

Rozwiązując to nowe równanie poznamy resztę z dzielenia x przez (N/d). To nie jest to czego szukaliśmy, bo chcieliśmy poznać resztę z dzielenia przez N. Istnieje aż d różnych reszt z dzielenia przez N, które spełniają ten warunek. Okazuje się, że każda z nich jest dobra. Wracając do naszego przykładu. Rozwiążemy :

$x = 3 \pmod 5$

Istnieją dokaldnie dwie cyfry, które tak mają : 3 i 8. Ogólnie przepis jest taki, że jeśli znajdziemy już poprawną resztę modulo (N/d) to wystarczy do niej dodać i*(N/d), dla $i=0,\ldots,d-1,$ aby uzyskać wszystkie poprawne reszty modulo N. Ale dlaczego tak jest, że każda z nich jest dobra?

Jest tak, bo są one postaci $x' + i*(N/d)$ , gdzie $x'*A/d = B/d \pmod N/d$ , co po podstawieniu do oryginalnego równania daje: