Arytmetyka modularna

Z Wikipedii

Dodawanie modulo 12

Arytmetyka modularna – w matematyce system liczb całkowitych, w którym liczby „zawijają się” po osiągnięciu pewnej wartości określonej terminem modulo (skracane mod).

Przykładem może być zegar 24-godzinny: dzielimy dzień na 24 godziny numerowane od 0 do 23. Jeżeli obecnie jest 19:00, to 8 godzin później nie będzie 27:00 (ten wynik otrzymalibyśmy dodając 19+8=27), lecz 3:00. Podobnie, jeżeli obecnie jest 12:00 i minie 21 godzin, to zegar wskaże 9:00, a nie 33:00. Jeżeli obecnie jest 3:00, to 4 godziny wcześniej była 23:00, nie zaś -1:00.

Tak więc mierzenie czasu na zegarze rozpoczyna się o godzinie 0:00 „zerując się” po osiągnięciu 24. Mówimy, że na zegarze obowiązuje arytmetyka modulo 24. W ten sam sposób możemy rozpatrywać obliczenia na dniach tygodnia (wykonywane modulo 7) lub na miesiącach (modulo 12). Prawa działań na liczbach takie jak liczba nieparzysta + liczba parzysta = liczba nieparzysta można łatwo wyprowadzać używając arytmetyki modulo 2.

[edytuj] Prosty model

Aby „dodać” dwie godziny na zegarze, dodajemy odpowiadające im liczby. Jeżeli wynik jest większy od 23, odejmujemy od niego 24. Aby utworzyć model arytmetyki modulo $n$ , w zbiorze $\{0,1,\dots,n-1\}$ wprowadzamy działanie dodawania, które oznaczymy symbolem $\oplus$ , aby odróżnić je od zwykłego dodawania oznaczanego $+$ . Sumą $a \oplus b$ jest

liczba $a + b$ , gdy $a + b < n$ ;
liczba $a + b - n$ , gdy $a+b\geqslant n$ .

Tak określone dodawanie pokrywa się z intuicyjnym rozumieniem zegara 24-godzinnego dla $n = 24$ . Na przykład:

$7 \oplus 8 = 15$
$22 \oplus 5 = 27-24 = 3$

Ten model dobrze obrazuje działania na 24-godzinnym zegarze, jednakże ma ograniczenia, np. nie jest w nim możliwe mnożenie liczb. Aby rozszerzyć tę strukturę, potrzebne są pojęcia przystawania i klas reszt.

[edytuj] Przystawanie

Zobacz więcej w osobnym artykule: kongruencja.

Mówimy, że liczba $a$ przystaje do $b$ modulo $n$ , jeżeli różnica $a - b$ jest wielokrotnością liczby $n$ . Zapisujemy to

$a \equiv b \pmod n$

Na przykład,

$33 \equiv 9 \pmod {24}$ ,

ponieważ $33 - 9 = 24$ jest podzielne przez $24$ ;

$15 \equiv 1 \pmod {7}$ ,

ponieważ $15 - 1 = 14$ jest podzielne przez $7$ ;

$-1 \equiv 23 \pmod {24}$

ponieważ $- 1 - 23 = - 24$ jest podzielne przez $24$ .

Równoważnie przystawanie można zdefiniować następująco: liczba $a$ przystaje do $b$ modulo $n$ , gdy $a$ i $b$ dają taką samą resztę z dzielenia przez $n$ .

Relację przystawania nazywa się także kongruencją.

[edytuj] Klasy reszt

Relacja przystawania modulo $n$ jest tzw. relacją równoważności. Oznacza to, że dzieli ona zbiór liczb całkowitych na $n$ podzbiorów, klas równoważności, nazywanych klasami reszt. Na przykład dla $n = 4$ tymi zbiorami są:

$\{\dots, -4, 0, 4, 8, 12, \dots\}$ ,

$\{\dots, -3, 1, 5, 9, 13, \dots\}$ ,

