9*. Wiedza z plusem: Liczby pierwsze - zastosowania, ciekawostki - Zbiory liczbowe

R1K7VOP5UFQDX

9*. Wiedza z plusem: Liczby pierwsze - zastosowania, ciekawostki

Liczby pierwsze to liczby naturalne, które posiadają dwa dzielniki: liczbę $1$ i samą siebie. W zbiorze liczb pierwszych nie ma liczby $1$ , gdyż jej własność multiplikacji nie zmienia wartości liczby (każda liczba pomnożona przez $1$ w iloczynie jest równa samej sobie, stąd można wielokrotnie pomnożyć przez $1$ nie uzyskując żadnych zmian w wartości wyniku). Zatem liczby pierwsze to liczby: $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , … Czy jest ich skończona ilość?
Należałoby przypuszczać że nie, skoro liczb naturalnych jest nieskończenie wiele. Jak zatem można odnajdywać liczby pierwsze w zbiorze liczb naturalnych? Częstość ich występowania wydaje się być całkowicie przypadkowa.

Twoje cele

Rozpoznasz (wskażesz) liczby pierwsze, bliźniacze, doskonałe, zaprzyjaźnione.
Wykorzystasz informacje o poznanych rodzajach liczb do rozwiązywania zadań.
Przeanalizujesz przeprowadzony dowód w zakresie istnienia nieskończenie wielu liczb pierwszych.
Przetestujesz hipotezy w zakresie poznanych własności liczb.
Zastosujesz arytmetykę modularną.
Zastosujesz algorytm RSA do zakodowania i odkodowania wiadomości.

Na pytania o własności liczb pierwszychliczby pierwszeliczb pierwszych próbowało odpowiedzieć wielu naukowców, a dziś komputery stosujące odpowiednie algorytmy wciąż poszukują coraz to większych liczb pierwszych. Aktualnie największą znaną liczbą pierwszą jest $2^{82 589 933} - 1$ . Liczba ta ma $24862048$ cyfr. Jej odkrycia dokonano 7 XII 2018 roku na komputerze jednego z uczestników projektu GIMPS - Patricka Laroche'a z Ocali w stanie Floryda.

R1FHUEPX3MAOL1

Rysunek przedstawia zdjęcie Stanisława Ulama. Matematyk ubrany jest w płaszcz, szalik, kapelusz. Pod prawą ręką trzyma teczkę na dokument oraz rękawiczki. Ma uśmiechniętą, pogodną twarz. Stoi na tle bloku i drzewa, typowy widok podwórka. — Stanisław Ulam
Źródło: Los Alamos National laboratory, http://commons.wikimedia.org, domena publiczna.

Spirala Ulama lub spirala liczb pierwszych, to graficzna metoda ukazująca prawidłowości w rozkładzie liczb pierwszych, zaproponowana przez polskiego matematyka Stanisława Ulama w 1963 roku. Spirala powstaje z zapisu kolejnych liczb naturalnych począwszy od $1$ , a potem spiralnie w kwadracie wpisywanych kolejnych liczb naturalnych. Stanisław Ulam oznaczając na niej jedynie liczby pierwszeliczby pierwszeliczby pierwsze zauważył, że występują one na liniach diagonalnych, czyli skośnych.

RKQ51OL3352EN1

Rysunek przedstawia spiralę Ulama zbudowaną na podstawie kwadratu o 11 polach. Spirala rozpoczyna się cyfrą 1 osadzoną w środkowym polu kwadratu, a kończy cyfrą 121 znajdującą się w prawym dolnym rogu kwadratu. Liczby pierwsze zaznaczone zostały na kolor niebieski. — Spiralę Ulama wykorzystują dziś programiści podejmując kolejne próby programowania algorytmów, które służyć mają wyszukiwaniu liczb pierwszych.
Źródło: Gromar Sp. z o.o., licencja: CC BY-SA 3.0.

Najbardziej znanym algorytmem, i jednym z najstarszych wykorzystywanych w poszukiwaniu liczb pierwszych, jest Sito Erastotenesa. Autorstwo tego algorytmu przypisuje się Eratostenesowi z Cyreny. Algorytm ten pozwala na wyznaczenie wszystkich liczb pierwszych, mniejszych od ustalonej liczby. Istotą algorytmu jest wykreślanie z listy kolejnych liczb naturalnych, tych liczb, które mają więcej niż dwa dzielniki. Dla przykładu rozpatrzymy kolejne liczby naturalne od $0$ do $102$ .

Wiemy że zero i jeden nie są liczbami pierwszymi oraz, że najmniejsza liczba pierwsza to 2. Zatem ze spirali skreślimy najpierw wszystkie liczby będące wielokrotnością 2 (oznaczone kolorem zielonym). Kolejną liczbą pierwsza jest 3, zatem wykreślamy te wielokrotności liczby 3, które jeszcze nie zostały wykreślone. Następnie wykreślamy wielokrotności liczb 5 i 7. W wyniku tej operacji wykreślania w tabeli pozostają tylko liczby pierwsze (na białym tle).

