Crypto-IT

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.

Definicja Oznaczmy jako Z_N zbiór wszystkich nieujemnych liczb całkowitych, mniejszych niż N:
Z_N = {0,1,2,...,N-1}

gdzie:

N jest dodatnią liczbą całkowitą,
jeżeli N jest liczbą pierwszą, to będzie oznaczana jako p (cały zbiór będzie oznaczony jako Z_p).

Aby wyznaczyć wartość dowolnej liczby całkowitej dla modułu N należy podzielić tę liczbę przez N i za jej wartość w Z_N 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.

Definicja Liczbą odwrotną do liczby x w Z_N jest taki element y należący do Z_N, który spełnia równanie:
x · y = 1 (w Z_N)

gdzie:

y jest oznaczane jako x^-1

Przykładowo, jeśli N jest dowolną nieparzystą liczbą, to odwrotność 2 in Z_N is (N+1)/2:
x · (N+1)/2 = N + 1 = 1 (in Z_N)

Twierdzenie Dowolna liczba x posiada liczbę odwrotną w Z_N wtedy i tylko wtedy gdy liczby x oraz N są względnie pierwsze.

Twierdzenie to można udowodnić korzystając z tego, że największy wspólny dzielnik dwóch liczb całkowitych może być zawsze przedstawiony jako suma dwóch iloczynów każdej z tych dwóch liczb z inną odpowiednio dobraną liczbą całkowitą:
a·x + b·y = gcd(x,y)

Wyznaczenie liczb odwrotnych w Z_N umożliwia rozwiązywanie równań liniowych w arytmetyce modularnej:
równanie: a · x + b = 0 (w Z_N)
ma rozwiązanie: x = -b · a^-1 (w Z_N)

Definicja Symbol Z^*_N oznacza zbiór wszystkich elementów Z_N, dla których można wyznaczyć liczby odwrotne; czyli zbiór takich liczb x należących do Z_N, że x oraz N są względnie pierwsze.

przykładowo dla liczby pierwszej p:
Z^*_p = Z_p \ {0} = {1, 2, …, p - 1}

Wyznaczanie liczb odwrotnych w Z_N

Liczby odwrotne w Z_N można wyznaczyć w czasie O(log₂N) za pomocą algorytmu Euklidesa, 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 Z_a)
Czyli b jest liczbą odwrotną do y w Z_a.

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:
a_i = a_i-2 - q_i-1·a_i-1
b_i = b_i-2 - q_i-1·b_i-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
    a₀ = 0
    b_-1 = 0
    b₀ = 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ą).

Data: 2020-03-09