$\{\dots, -2, 2, 6, 10, 14, \dots\}$ ,

$\{\dots, -1, 3, 7, 11, 15, \dots\}$ .

Każda liczba całkowita należy do dokładnie jednej klasy reszt.

Dwie klasy reszt $A$ i $B$ możemy dodać w następujący sposób. Wybierzmy z każdej z nich po jednym elemencie (reprezentancie klasy): $x \in A, y \in B$ . Wynikiem jest klasa reszt, do której należy $x + y$ . Okazuje się, że wynik takiego dodawania nie zależy od wyboru $x$ i $y$ . Przykładowo, chcąc dodać

$\{\dots, -2, 2, 6, 10, 14, \dots\}$

$\{\dots, -1, 3, 7, 11, 15, \dots\}$

wybierzmy po jednym elemencie z każdej z nich, np. $2$ i $7$ . Wynikiem jest klasa zawierająca $2 + 7 = 9$ :

$\{\dots, -3, 1, 5, 9, 13, \dots\}$

Jeżeli wybralibyśmy przy dodawaniu $10$ i $3$ , to wynik byłby taki sam: ta sama klasa reszt zawiera liczbę $13$ . W taki sam sposób można zdefiniować mnożenie, które również jest jednoznaczne.

Zauważmy, że tak określone działania mają regularne własności:

dodawanie i mnożenie jest przemienne i łączne;
dodawanie ma element neutralny $\{\dots, -2n, -n, 0, n, 2n, \dots\}$ ;
mnożenie ma element neutralny $\{\dots, -n+1, 1, n+1, 2n+1, \dots\}$ ;
mnożenie jest rozdzielne względem dodawania.

Mówimy, że zbiór klas reszt tworzy pierścień zwany pierścieniem klas reszt modulo $n$ . Pierścień ten oznaczany jest przez $\mathbb Z_n$ .

[edytuj] Definicja formalna

Niech $n$ będzie nieujemną liczbą całkowitą. Niech $\equiv_n$ będzie relacją przystawania modulo $n$ . Oznaczmy przez $[a]$ klasę abstrakcji odpowiadającą liczbie $a$ . W zbiorze $\mathbb Z/\equiv_n$ określamy działania dodawania i mnożenia:

[a] + [b] = [a + b]

$[a]\cdot[b]=[a \cdot b]$

Tak utworzona struktura jest pierścieniem, zwanym pierścieniem klas reszt modulo $n$ . Oznaczana jest jako $(\mathbb Z_n, +, \cdot)$ .

Równoważnie pierścień klas reszt modulo $n$ można zdefiniować jako pierścień ilorazowy pierścienia liczb całkowitych przez ideał $n\mathbb Z$ będący zbiorem wielokrotności liczby $n$ . Stąd też alternatywne oznaczenie tego pierścienia, czyli $\mathbb Z/n\mathbb Z$ lub $\mathbb Z/(n)$ .

W przypadku $n = 0$ , $\mathbb Z/0\mathbb{Z}$ jest izomorficzny z pierścieniem $\mathbb Z$ . Ten zdegenerowany przypadek omówiony został w artykule dotyczącym liczb całkowitych.

[edytuj] Własności

Elementem neutralnym dodawania w $\mathbb{Z}_n$ jest $[0]$ , elementem przeciwnym do $[k]$ jest $[ - k] = [n - k]$ , elementem neutralnym mnożenia jest $[1]$ .

Element $[k]$ pierścienia $\mathbb{Z}_n$ jest odwracalny wtedy i tylko wtedy, gdy liczba całkowita $k$ jest względnie pierwsza z $n$ . W przeciwnym wypadku jest on dzielnikiem zera.

Dowód:

Jeżeli $n$ i $k$ są względnie pierwsze, to istnieją liczby $a,b \in \mathbb{Z}$ , że $a n + b k = 1$ . Wówczas $bk \equiv 1 \pmod n$ , zatem $[b][k] = 1$ i element $[k]$ ma odwrotność $[b]$ .
Jeżeli $n$ i $k$ mają wspólny dzielnik $a > 1$ , tj. $n = a b$ , $k = a c$ , to $[k][b] = [a c][b] = [a b c] = 0$ , czyli $[k]$ jest dzielnikiem zera.

