PricingLoginStart free
Cryptology Academy · Lekcja

Podstawy arytmetyki modularnej

Poznaj arytmetykę zegarową i dowiedz się, dlaczego ma kluczowe znaczenie dla kryptografii.

Lekcja 2 z 413 kroki

Podstawy arytmetyki modularnej to bezpłatna lekcja Cryptology Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Cryptology Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Cryptology Academy zawiera 4 lekcji w sumie.

Wprowadzenie

Arytmetyka modularna — nazywana czasem „arytmetyką zegarową” — jest matematyczną podstawą AES, RSA, Diffie-Hellman i niemal każdego współczesnego szyfru.

Czym jest modulo?

a mod m to reszta z dzielenia a przez m. 17 mod 5 = 2 (ponieważ 17 = 3×5 + 2). W Pythonie: 17 % 5 == 2.

Intuicja arytmetyki zegarowej

Na zegarze dwunastogodzinnym 10 + 5 = 3 (a nie 15). Jest to arytmetyka mod 12. Arytmetyka modularna „zawija się” po osiągnięciu modułu — dokładnie tego potrzebujemy w matematyce szyfrów.

Modularne dodawanie i odejmowanie

(a + b) mod m = ((a mod m) + (b mod m)) mod m Przykład: (19 + 23) mod 7 = (5 + 2) mod 7 = 7 mod 7 = 0

Modularne mnożenie

(a × b) mod m = ((a mod m) × (b mod m)) mod m Przykład: (13 × 17) mod 11 = (2 × 6) mod 11 = 12 mod 11 = 1

Modularne potęgowanie

RSA używa a^b mod m. W przypadku dużych wykładników stosujemy metodę kolejnych kwadratów i mnożenia: 2^10 mod 13: 2^2=4, 4^2=16≡3, 3^2=9, 9×2^2=9×4=36≡10. Python: pow(2, 10, 13) → 10

Odwrotność modularna

a^(-1) mod m to taka wartość x, że a×x ≡ 1 (mod m). Przykład: 3^(-1) mod 7 = 5, ponieważ 3×5=15≡1 (mod 7). Stosuje się ją w RSA i podczas deszyfrowania szyfru afinicznego.

Rozszerzony algorytm Euklidesa

Rozszerzony algorytm Euklidesa efektywnie oblicza odwrotności modularne. Python: pow(3, -1, 7) == 5 (Python 3.8+ obsługuje ujemne wykładniki w funkcji pow).

Małe twierdzenie Fermata

Jeśli p jest liczbą pierwszą: a^p ≡ a (mod p), więc a^(p-1) ≡ 1 (mod p). Oznacza to, że a^(-1) ≡ a^(p-2) (mod p). Twierdzenie jest używane podczas generowania kluczy RSA i testów pierwszości.

Chińskie twierdzenie o resztach (CRT)

CRT umożliwia rozwiązywanie układów równań modularnych. Deszyfrowanie RSA używa CRT do przyspieszenia obliczeń: wyniki są obliczane osobno modulo p i q, a następnie łączone.

Arytmetyka modularna w AES

AES działa w GF(2^8) — ciele Galois, w którym dodawanie jest operacją XOR, a mnożenie wykorzystuje arytmetykę wielomianów modulo nierozkładalnego wielomianu. Wszystkie działania arytmetyczne AES są modularne.

Szybki test

Jaki wynik zwraca w Pythonie wyrażenie pow(2, 10, 7)?
Odpowiedz w interaktywnej lekcji

Podsumowanie

Opanowali już Państwo arytmetykę modularną! Następnie zajmiemy się liczbami pierwszymi — tym, dlaczego są wyjątkowe i dlaczego ich faktoryzacja leży u podstaw bezpieczeństwa RSA.
Bezpłatny start

Ucz się Cryptology Academy dzięki korepetycjom AI — za darmo

Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.

Kursy
67
Lekcje
261
Zacznij naukę bezpłatnieWyświetl pełny kurs

Często zadawane pytania

Czy lekcja „Podstawy arytmetyki modularnej” jest bezpłatna?

Tak — pełny tekst „Podstawy arytmetyki modularnej” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Cryptology Academy, przejdź na CoddyKit PRO. Kurs Cryptology Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Podstawy arytmetyki modularnej”?

Poznaj arytmetykę zegarową i dowiedz się, dlaczego ma kluczowe znaczenie dla kryptografii. Ćwiczysz Cryptology Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Cryptology Academy?

Nie wymagamy żadnego doświadczenia. Cryptology Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Podstawy arytmetyki modularnej”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Cryptology Academy?

Tak. Każda lekcja Cryptology Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Podstawy systemu binarnego i szesnastkowego
  2. Podstawy arytmetyki modularnej
  3. Liczby pierwsze i rozkład na czynniki
  4. NWD, funkcja Eulera i wprowadzenie do teorii liczb
← Powrót do Cryptology Academy