Arytmetyka modularna.html

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 kongruencji lub 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.