Arytmetyka modularna – wyjaśnienie

Każdy już stosuje arytmetykę modularną: 10 godzin po 8 jest 6, a dzień po niedzieli to poniedziałek. Liczenie, które po n krokach zaczyna znowu od 0, okazuje się mieć własną, pełną arytmetykę, z regułami, niespodziankami i centralnym miejscem w teorii liczb oraz w kryptografii, która chroni internet.

Zegar z dwunastoma pozycjami ponumerowanymi od 0 do 11 i spiralna ścieżka, która raz okrąża tarczę od 9 do 2
Zegar z dwunastoma pozycjami ponumerowanymi od 0 do 11 i spiralna ścieżka, która raz okrąża tarczę od 9 do 2

Reszty i przystawanie

Podziel a przez n i zachowaj tylko resztę: to jest a mod n, liczba od 0 do n − 1. 26 mod 7 = 5, bo 26 = 3 × 7 + 5. Liczby o tej samej reszcie zachowują się tak samo mod n, dlatego nazywamy je przystającymi: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss wprowadził ten zapis w swoich Disquisitiones Arithmeticae z 1801 roku i dzięki niemu dawne obserwacje Fermata i Eulera stały się odrębną arytmetyką. Na zegarze z n pozycjami każda liczba całkowita trafia na swoją resztę; pełne obroty idą w zapomnienie.

Carl Friedrich Gauss na portracie Christiana Albrechta Jensena z 1840 roku. Notację kongruencji a ≡ b (mod n) wprowadził w Disquisitiones Arithmeticae z 1801.
Carl Friedrich Gauss na portracie Christiana Albrechta Jensena z 1840 roku. Notację kongruencji a ≡ b (mod n) wprowadził w Disquisitiones Arithmeticae z 1801.

Dodawanie, odejmowanie i mnożenie

Trzy zwykłe działania wykonuje się jak zawsze, a redukować mod n można w dowolnej chwili: reszta z sumy jest resztą z sumy reszt, i tak samo jest z różnicami i iloczynami. Aby znaleźć ostatnią cyfrę 37 × 48, pomnóż tylko ostatnie cyfry: 7 × 8 = 56, więc wynik kończy się na 6. Właśnie dlatego arytmetyka modularna jest tak przydatna dla komputerów: bez względu na to, jak duże są liczby, wartości pośrednie nigdy nie przekraczają n².

Dzielenie wymaga odwrotności

Dzielenie jest wyjątkiem. 2 × 3 ≡ 2 × 8 (mod 10), bo oba iloczyny dają 6 mod 10, a jednak 3 i 8 są różne, więc nie można po prostu skrócić 2. Dzielenie przez a oznacza mnożenie przez jego odwrotność, czyli liczbę x, dla której a × x ≡ 1, a ta istnieje dokładnie wtedy, gdy a i n nie mają wspólnego czynnika. Znajduje ją rozszerzony algorytm Euklidesa: wykonuje kroki dzielenia z algorytmu Euklidesa dla największego wspólnego dzielnika i na każdym kroku śledzi mnożnik, tak że gdy reszta dojdzie do 1, mnożnik jest odwrotnością. Gdy n jest liczbą pierwszą, każda liczba oprócz 0 ma odwrotność i dzielenie zawsze działa.

Potęgi, Fermat i Euler

Potęgi się powtarzają. Weź potęgi 3 mod 7: 3, 2, 6, 4, 5, 1, a potem znowu 3. Długość tego cyklu to rząd liczby 3. W 1640 roku Pierre de Fermat zauważył, że dla liczby pierwszej p zachodzi a^(p − 1) ≡ 1 (mod p), o ile p nie dzieli a, więc każdy rząd dzieli p − 1. Leonhard Euler to udowodnił i uogólnił na dowolne n, zastępując p − 1 liczbą wartości względnie pierwszych z n. Ogromne potęgi oblicza się przez wielokrotne podnoszenie do kwadratu: a, a², a⁴, a⁸ …, każda jest kwadratem poprzedniej zredukowanym mod n, a potem mnoży się je zgodnie z cyframi dwójkowymi wykładnika.