Zatem jeżeli $n$ jest liczbą pierwszą, to w pierścieniu $\mathbb Z_n$ jedynym dzielnikiem zera jest $[0]$ . W przeciwnym wypadku istnieją nietrywialne dzielniki zera. Tak więc pierścień $\mathbb Z_n$ jest ciałem wtedy i tylko wtedy, gdy $n$ jest liczbą pierwszą.

Zwykle podając elementy pierścienia $\mathbb Z_n$ opuszcza się nawiasy i wybiera najmniejszego dodatniego reprezentanta (tj. liczbę ze zbioru $\{0,1,\dots,n-1\}$ , którą można znaleźć biorąc resztę z dzielenia dowolnego reprezentanta przez $n$ ). Co więcej, liczby ze zbioru $\{0,1,\dots,n-1\}$ można utożsamiać z elementami pierścienia $\mathbb Z_n$ .

Charakterystyką pierścienia $\mathbb Z_n$ jest $n$ .

[edytuj] Grupa addytywna

Grupa addytywna pierścienia $(\mathbb{Z}_n, +, \cdot)$ , tj. $(\mathbb Z_n, +)$ jest grupą cykliczną zwaną addytywną grupą klas reszt modulo $n$ . W teorii grup oznacza się ją symbolami $\mathbb Z_n$ lub $\mathbb Z/n\mathbb Z$ .

Generatorem tej grupy jest dowolna liczba względnie pierwsza z $n$ . Co więcej, z dokładnością do izomorfizmu, jedynymi grupami cyklicznymi są $(\mathbb Z_n, +, \cdot)$ i grupa addytywna liczb całkowitych.

Każdą grupę abelową o skończonej liczbie generatorów można zapisać jako sumę prostą grup $\mathbb Z/n\mathbb Z$ . Przykłady:

grupa czwórkowa Kleina $V_4 \simeq \mathbb Z_2 \oplus \mathbb Z_2$
$\mathbb Z_{16}^* \simeq \mathbb Z_2 \oplus \mathbb Z_4$
grupa pierwiastków z jedynki $\mathbb C_n \simeq \mathbb Z_n$ .

Prawdziwa jest też równość dotycząca rzędu elementu:

$\operatorname{o}(g) = \tfrac{n}{\operatorname{NWD}(g, n)}$ .

[edytuj] Grupa multiplikatywna

Zobacz więcej w osobnym artykule: Grupa multiplikatywna.

Elementami odwracalnymi pierścienia $\mathbb Z_n$ są te liczby ze zbioru $\{0,1,\dots,n-1\}$ , które są względnie pierwsze z $n$ :

$\mathbb{Z}_n^{*}=\{[a]\colon\operatorname{NWD}(a,n)=1\}$ .

Ich liczbę wyznacza funkcja φ Eulera. W szczególności, $\phi(n)=n-1 \iff n \in \mathbb{P} \iff \mathbb{Z}_n$ jest ciałem.

Te elementy tworzą grupę, zwaną multiplikatywną grupą klas reszt modulo $n$ . Oznaczana jest $\mathbb Z_n^*$ , $U(\mathbb Z_n)$ lub $(\mathbb Z/n\mathbb Z)^*$ .

Grupa ta nie zawsze jest cykliczna, jest nią natomiast dla $n$ będących naturalnymi potęgami liczb pierwszych.

Ogólniej, jeżeli $\lambda(n) = \varphi(n)$ , gdzie $λ$ jest funkcją Carmichaёla, to $\mathbb Z_n^*$ jest grupą cykliczną. Implikacja ta nie działa w drugą stronę, czego przykładem może być grupa $\mathbb Z_{10}^*$ , która jest cykliczna.

[edytuj] Rozkład na sumę prostą

