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ść
.
Pokazaliśmy sobie też przypadek wymagający
.
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
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 następnie mnożymy obustronnie nasze równanie i otrzymujemy:
Schody zaczynają się, gdy A nie jest zględnie pierwsze z N, czyli

.
Sytuacja wygląda wtedy tak:
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:
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:
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:
Ż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 :
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

aby uzyskać wszystkie poprawne reszty modulo N.
Ale dlaczego tak jest, że każda z nich jest dobra?
Jest tak, bo są one postaci
, gdzie
, co po podstawieniu do oryginalnego równania daje: