ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

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 ZN zbiór wszystkich nieujemnych liczb całkowitych, mniejszych niż N:
    ZN = {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 Zp).

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.

Definicja Liczbą odwrotną do liczby xZN jest taki element y należący do ZN, który spełnia równanie:
    x · y = 1 (w ZN)
gdzie:
  • y jest oznaczane jako x-1

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

Twierdzenie Dowolna liczba x posiada liczbę odwrotną w ZN 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 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)

Definicja Symbol Z*N oznacza zbiór wszystkich elementów ZN, dla których można wyznaczyć liczby odwrotne; czyli zbiór takich liczb x należących do ZN, że x oraz N są względnie pierwsze.
  • przykładowo dla liczby pierwszej p:
        Z*p  =  Zp \ {0} = {1, 2, …, p - 1}

Wyznaczanie liczb odwrotnych w ZN

Liczby odwrotne w ZN można wyznaczyć w czasie O(log2N) 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 Za)
Czyli b jest liczbą odwrotną do yZa.

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