Arytmetyka modularna to system liczb całkowitych, w którym wartości liczb zerują się i zaczynają zwiększać od początku po osiągnięciu pewnej przyjętej wartości, nazywanej modułem (modulo). Arytmetyka modularna jest powszechnie wykorzystywana w systemach informatycznych i kryptografii.
Aby wyznaczyć wartość dowolnej liczby całkowitej dla modułu N należy podzielić tę liczbę przez N i za jej wartość w ZN przyjąć resztę z tego dzielenia. W arytmetyce modularnej można zdefiniować wszystkie takie typowe działania, co w zwykłej arytmetyce. Charakteryzują się one analogicznymi właściwościami (m.in. prawami przemienności, łączności).
Liczby odwrotne w arytmetyce modularnej
Liczby całkowite rozpatrywane w arytmetyce modularnej mogą (ale nie muszą) posiadać liczby odwrotne.
Przykładowo, jeśli N jest dowolną nieparzystą liczbą, to odwrotność 2 w ZN wynosi (N+1)/2:
x · (N+1)/2 = N + 1 = 1 (w ZN)
Wyznaczenie liczb odwrotnych w ZN umożliwia rozwiązywanie równań liniowych w arytmetyce modularnej:
równanie: a · x + b = 0 (w ZN)
ma rozwiązanie: x = -b · a-1 (w ZN)
Wyznaczanie liczb odwrotnych w ZN
Liczby odwrotne w ZN można wyznaczyć w czasie O(log2N) za pomocą , który służy do wyliczenia największego wspólnego dzielnika dwóch liczb całkowitych.
Rozszerzona wersja algorytmu Euklidesa znajduje dodatkowo całkowite współczynniki a oraz b spełniające tożsamość Bezouta:
a·x + b·y = gcd(x,y)
W celu otrzymania liczby odwrotnej należy przeprowadzić następujące przekształcenia:
a·x + b·y = 1
b·y = 1 (w Za)
Czyli b jest liczbą odwrotną do y w Za.
Współczynniki a oraz b należy wyliczać w każdym kroku algorytmu Euklidesa, za pomocą otrzymywanych ilorazów oraz wartości współczynników z dwóch poprzednich kroków:
ai = ai-2 - qi-1·ai-1
bi = bi-2 - qi-1·bi-1
Jeżeli kroki algorytmu numerowane są od 1, to należy przyjąć następujące wartości początkowe współczynników:
a-1 = 1
a0 = 0
b-1 = 0
b0 = 1
Końcowe wartości współczynników a oraz b otrzymywane są w kroku, z którego pobierana jest również wartość największego wspólnego dzielnika liczb x oraz y (czyli w kroku z ostatnią niezerową resztą).
Aby znaleźć największy wspólny dzielnik liczb a oraz b (gdzie a > b) za pomocą algorytmu Euklidesa należy podzielić a przez b, a otrzymany wynik zapisać w formie ilorazu i reszty z dzielenia:
a / b = q1 + r1
Następnie trzeba wykonać kolejne dzielenie, w którym b pełni rolę a oraz r1 pełni rolę b:
b / r1 = q2 + r2
Kroki należy powtarzać analogicznie:
r1 / r2 = q3 + r3
… …
aż do otrzymania zerowej reszty z dzielenia.
Ostatnia niezerowa reszta jest największym wspólnym dzielnikiem liczb a oraz b.
Można wykazać, że algorytm Euklidesa działa w czasie proporcjonalnym do wielkości większej liczby: O(log2a).