R1GFOFJV24E711

Rysunek przedstawia spiralnie ułożone liczby - w środku znajduje się 0 i jeden, znajdują się one na szarych polach. Przeciwnie do wskazówek zegara liczby rozchodzą się do wartości 102. Liczby pierwsze znajdują się na białych polach. Wielokrotności liczby 2 zostały zaznaczone na kolor zielony. Wielokrotności liczby 3 zaznaczono na kolor niebieski. Wielokrotności liczby 5 mają kolor pomarańczowy, a wielokrotności liczby 7 mają kolor żółty. — Źródło: Gromar Sp. z o.o., licencja: CC BY-SA 3.0.

Funkcjonalność sita Erastotenesa maleje wraz ze wzrostem liczb pierwszych. Poszukiwanie coraz większych liczb pierwszych wymaga wykonania coraz większej liczby operacji, które również dla dzisiejszych komputerów stanowią wyzwanie. Stąd też wnioskując o pewnej równomierności rozkładu liczb pierwszych w zbiorze liczb naturalnych, wciąż jest trudno przewidzieć wartość kolejnej liczby pierwszej.

R533DX8K2EOF61

Liczby Mersenne’a, to liczby, które mają postać dwa do potęgi pe minus jeden, gdzie pe jest liczbą pierwszą, a ich nazwa pochodzi od Marina Mersenne’a (1588‑1648), francuskiego mnicha franciszkanina i matematyka, który przypuszczał, że wśród liczb postaci dwa do potęgi pe minus 1 znajdują się prawie wszystkie liczby pierwsze (tzn. wszystkie poza ewentualną pewną skończoną ich liczbą). Mersenne twierdził też, że liczby dwa do potęgi pe minus jeden są pierwsze dla pe równa się 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 i dla żadnych innych liczb naturalnych pe mniejsze od 258. Co wynikało z konieczności przeprowadzenia bardzo żmudnych i nie wolnych od błędów arytmetycznych obliczeń. Dziś już wiemy, że popełnił pięć błędów. Liczby pierwsze otrzymamy także dla pe równa się 61, 89 i 107, a dla pe równa się 67 i 257 otrzymamy liczby złożone. Liczby bliźniacze Liczby pierwsze, różniące się o 2, zwane są bliźniaczymi. Liczby bliźniacze stanowią pary: 3 i 5, 5 i 7, 11 i 13, 17 i 19, 29 i 31, 41 i 43… Największą znaną dziś parą liczb bliźniaczych są liczby: dwa sześć zero cztery dziewięć siedem pięć cztery pięć mnożone przez dwa sześć sześć dwa pięć dodać jeden i dwa sześć zero cztery dziewięć siedem pięć cztery pięć mnożone przez dwa sześć sześć dwa pięć minus jeden. Liczby doskonałe Liczbę naturalną nazywamy doskonałą, gdy jest sumą wszystkich swoich dzielników właściwych (dzielnik właściwy liczby to każdy dzielnik mniejszy od samej liczby). Liczbami doskonałymi są: 6, 28, 498, ponieważ: dzielniki właściwe 6 to 1, 2, 3, zaś ich suma: 1 dodać 2 dodać 3 równa się 6. Dzielniki właściwe 28 to 1, 2, 4, 7, 14, suma: 1 dodać 2 dodać 4 dodać 7 dodać 14 równa się 28, dzielniki właściwe 496 to 1, 2, 4, 8, 16, 31, 62, 124, 248, suma: 1 dodać 2 dodać 4 dodać 8 dodać 16 dodać 31 dodać 62 dodać 124 dodać 248 równa się 496. Nie dziwi fakt, że dotychczas znaleziono tylko 39 liczb doskonałych, wszak obiekty doskonałe i piękne zawsze są rzadkie. Euklides zauważył, że liczby postaci 2 do potęgo pe minus jeden otwórz nawias dwa do potęgi pe minus jeden zamknij nawias są doskonałe, o ile dwa do potęgi pe minus 1 jest liczbą pierwszą. Liczby zaprzyjaźnione Pary liczb naturalnych o tej własności, że suma dzielników właściwych każdej z nich równa jest drugiej liczbie, to liczby zaprzyjaźnione. Zaprzyjaźniony duet to: 220 i 284, ponieważ suma dzielników właściwych 220 otwórz nawias 1 dodać 2 dodać 5 dodać 10 dodać 11 dodać 20 dodać 22 dodać 44 dodać 55 dodać 110 zamknij nawias jest równa 284, a suma dzielników właściwych 284 otworzyć nawias 1 dodać 2 dodać 4 dodać 71 dodać 142 zamknąć nawias to 220. Każda liczba doskonała jest zaprzyjaźniona ze sobą. Obecnie znanych jest blisko 8000 par liczb zaprzyjaźnionych, nie wiadomo jednak, czy istnieje ich nieskończenie wiele.

Hipoteza Goldbacha: każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych

W $1724$ roku Christian Goldbach w liście do Leonharda Eulera, przedstawił hipotezę, że każdą liczbę naturalną większą od $2$ można przedstawić za pomocą trzech liczb pierwszych, gdzie liczby te mogą się powtórzyć (w tamtych czasach $1$ uważano za liczbę pierwszą).

Euler uprościł tę hipotezę i przedstawił ją następująco:
każda liczba naturalna parzysta większa od $2$ jest sumą dwóch liczb pierwszych.

A zatem:

$4 = 2 + 2$
$6 = 3 + 3$
$8 = 3 + 5$
$10 = 3 + 7 = 5 + 5$
$12 = 5 + 7$
$14 = 3 + 11 = 7 + 7$

Pomimo, iż sformułował ją w rezultacie Euler, nazwa nie została zmieniona, i to właśnie tę hipotezę do dzisiaj nazywamy hipotezą Goldbacha. Dlaczego hipoteza? Gdyż do dnia dzisiejszego nie doczekała się formalnego matematycznego dowodu.

Aplet

Zaobserwuj wskazania prostej, zmieniając wartości zawarte w suwaku. Co ilustrują punkty przedstawione na układzie współrzędnych? Jakie możesz wyciągnąć wnioski?

RAOC2DEDB1UGH

Zastosowanie liczb pierwszych w kryptografii

Omówimy teraz najczęściej dziś stosowany algorytm szyfrowania, jakim jest RSA. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców, czyli Rona Rivesta, Adiego Shamira oraz Leonarda Adlemana.

Zanim jednak opiszemy działanie algorytmu, wprowadzimy pojęcia matematyczne, które są przydatne do jego dokładnego omówienia.

Kongruencje i arytmetyka modularna

Przypomnijmy sobie dzielenie z resztą i bez reszty w zbiorze liczb naturalnych.

Wprowadźmy oznaczenie. Niech $n$ będzie liczbą naturalną większą od $1$ . Fakt, że liczby naturalne $a$ i $b$ dają z dzielenia przez $n$ tę samą resztę będziemy zapisywać następująco:

a \equiv b (\mod n)

Powyższy napis można odczytać jako “ $a$ przystaje do $b$ modulo $n$ ” albo “liczby $a$ i $b$ przystają modulo $n$ ”. Jeżeli któraś spośród liczb $a$ i $b$ jest mniejsza od liczby $n$ , wówczas jest ona równa reszcie z dzielenia każdej z liczb $a$ i $b$ przez $n$ .

Przykład 1

Ponieważ liczby $5$ i $9$ z dzielenia przez $2$ dają resztę $1$ , więc prawdą jest, że $5 \equiv 9 \equiv 1 (\mod 2)$ .

Ponieważ liczby $8$ i $23$ z dzielenia przez $3$ dają resztę $2$ , więc prawdą jest, że $8 \equiv 23 \equiv 2 (\mod 3)$ .

Ponieważ liczby $55$ i $10$ z dzielenia przez $5$ dają resztę $0$ , więc prawdą jest, że $55 \equiv 10 \equiv 0 (\mod 5)$ .

Ponieważ liczby $24$ i $38$ z dzielenia przez $7$ dają resztę $3$ , więc prawdą jest, że $24 \equiv 38 \equiv 3 (\mod 7)$ .

Kongruencje (relacja przystawania liczb modulo) mają wiele własności analogicznych do własności relacji równości, ale nie będziemy ich tutaj szczegółowo omawiać.

Rozważmy zbiór $ℤ_{n} = \{0, 1, 2, 3, \dots, n - 1\}$ wszystkich możliwych reszt z dzielenia przez liczbę naturalną $n$ większą od $1$ .

W zbiorze tym zdefiniujemy dwa działania:

dodawanie modulo $n$ (oznaczane symbolem $+_{n}$ ),
mnożenie modulo $n$ (oznaczane symbolem $\cdot_{n}$ ).

Niech $a$ i $b$ będą liczbami ze zbioru $ℤ_{n} = \{0, 1, 2, 3, \dots, n - 1\}$ . Wówczas sumą modulo $n$ liczb $a$ i $b$ nazywamy resztę z dzielenia liczby $a + b$ przez $n$ , zaś iloczynem modulo $n$ liczb $a$ i $b$ nazywamy resztę z dzielenia liczby $a \cdot b$ przez $n$ .

Przykład 2

Rozważmy zbiór $ℤ_{7} = \{0, 1, 2, 3, 4, 5, 6\}$ .

$0 +_{7} 2$ jest równe reszcie z dzielenia liczby $0 + 2 = 2$ przez $7$ , czyli $2$ .

$4 +_{7} 2$ jest równe reszcie z dzielenia liczby $4 + 2 = 6$ przez $7$ , czyli $6$ .

$4 +_{7} 5$ jest równe reszcie z dzielenia liczby $4 + 5 = 9$ przez $7$ , czyli $2$ .

$6 +_{7} 2$ jest równe reszcie z dzielenia liczby $6 + 2 = 8$ przez $7$ , czyli $1$ .

Cała tabliczka dodawania modulo $7$ znajduje się poniżej i zawiera wszystkie możliwe sumy dwóch liczb ze zbioru $ℤ_{7} = \{0, 1, 2, 3, 4, 5, 6\}$ .

$+_{7}$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$0$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$1$	$1$	$2$	$3$	$4$	$5$	$6$	$0$
$2$	$2$	$3$	$4$	$5$	$6$	$0$	$1$
$3$	$3$	$4$	$5$	$6$	$0$	$1$	$2$
$4$	$4$	$5$	$6$	$0$	$1$	$2$	$3$
$5$	$5$	$6$	$0$	$1$	$2$	$3$	$4$
$6$	$6$	$0$	$1$	$2$	$3$	$4$	$5$

Przykład 3

Rozważmy zbiór $ℤ_{5} = \{0, 1, 2, 3, 4\}$ .

$0 \cdot_{5} 2$ jest równe reszcie z dzielenia liczby $0 \cdot 2 = 0$ przez $5$ , czyli $0$ .

$1 \cdot_{5} 3$ jest równe reszcie z dzielenia liczby $1 \cdot 3 = 3$ przez $5$ , czyli $3$ .

$3 \cdot_{5} 2$ jest równe reszcie z dzielenia liczby $3 \cdot 2 = 6$ przez $5$ , czyli $1$ .

$3 \cdot_{5} 4$ jest równe reszcie z dzielenia liczby $3 \cdot 4 = 12$ przez $5$ , czyli $2$ .

Cała tabliczka mnożenia modulo $5$ znajduje się poniżej i zawiera wszystkie możliwe iloczyny dwóch liczb ze zbioru $ℤ_{5} = \{0, 1, 2, 3, 4\}$ .

$\cdot_{5}$	$0$	$1$	$2$	$3$	$4$
$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$2$	$3$	$4$
$2$	$0$	$2$	$4$	$1$	$3$
$3$	$0$	$3$	$1$	$4$	$2$
$4$	$0$	$4$	$3$	$2$	$1$

Można udowodnić wiele własności działań modulo $n$ w zbiorze $ℤ_{n} = \{0, 1, 2, 3, \dots, n - 1\}$ analogicznych do własności dodawania i mnożenia w zbiorze liczb całkowitych.

Niektóre można zaobserwować na powyższych przykładach:

zbiór $ℤ_{n} = \{0, 1, 2, 3, \dots, n - 1\}$ jest zamknięty na dodawanie modulo $n$ , co oznacza, że wynik tego działania należy do zbioru $ℤ_{n}$ ,
zbiór $ℤ_{n} = \{0, 1, 2, 3, \dots, n - 1\}$ jest zamknięty na mnożenie modulo $n$ , co oznacza, że wynik tego działania należy do zbioru $ℤ_{n}$ ,
$1$ jest elementem neutralnym mnożenia modulo $n$ ,
$0$ jest elementem neutralnym dodawania modulo $n$ ,
dodawanie modulo $n$ jest działaniem przemiennym,
mnożenie modulo $n$ jest działaniem przemiennym.

Ponadto możemy wprowadzić definicje liczb (elementów) przeciwnych i liczb (elementów) odwrotnych.

Liczby (elementy) przeciwne

Definicja: Liczby (elementy) przeciwne

Mówimy, że liczby $a$ i $b$ ze zbioru $ℤ_{n}$ są liczbami przeciwnymi modulo $n$ , jeśli ich suma modulo $n$ jest równa $0$ .

Liczby (elementy) odwrotne

Definicja: Liczby (elementy) odwrotne

Mówimy, że liczby $a$ i $b$ ze zbioru $ℤ_{n}$ są liczbami odwrotnymi modulo $n$ , jeśli ich iloczyn modulo $n$ jest równy $1$ .

Przykład 4

W zbiorze $ℤ_{7}$ parami liczb przeciwnych modulo $7$ są: $1$ i $6$ , $2$ i $5$ , $3$ i $4$ , bo $1 +_{7} 6 = 0$ , $2 +_{7} 5 = 0$ , $3 +_{7} 4 = 0$ . Zero jest liczbą przeciwną do samego siebie, bo $0 +_{7} 0 = 0$ .