Rozłóżmy liczbę $n$ na czynniki pierwsze: $n = p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k}$ , gdzie $p i$ są parami różnymi liczbami pierwszymi, $a i$ - liczbami naturalnymi. Zgodnie z chińskim twierdzeniem o resztach, pierścień $\mathbb Z_n$ można przedstawić w postaci sumy prostej:

$\mathbb Z_n \simeq \mathbb Z_{p_1^{a_1}} \oplus Z_{p_2^{a_2}} \oplus \dots \oplus \mathbb Z_{p_k^{a_k}} = \bigoplus_{i=1}^k \mathbb Z_{p_i^{a_i}}$ .

To twierdzenie ma zastosowanie w informatyce, gdyż obliczenia w kilku systemach $\mathbb Z_{p_i^{a_i}}$ mogą być wykonywane równolegle.

[edytuj] Pierwiastki kwadratowe z jedności

Pierwiastkiem kwadratowym z jedności modulo $n$ nazywamy element $k \in \mathbb Z_n$ taki, że

k 2 = 1

W dowolnym pierścieniu $\mathbb Z_n$ pierwiastkami z jedności są $1$ i $- 1$ . Można udowodnić, że liczba wszystkich pierwiastków kwadratowych mod $n$ wynosi

$2^{f(n)+[8|n]-[2|n]+[4|n]}\,$ ^[1]

gdzie:

$[x | y]$ jest równe 1, gdy $x$ jest dzielnikiem $y$ , 0, jeżeli nie jest;
$f (n)$ jest liczbą pierwszych dzielników $n$ .

Aby sprawdzić, czy równanie $a 2 = x$ ma rozwiązanie, można skorzystać z własności symbolu Jacobiego.

[edytuj] Przykład

W pierścieniu $\mathbb Z_{60}$ jest $2 3 + 0 - 1 + 1 = 2 3 = 8$ pierwiastków z jedynki:

$1 \mapsto 1^2 = 1$ ,
$11 \mapsto 11^2 = 121 \mod 60 = 1$ ,
$19 \mapsto 19^2 = 361 \mod 60 = 1$ ,
$29 \mapsto 29^2 = 841 \mod 60 = 1$ ,
$31 \mapsto 31^2 = (-29)^2 = 1$ ,
$41 \mapsto 41^2 = (-19)^2 = 1$ ,
$49 \mapsto 49^2 = (-11)^2 = 1$ ,
$59 \mapsto 59^2 = (-1)^2 = 1$ .

[edytuj] Pokrewne struktury

Do struktur podobnie zbudowanych można zaliczyć:

grupę addytywną liczb wymiernych modulo $d \in \mathbb Q$ oznaczaną $\mathbb Q/(d)$ ;
grupę addytywną liczb rzeczywistych modulo $d \in \mathbb R$ oznaczaną $\mathbb R/(d)$ .

Grupa $\mathbb Q/(d)$ jest izomorficzna z grupą $\mathbb Q/(1)$ ; grupa $\mathbb R/(d)$ z grupą $\mathbb R/(1)$ .

[edytuj] Użycie nieformalne

Wyraz modulo w żargonie jest używany jako "z dokładnością do", na przykład: "Protokoły http i https są takie same modulo szyfrowanie" (tj. jedyną różnicą między http i https jest szyfrowanie).

[edytuj] Zastosowania

Arytmetyka modularna jest używana w teorii liczb, teorii grup, kryptografii, informatyce, przy tworzeniu sum kontrolnych, a nawet przy tworzeniu wzorów^[2]

Zasada działania szyfru RSA oraz algorytm Rabina-Millera opierają się na własnościach grupy $\mathbb Z_n^*$ .

[edytuj] Zobacz też

Przypisy

↑ Graham, Knuth, Patashnik, str. 154
↑ http://britton.disted.camosun.bc.ca/modart/jbmodart.htm

[edytuj] Bibliografia

Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006. ISBN 83-01-14764-4.

We provide Linux to the World