0Pricing
Cryptology Academy · Lekcja

NWD, funkcja Eulera i wprowadzenie do teorii liczb

Stosuj NWD i funkcję Eulera w rzeczywistych problemach kryptograficznych.

NWD, funkcja Eulera i wprowadzenie do teorii liczb to bezpłatna lekcja Cryptology Academy na CoddyKit. To lekcja 4 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

NWD i funkcja Eulera są niezbędnymi narzędziami w RSA oraz wielu innych systemach klucza publicznego. Opanujmy je na przykładach.

Największy wspólny dzielnik (NWD)

NWD(a, b) to największa liczba całkowita, która dzieli zarówno a, jak i b bez reszty. NWD(12, 8) = 4. Jeśli NWD(a, m) = 1, mówimy, że a i m są względnie pierwsze.

Algorytm Euklidesa

NWD(a, b) = NWD(b, a mod b), a przypadek bazowy to NWD(a, 0) = a. NWD(48, 18): = NWD(18, 12) = NWD(12, 6) = NWD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Rozszerzony algorytm Euklidesa

Wersja rozszerzona znajduje liczby całkowite x i y takie, że ax + by = NWD(a,b). Gdy NWD(a,m)=1, x jest odwrotnością modularną a modulo m. W ten sposób RSA oblicza klucze prywatne.

Funkcja Eulera φ(n)

φ(n) zlicza liczby całkowite od 1 do n, które są względnie pierwsze z n. φ(10) = 4, ponieważ {1, 3, 7, 9} są względnie pierwsze z 10. Dla każdej liczby pierwszej p zachodzi φ(p) = p-1.

Funkcja Eulera dla iloczynu

Dla RSA: n = p×q (p i q są pierwsze). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Przykład: p=5, q=11: φ(55) = 4×10 = 40. Dlatego faktoryzacja n łamie RSA — ujawnia φ(n).

Twierdzenie Eulera

Jeśli NWD(a,n)=1: a^φ(n) ≡ 1 (mod n). Jest to matematyczna podstawa deszyfrowania RSA: M = C^d mod n, ponieważ e×d ≡ 1 (mod φ(n)).

Obliczanie d w RSA

Należy wybrać e = 65537 (typowy publiczny wykładnik RSA). Następnie obliczyć d = e^(-1) mod φ(n) za pomocą rozszerzonego algorytmu Euklidesa. Należy sprawdzić, czy e×d mod φ(n) == 1.

Funkcja Eulera w Pythonie

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Funkcja lambda Carmichaela

Współczesne RSA używa funkcji lambda Carmichaela λ(n) = lcm(p-1, q-1) zamiast φ(n). Daje ona mniejszy, równoważny moduł. PKCS#1 v2 i NIST zalecają λ(n).

Podsumowanie zastosowań praktycznych

NWD: weryfikacja względnej pierwszości e i φ(n). Rozszerzony algorytm Euklidesa: obliczanie klucza prywatnego d. Funkcja Eulera: określanie grupy wykładników dla potęgowania modularnego. Wszystkie trzy elementy są używane podczas każdego generowania kluczy RSA.

Szybki test

Dla RSA z p=7 i q=11 jaka jest wartość φ(n)?

Podsumowanie

Doskonale! NWD, algorytm Euklidesa i funkcja Eulera są już w Państwa zestawie narzędzi. Następnie zajmiemy się operacją XOR i operacjami bitowymi — podstawowymi elementami szyfrów symetrycznych.

Często zadawane pytania

Czy lekcja „NWD, funkcja Eulera i wprowadzenie do teorii liczb” jest bezpłatna?

Tak — pełny tekst „NWD, funkcja Eulera i wprowadzenie do teorii liczb” 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 „NWD, funkcja Eulera i wprowadzenie do teorii liczb”?

Stosuj NWD i funkcję Eulera w rzeczywistych problemach kryptograficznych. Ć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 4 z 4.

Ile czasu zajmuje lekcja „NWD, funkcja Eulera i wprowadzenie do teorii liczb”?

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