W zbiorze $ℤ_{7}$ parami liczb odwrotnych modulo $7$ są: $2$ i $4$ , $3$ i $5$ , bo $2 \cdot_{7} 4 = 1$ , $3 \cdot_{7} 5 = 1$ .
Jedynka jest liczbą odwrotną do samej siebie, bo $1 \cdot_{7} 1 = 1$ . Podobnie liczba $6$ jest odwrotna sama do siebie, bo $6 \cdot_{7} 6 = 1$ .

Funkcja $φ$ Eulera

Funkcja $φ$ przyporządkowuje liczbie naturalnej $n$ liczbę liczb względnie pierwszych z $n$ , które nie są od niej większe.

Przykład 5

$φ (10)$ oznacza liczbę liczb naturalnych nie większych od $10$ , które są z dziesiątką względnie pierwsze.
Są to liczby: $1$ , $3$ , $7$ , $9$ i jest ich $4$ , zatem $φ (10) = 4$ .

$φ (11)$ oznacza liczbę liczb naturalnych nie większych od $11$ , które są z jedenastką względnie pierwsze.
Są to liczby: $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ , $10$ i jest ich $10$ , zatem $φ (11) = 10$ .

Zauważmy, że liczb względnie pierwszych z liczbą $11$ jest znacznie więcej, niż liczb względnie pierwszych z liczbą $10$ , pomimo że obie liczby różnią się tylko o $1$ . Powodem tego jest fakt, że liczba $11$ jest liczbą pierwszą, czyli poza jedynką nie ma dzielników mniejszych od siebie.

Ponieważ liczba pierwszaliczba pierwszaliczba pierwsza $p$ nie ma poza jedynką dzielników mniejszych niż $p$ , zatem wszystkie liczby naturalne mniejsze niż $p$ są z nią względnie pierwsze. Wynika stąd, że dla każdej liczby pierwszej $p$ zachodzi

φ (p) = p - 1

Przykład 6

Wyznaczymy $φ (49)$ .

Zauważmy, że liczba $49$ jest kwadratem liczby pierwszej $7$ ( $49 = 7^{2}$ ).

Zatem jedyne liczby nie większe od liczby $49$ , które nie są z nią względnie pierwsze to wielokrotności liczby $7$ , czyli $7 = 7 \cdot 1$ , $14 = 7 \cdot 2$ , $21 = 7 \cdot 3$ , $28 = 7 \cdot 4$ , $35 = 7 \cdot 5$ , $42 = 7 \cdot 6$ , $49 = 7 \cdot 7$ . Jest ich dokładnie $7$ .

Zatem $φ (49) = 49 - 7 = 42$ .

Przykład 7

Wyznaczymy $φ (p^{2})$ dla dowolnej liczby pierwszej $p$ .

Zauważmy, że jedyne liczby nie większe od $p^{2}$ , które nie są względnie pierwsze z $p^{2}$ to wielokrotności liczby $p$ , czyli liczby $p$ , $2 p$ , $3 p$ , $4 p$ , $\dots$ , $(p - 1) p$ , $p^{2}$ . Jest ich dokładnie $p$ .

Zatem $φ (p^{2})$ możemy otrzymać odejmując od liczby wszystkich liczb naturalnych od $1$ do $p^{2}$ liczbę wielokrotności liczby $p$ nie większych od liczby $p^{2}$ , zatem $φ (p^{2}) = p^{2} - p = p (p - 1)$ .

Przykład 8

Wyznaczymy $φ (p q)$ dla dowolnych liczby pierwszych $p$ i $q$ .

Zauważmy, że jedyne liczby nie większe od $p q$ , które nie są względnie pierwsze z $p q$ to wielokrotności liczby $p$ i wielokrotności liczby $q$ , czyli liczby $p$ , $2 p$ , $3 p$ , $4 p$ , $\dots$ , $(q - 1) p$ , $q p$ oraz liczby $q$ , $2 q$ , $3 q$ , $4 q$ , $\dots$ , $(p - 1) q$ , $p q$ .

Tych pierwszych jest dokładnie $p$ , zaś tych drugich dokładnie $q$ , ale liczba $p q$ jest wielokrotnością i liczby $p$ , i liczby $q$ , co oznacza, że razem tych liczb jest $(p + q - 1)$ .

Zatem $φ (p q)$ możemy otrzymać odejmując od liczby wszystkich liczb naturalnych od $1$ do $p q$ liczbę wielokrotności liczby $p$ nie większych od liczby $p q$ oraz liczbę wielokrotności liczby $q$ mniejszych od $p q$ .

Zatem $φ (p q) = p q - (p + q - 1) = p q - p - q + 1 = p (q - 1) - (q - 1) = (q - 1) (p - 1)$ .

Przykład 9

Wyznaczymy wartość funkcji $φ$ dla wybranych liczb naturalnych:

