Teoria liczb i arytmetyka modularna: zadania z rozwiązaniami krok po kroku

1Reszty i kongruencje

Dzielenie a przez n daje iloraz q i resztę r: a = q·n + r, gdzie 0 ≤ r < n. Resztę zapisujemy jako a mod n. Dla liczby ujemnej q też jest ujemne: −3 = −1·7 + 4, więc −3 mod 7 = 4.

Dwie liczby są przystające modulo n, a ≡ b (mod n), gdy dają tę samą resztę, czyli gdy n dzieli a − b.

Reszty można redukować w każdym kroku, co utrzymuje małe liczby:

Na przykład 47·58 mod 9: 47 ≡ 2 i 58 ≡ 4, więc 47·58 ≡ 8 (mod 9).

2Algorytm Euklidesa

Największy wspólny dzielnik NWD(a, b) to największa liczba dzieląca obie. Algorytm Euklidesa używa NWD(a, b) = NWD(b, a mod b):

1. Podziel: a = q·b + r.
2. Zastąp (a, b) przez (b, r).
3. Powtarzaj, aż reszta wyniesie 0. Ostatnia niezerowa reszta jest NWD.

Najmniejsza wspólna wielokrotność wynika stąd: NWW(a, b) = a·b / NWD(a, b).

3Elementy odwrotne i rozszerzony algorytm

Element odwrotny do a modulo n to liczba x, dla której a·x ≡ 1 (mod n). Istnieje dokładnie wtedy, gdy NWD(a, n) = 1.

Rozszerzony algorytm Euklidesa wykonuje Euklidesa na (n, a) i przy każdej reszcie zapamiętuje współczynnik t, tak aby każda reszta r ≡ t·a (mod n). Zacznij od t = 0 dla n i t = 1 dla a; każde nowe t to t sprzed dwóch wierszy minus q razy t sprzed jednego wiersza. Gdy pojawi się reszta 1, jej t jest elementem odwrotnym.

Mając element odwrotny, kongruencję a·x ≡ b (mod n) rozwiązujemy jako x ≡ a⁻¹·b. Gdy d = NWD(a, n) jest większe niż 1, jest d rozwiązań, jeśli d dzieli b, a w przeciwnym razie żadnego.

Dwie kongruencje o względnie pierwszych modułach, x ≡ r₁ (mod m₁) i x ≡ r₂ (mod m₂), mają dokładnie jedno rozwiązanie modulo m₁·m₂ (chińskie twierdzenie o resztach). Zapisz x = r₁ + m₁k i rozwiąż względem k.

4Potęgi modularne i RSA

Wielokrotne podnoszenie do kwadratu szybko oblicza aᵏ mod n: zapisz k binarnie, znajdź a, a², a⁴, a⁸, … mod n przez podnoszenie do kwadratu i redukcję, a następnie pomnóż potęgi, których bit jest równy 1.

Małe twierdzenie Fermata: dla liczby pierwszej p, która nie dzieli a, aᵖ⁻¹ ≡ 1 (mod p). Zatem wykładnik można redukować modulo p − 1.

RSA buduje klucz z dwóch liczb pierwszych p i q:

1. n = p·q oraz φ(n) = (p − 1)(q − 1).
2. Wybierz e z NWD(e, φ(n)) = 1; (n, e) jest kluczem publicznym.
3. Oblicz d = e⁻¹ mod φ(n): to klucz prywatny.
4. Szyfrowanie c = mᵉ mod n; odszyfrowanie m = cᵈ mod n.

Funkcja φ(n) Eulera zlicza liczby od 1 do n względnie pierwsze z n: φ(p) = p − 1 dla liczby pierwszej, φ(pᵏ) = pᵏ − pᵏ⁻¹, a φ jest multiplikatywna dla czynników względnie pierwszych.

5Typowe błędy

• Podanie ujemnej reszty dla liczby ujemnej: −17 mod 5 to 3, nie −2.
• Zatrzymanie Euklidesa na pierwszej reszcie zamiast na ostatniej niezerowej.
• Zapomnienie o dodaniu n do ujemnego współczynnika z rozszerzonego algorytmu.
• Obliczanie wykładnika RSA d modulo n zamiast modulo φ(n).
• Redukowanie wykładnika modulo p zamiast p − 1 w twierdzeniu Fermata.

6Jak wyglądają zadania egzaminacyjne

• Łatwe: NWD i reszty. Wykonujesz algorytm Euklidesa dla NWD lub NWW, znajdujesz reszty liczb ujemnych i redukujesz sumy oraz iloczyny modulo n.
• Średnie: elementy odwrotne i kongruencje. Znajdujesz odwrotności modularne rozszerzonym algorytmem, rozwiązujesz kongruencje liniowe, łączysz dwie kongruencje chińskim twierdzeniem o resztach i obliczasz φ(n) Eulera.
• Trudne: potęgi modularne i RSA. Używasz wielokrotnego podnoszenia do kwadratu i twierdzenia Fermata, rozwiązujesz kongruencje z wieloma rozwiązaniami oraz znajdujesz prywatne wykładniki RSA, szyfrogramy i odszyfrowane wiadomości.