Arytmetyka modularna (arytmetyka reszt)

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).