$φ (20)$ – liczby względnie pierwszeliczby względnie pierwszeliczby względnie pierwsze z liczbą $20$ i nie większe od niej to $1$ , $3$ , $7$ , $9$ , $11$ , $13$ , $17$ , $19$ , zatem $φ (20) = 8$

$φ (25)$ – liczba $25$ jest kwadratem liczby $5$ , więc możemy wykorzystać zależność z przykładu 7: $φ (25) = 25 - 5 = 20$

$φ (35)$ – liczba $35$ jest iloczynem dwóch liczb pierwszych ( $5$ i $7$ ), więc możemy skorzystać z zależności z przykładu 8: $φ (35) = φ (5 \cdot 7) = (5 - 1) (7 - 1) = 4 \cdot 6 = 24$

Twierdzenie Eulera

Twierdzenie: Twierdzenie Eulera

Jeśli $a$ i $m$ są względnie pierwszymi liczbami naturalnymi dodatnimi, to $m$ dzieli liczbę

a^{φ (m)} - 1

Równoważnie twierdzenie można sformułować następująco:

Jeśli $a$ i $m$ są względnie pierwszymi liczbami naturalnymi dodatnimi, to

a^{φ (m)} \equiv 1 (\mod m)

Dowód powyższego twierdzenia pominiemy, ale ma ono zasadnicze znaczenie w algorytmie RSA.

Przykład 10

Rozważmy $a = 22$ i $m = 35$ . Ponieważ $a = 2 \cdot 11$ i $m = 5 \cdot 7$ , więc liczby $22$ i $35$ są względnie pierwsze.

Na mocy twierdzenia Eulera $22^{φ (35)} \equiv 1 (\mod 35)$ .

Ponieważ $φ (35) = φ (5 \cdot 7) = (5 - 1) (7 - 1) = 4 \cdot 6 = 24$ , więc $22^{24} \equiv 1 (\mod 35)$ , co oznacza, że liczba $22^{24}$ z dzielenia przez $35$ daje resztę $1$ .

Szyfrowanie RSA

Opiszemy teraz krok po kroku działanie algorytmu RSA.

Losujemy dwie liczby pierwsze $p$ i $q$ .
Obliczamy iloczyn liczb $p$ i $q$ : $n = p \cdot q$ .
Obliczamy $φ (n) = φ (p q) = (p - 1) (q - 1)$ .
Wybieramy liczbę $J$ , która spełnia warunki: $1 < J < φ (n)$ oraz $J$ jest względnie pierwsze z $φ (n)$ ( $J$ nie jest dzielnikiem $φ (n)$ ).
Szyfrogramem (który zostaje przesłany) liczby $m$ jest liczba $c$ obliczona ze wzoru $c \equiv m^{J} (\mod n)$ .
Obliczamy $T$ tak, aby $T \cdot J \equiv 1 (\mod 𝜑 (𝑛))$ .
Aby odkodować otrzymany szyfrogram $c$ , obliczamy resztę z dzielenia liczby $c^{T}$ przez $n$ . Z własności kongruencji wynika, że $m = c^{T} (\mod n)$ .

Parę liczb $(n, J)$ nazywamy kluczem publicznym (jawnym), zaś parę $(n, T)$ nazywamy kluczem prywatnym (tajnym).

Przykład 11

Przyporządkujmy literom alfabetu liczby wg poniższego wzoru:

$a$	$b$	$c$	$d$	$e$	$f$	$g$	$h$	$i$	$j$	$k$	$l$
$01$	$02$	$03$	$04$	$05$	$06$	$07$	$08$	$09$	$10$	$11$	$12$

$ł$	$m$	$n$	$o$	$p$	$r$	$s$	$t$	$u$	$w$	$y$	$z$
$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$	$21$	$22$	$23$	$24$

Zaszyfrujemy słowo “rak”:

Wybieramy liczby pierwsze $p = 3$ i $q = 11$ .
Obliczamy $n = 3 \cdot 11 = 33$ .
Obliczamy $φ (33) = (3 - 1) (11 - 1) = 20$ .
Wybieramy $J$ większe od $1$ i mniejsze od $20$ względnie pierwsze z $20$ . Niech $J = 3$ .
Odczytujemy liczby odpowiadające literom słowa “rak”:

Litera	$r$	$a$	$k$
Liczba odpowiadająca (z tabeli powyżej)	$18$	$01$	$11$
$I$ etap szyfrowania – podnoszenie do potęgi $J = 3$	$18^{3} = 5832$	$1^{3} = 1$	$11^{3} = 1331$
$II$ etap szyfrowania – obliczanie reszty z dzielenia przez $33$	$5832 \equiv 24 (\mod 33)$	$1 \equiv 1 (\mod 33)$	$1331 \equiv 11 (\mod 33)$
Liczby do przesłania	$24$	$01$	$11$

Zatem szyfrogram do przesłania to $24 01 11$ .

Przykład 12

Chcemy odczytać szyfrogram $09 03 26$ , znając klucz publiczny $(n, J) = (33, 3)$ .