Portret Pierre’a de Fermata
Portret Pierre’a de Fermata
Portret Leonharda Eulera
Portret Leonharda Eulera

Cyfry kontrolne i kalendarze

Arytmetyka modularna wyłapuje pomyłki. Ostatnią cyfrę numeru ISBN-10 dobiera się tak, by ważona suma wszystkich dziesięciu cyfr była wielokrotnością 11, dzięki czemu wykrywana jest każda pojedyncza błędna cyfra i każda zamiana dwóch sąsiednich. Numery kart płatniczych korzystają z algorytmu Luhna mod 10, a numery IBAN z kontroli mod 97. Kalendarze działają mod 7: dzień tygodnia dowolnej daty można wyznaczyć za pomocą kilku reszt i tak właśnie działają kalendarze wieczne oraz metoda doomsday.

Kryptografia

Współczesna kryptografia opiera się na potęgach modularnych, które łatwo obliczyć, a trudno odwrócić. W protokole wymiany kluczy Diffiego–Hellmana z 1976 roku dwie osoby uzgadniają wspólny sekret przez otwarte łącze, wymieniając potęgi modulo dużej liczby pierwszej. RSA, opublikowany w 1977 roku przez Rivesta, Shamira i Adlemana, szyfruje wiadomość m jako m^e mod n, gdzie n jest iloczynem dwóch dużych liczb pierwszych, i odszyfrowuje drugim wykładnikiem d, który może obliczyć tylko ktoś, kto zna te dwie liczby pierwsze. W podręcznikowym przykładzie n = 3233 = 61 × 53, e = 17 i d = 413: 65 zmienia się w 2790, a 2790 z powrotem w 65.

Wypróbuj sam

Otwórz zegar modularny, aby obliczać a mod n, sumy, różnice, iloczyny, potęgi, odwrotności i ilorazy mod n dla liczb do 30 cyfr. Każdy wynik ma swoje kroki: dzielenie z resztą, potęgi z wielokrotnego podnoszenia do kwadratu albo tabelę rozszerzonego algorytmu Euklidesa. Zegar rysuje, jak dochodzi się do wyniku, od spirali dodawania po cykl potęg, a dla małych n tabela działania pokazuje wszystkie wyniki naraz.

Często zadawane pytania

Co oznacza symbol ≡?

a ≡ b (mod n) mówi, że a i b dają tę samą resztę z dzielenia przez n, czyli równoważnie, że n dzieli a − b. 38 ≡ 2 (mod 12), bo 38 − 2 = 36 jest wielokrotnością 12.

Czy mod to to samo co operator % w programowaniu?

Dla liczb dodatnich tak. Dla liczb ujemnych wiele języków, takich jak C, Java i JavaScript, zwraca ujemną resztę: −7 % 3 daje tam −1, podczas gdy −7 mod 3 = 2. Operator % w Pythonie stosuje konwencję matematyczną dla dodatniego n.

Czym jest rząd liczby mod n?

To najmniejsze k > 0, dla którego a^k ≡ 1 (mod n). Istnieje tylko wtedy, gdy a i n nie mają wspólnego czynnika. Rząd 2 mod 7 wynosi 3, bo 2³ = 8 ≡ 1, a rząd 3 mod 7 wynosi 6, więc potęgi 3 przechodzą przez każdą niezerową resztę: 3 jest pierwiastkiem pierwotnym mod 7.

Kto wymyślił arytmetykę modularną?

Reszt używano znacznie wcześniej, na przykład w chińskim twierdzeniu o resztach z III–V wieku, a posługiwali się nimi także Fermat i Euler. Gauss uczynił z niej systematyczną arytmetykę, z zapisem kongruencji, w 1801 roku.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz zegar modularny