PricingLoginStart free
Cryptology Academy · Lekcja

Liczby pierwsze i rozkład na czynniki

Dowiedz się, dlaczego liczby pierwsze są podstawą kryptografii klucza publicznego.

Lekcja 3 z 413 kroki

Liczby pierwsze i rozkład na czynniki to bezpłatna lekcja Cryptology Academy na CoddyKit. To lekcja 3 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

Liczby pierwsze są podzielne tylko przez 1 i przez siebie. Są atomami mnożenia — a zarazem fundamentem RSA, Diffie-Hellman i wielu innych systemów kryptograficznych.

Definicja i przykłady

Liczby pierwsze: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Liczba jest pierwsza, jeśli jej jedynymi dodatnimi dzielnikami są 1 i ona sama. Zgodnie z konwencją 1 NIE jest liczbą pierwszą.

Podstawowe twierdzenie arytmetyki

Każdą liczbę całkowitą > 1 można rozłożyć na liczby pierwsze dokładnie na jeden sposób (pomijając kolejność). 60 = 2² × 3 × 5. To właśnie jednoznaczność rozkładu umożliwia działanie kryptografii opartej na faktoryzacji.

Dzielenie próbne

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Wystarczy sprawdzać dzielniki do √n — jeśli poniżej √n nie znaleziono żadnego dzielnika, n jest liczbą pierwszą.

Sito Eratostenesa

Aby znaleźć wszystkie liczby pierwsze do N, należy rozpocząć od listy liczb od 2 do N. Następnie trzeba wykreślić wielokrotności 2, potem 3, 5 itd. Pozostałe liczby są pierwsze. Algorytm działa w czasie O(N log log N).

Testowanie pierwszości: Miller-Rabin

W przypadku dużych liczb (2048 bitów) dzielenie próbne jest zbyt wolne. Miller-Rabin to test probabilistyczny: po wykonaniu go 40 razy prawdopodobieństwo błędu jest mniejsze niż 4^(-40).

Faktoryzacja liczb całkowitych

Mając n = p × q, znalezienie p i q jest problemem faktoryzacji liczb całkowitych. Jeśli n ma 2048 bitów, najlepsze znane algorytmy wymagają 2^112 operacji — obecnie jest to niewykonalne.

Dlaczego RSA używa dwóch dużych liczb pierwszych

Moduł RSA n = p × q. Znajomość n bez znajomości p i q utrudnia obliczenie klucza prywatnego. Bezpieczeństwo opiera się w całości na trudności faktoryzacji n.

Generowanie dużych liczb pierwszych

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Należy wygenerować losową nieparzystą liczbę, sprawdzić ją testem Millera-Rabina i powtarzać te kroki, aż otrzyma się liczbę pierwszą.

Bezpieczne i silne liczby pierwsze

Bezpieczna liczba pierwsza p = 2q+1, gdzie q również jest liczbą pierwszą. Bezpieczne liczby pierwsze są odporne na niektóre ataki na DH. W RSA czasami stosuje się silne liczby pierwsze, aby zapobiec atakowi Pollarda p-1.

Luki między liczbami pierwszymi i ich nieskończoność

Euklides udowodnił w 300 roku p.n.e., że istnieje nieskończenie wiele liczb pierwszych. Hipoteza liczb bliźniaczych (liczby pierwsze p i p+2 występują nieskończenie wiele razy) nadal nie została udowodniona. W kryptografii nigdy nie zabraknie liczb pierwszych.

Szybki test

Dlaczego RSA używa dużych liczb pierwszych?
Odpowiedz w interaktywnej lekcji

Podsumowanie

Rozumieją już Państwo liczby pierwsze i faktoryzację. Następnie zastosujemy funkcję Eulera oraz NWD — ostatnie narzędzia matematyczne potrzebne przed przejściem do 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 „Liczby pierwsze i rozkład na czynniki” jest bezpłatna?

Tak — pełny tekst „Liczby pierwsze i rozkład na czynniki” 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 „Liczby pierwsze i rozkład na czynniki”?

Dowiedz się, dlaczego liczby pierwsze są podstawą kryptografii klucza publicznego. Ć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 3 z 4.

Ile czasu zajmuje lekcja „Liczby pierwsze i rozkład na czynniki”?

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