Osoba, która chce szyfrogramszyfrogramszyfrogram odczytać, potrzebuje klucza prywatnego, czyli takiej liczby $T$ , dla której $J \cdot T \equiv 1 (\mod 𝜑 (𝑛))$ . W naszym przypadku $3 T \equiv 1 (\mod 20)$ .
Ponieważ $3 \cdot 7 = 21 \equiv 1 (\mod 20)$ , więc $T = 7$ .
Możemy deszyfrowaćdeszyfrowaćdeszyfrować wiadomość:

Otrzymane liczby	$09$	$03$	$26$
$I$ etap szyfrowania – podnoszenie do potęgi $T = 7$	$9^{7} = 4782969$	$3^{7} = 2187$	$26^{7} = 8031810176$
$II$ etap szyfrowania – obliczanie reszty z dzielenia przez $33$	$4782969 \equiv 15 (\mod 33)$	$2187 \equiv 9 (\mod 33)$	$8031810176 \equiv 5 (\mod 33)$
Liczby po odszyfrowaniu	$15$	$09$	$05$
Litery odpowiadające odszyfrowanym liczbom	$n$	$i$	$e$

Otrzymana wiadomość to “ $n i e$ ” – wstrzymujemy się zatem z działaniem, o którym była mowa z nadawcą szyfrogramu...

W przykładzie $12$ , aby odczytać treść szyfrogramu, potrzebowaliśmy wartości $T$ . Znając klucz publiczny, mogliśmy ją obliczyć.
Można w takim razie zadać pytanie, na czym polega szyfrowanie, skoro wszystko można obliczyć...
Zwróć uwagę na to, że aby wyznaczyć $T$ , potrzebowaliśmy $φ (n)$ , czyli rozkład liczby $n$ na czynniki pierwsze.
Skuteczność algorytmu RSA opiera się na tym, że nawet superkomputery mają problemy z rozkładaniem naprawdę dużych liczb na czynniki pierwsze. Gdy ktoś chce włamać się do jakiejś bazy danych i potrzebuje złamać hasło, musi zrobić to na tyle szybko, aby nikt nie zdążył się zorientować, a rozkładanie liczby na czynniki pierwsze może zająć przynajmniej kilka dni. Z tego też powodu ciągle trwają poszukiwania coraz większych liczb pierwszych – im większe liczby pierwsze $p$ i $q$ pomnożymy, tym większą liczbę $n$ otrzymamy. Zaś im większe $n$ , tym trudniej rozłożyć je na czynniki.

Przykład 13

Spróbuj rozłożyć na czynniki pierwsze liczby:

a) $2627$ ,

b) $56153$ .

Udało się? Ile czasu Ci to zajęło?

Odpowiedzi:

a) $37 \cdot 71 = 2627$ ,

b) $241 \cdot 233 = 56153$ .

Ciekawostka

Największa odkryta dotąd (styczeń $2019$ ) liczba pierwsza to $2^{82589933} - 1$ i liczy sobie $24 862 048$ cyfr w zapisie dziesiętnym. Wyobraź sobie rozkład na czynniki liczb będących iloczynem liczb pierwszych tego rzędu.

Animacja multimedialna

Przeanalizuj sposób działania algorytmu RSA przedstawiony w animacji.

R575QSCFB41M7

Polecenie 1

RBCVP1GA9LOP5

Polecenie 2

R1967GQKVBNPD

Zestaw ćwiczeń interaktywnych

Pokaż ćwiczenia:

R1L5P1R89R7RU1

Ćwiczenie 1

RU3AF7269ZP9Q1

Ćwiczenie 2

Ćwiczenie 3

R17GQ1TFHLE13

R19KRRBFM6H2V

R18J89D34D2C92

Ćwiczenie 4

R17GHF387QJSQ2

Ćwiczenie 5

R12RMDHT6OQJZ2

Ćwiczenie 6

R1HBVNQT7L3O72

Ćwiczenie 7

RS5LCNGC783MQ2

Ćwiczenie 8

R12G6LDJCBRJZ3

Ćwiczenie 9

Ćwiczenie 10

Podejmij próbę odpowiedzi na pytanie zawarte w temacie dzisiejszych zajęć: Dlaczego liczby bliźniacze nie są zaprzyjaźnione?

R1PG1QLZSBEAQ

R1PFUX5H17B9S1

Ćwiczenie 11

Ćwiczenie 12

R6DEESP8RAE2S

R1CM9T4U28SUA

R1RTQZRRMEBCZ2

Ćwiczenie 13

Ćwiczenie 14

R1JBSP88GQH1H

R4B4SD9HRPDEV

ROX4SFSRCC8QA2

Ćwiczenie 15

Ćwiczenie 16

R1QFVQM9QGNUD

Rozwiąż test składający się z pięciu pytań.

