gcd

20.11.2009
Trudność

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

1
2
3
4
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:

$$(x' + i*(N/d)) * A/d * d = x'*A/d*d + i*N/d*A/d*d = 
(B/d+j*N/d)*d+ i*N/d*A/d*d =$$
$$B+j*N+ i*N*A/d =
= B \pmod N
$$

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com