REU25N7SBPGZS

RTZR42EQE66V2

R1654HVDP7EJR

RN9PF4XCBRR5N

R1HKJ1P8GPTRO

Ćwiczenie 17

Znajdź klucz prywatny, gdy klucz publiczny stanowią liczby $(n, J) = (91, 29)$ .

Zauważmy, że $91 = 7 \cdot 13$ . Teraz możemy obliczyć $φ (91) = (7 - 1) (13 - 1) = 6 \cdot 12 = 72$ .

Szukamy takiej liczby $T$ , dla której zachodzi $29 T \equiv 1 (\mod 72)$ .

Możemy zastosować metodę prób i błędów podstawiając pod $T$ kolejne liczby naturalne:

$29 \cdot 1 = 29 \equiv 29 (\mod 72)$

$29 \cdot 2 = 58 \equiv 58 (\mod 72)$

$29 \cdot 3 = 87 \equiv 15 (\mod 72)$

$29 \cdot 4 = 116 \equiv 44 (\mod 72)$

$29 \cdot 5 = 145 \equiv 1 (\mod 72)$

Zatem szukanym kluczem prywatnym jest $(n, T) = (91, 5)$ .

Ćwiczenie 18

Klucz publiczny to $(n, J) = (55, 27)$ . Znajdź klucz prywatny i rozszyfruj szyfrogram “ $17 24 01$ ”. Literom odpowiadają liczby z przykładu $11$ .

Zauważmy, że $n = 55 = 5 \cdot 11$ , zatem $φ (55) = 4 \cdot 10 = 40$ .

Szukamy takiego $T$ , aby $27 T \equiv 1 (\mod 40)$ .

Podstawiając kolejne liczby naturalne za $T$ otrzymujemy:

$27 \cdot 1 = 27 \equiv 27 (\mod 40)$

$27 \cdot 2 = 54 \equiv 14 (\mod 40)$

$27 \cdot 3 = 81 \equiv 1 (\mod 40)$

Zatem klucz prywatny to $(n, T) = (55, 3)$ .

Możemy odkodować szyfrogram:

$17^{3} = 4913 \equiv 18 (\mod 55)$ – liczba $18$ odpowiada literze $R$ ,

$24^{3} = 13824 \equiv 19 (\mod 55)$ – liczba $19$ odpowiada literze $S$ ,

$1^{3} = 1 \equiv 1 (\mod 55)$ – liczba $1$ odpowiada literze $A$ .

Zatem treść wiadomości to “ $R S A$ ”.

Słownik

liczby pierwsze

to liczby naturalne, które posiadają dwa dzielniki: liczbę $1$ i samą siebie

liczby względnie pierwsze

mówimy, że liczby naturalne $k$ i $m$ są względnie pierwsze, jeśli ich największym wspólnym dzielnikiem jest $1$

liczba pierwsza

liczba naturalna, która ma dokładnie $2$ różne dzielniki: $1$ i samą siebie

szyfrogram

wiadomość, która została zaszyfrowana

deszyfrować

odszyfrowywać wiadomość, która wcześniej została zaszyfrowana

Podzielność w zbiorze liczb naturalnych – dzielenie z resztą i bez reszty.

$+_{7}$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$0$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$1$	$1$	$2$	$3$	$4$	$5$	$6$	$0$
$2$	$2$	$3$	$4$	$5$	$6$	$0$	$1$
$3$	$3$	$4$	$5$	$6$	$0$	$1$	$2$
$4$	$4$	$5$	$6$	$0$	$1$	$2$	$3$
$5$	$5$	$6$	$0$	$1$	$2$	$3$	$4$
$6$	$6$	$0$	$1$	$2$	$3$	$4$	$5$

$\cdot_{5}$	$0$	$1$	$2$	$3$	$4$
$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$2$	$3$	$4$
$2$	$0$	$2$	$4$	$1$	$3$
$3$	$0$	$3$	$1$	$4$	$2$
$4$	$0$	$4$	$3$	$2$	$1$

$+_{7}$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$0$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$1$	$1$	$2$	$3$	$4$	$5$	$6$	$0$
$2$	$2$	$3$	$4$	$5$	$6$	$0$	$1$
$3$	$3$	$4$	$5$	$6$	$0$	$1$	$2$
$4$	$4$	$5$	$6$	$0$	$1$	$2$	$3$
$5$	$5$	$6$	$0$	$1$	$2$	$3$	$4$
$6$	$6$	$0$	$1$	$2$	$3$	$4$	$5$

$\cdot_{5}$	$0$	$1$	$2$	$3$	$4$
$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$2$	$3$	$4$
$2$	$0$	$2$	$4$	$1$	$3$
$3$	$0$	$3$	$1$	$4$	$2$
$4$	$0$	$4$	$3$	$2$	$1$

7. NWD, NWW

Zbiory liczbowe