29/01/2025
Liczby pierwsze – matematyczne filary technologii i bezpieczeństwa oraz co to jest kryptografia 🔢💎
Liczby pierwsze – proste w definicji, a jednak pełne zagadek i praktycznych zastosowań. Od starożytności po współczesną technologię liczby pierwsze inspirują i zmieniają świat. Dlaczego są tak ważne i jakie tajemnice skrywają? Oto ich fascynująca historia.
Czym są liczby pierwsze?
Liczba pierwsza to taka liczba całkowita większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Przykłady kilku pierwszych liczb pierwszych to:
2,3,5,7,11,13,17,19,23...
Każda liczba całkowita większa od 1, która nie jest pierwsza, nazywana jest liczbą złożoną. Każdą liczbę złożoną można zapisać jako iloczyn liczb pierwszych. Na przykład:
28=2⋅2⋅7
💎Dlaczego 1 nie jest liczbą pierwszą?
Liczba 1 ma tylko jeden dzielnik – samą siebie – więc nie spełnia definicji liczby pierwszej, która wymaga dokładnie dwóch dzielników.
Wykluczenie 1 z definicji liczb pierwszych ma również praktyczne znaczenie. Każdy rozkład liczby na czynniki pierwsze jest dzięki temu jednoznaczny i precyzyjny. Na przykład:
30=2⋅3⋅5
Gdyby 1 była liczbą pierwszą, moglibyśmy ją dodawać nieskończenie wiele razy:
30=2⋅3⋅5⋅1⋅1⋅1⋅…
Taki zapis byłby nieskończony i niejednoznaczny.
💎 Wyjątkowość i samotność liczby 2
Wśród liczb pierwszych tylko 2 jest parzysta. Wszystkie inne liczby parzyste są podzielne przez 2, więc nie mogą być liczbami pierwszymi. Dlatego 2 stoi samotnie w świecie liczb pierwszych. to ciekawe, że pierwszą liczbą pierwszą jest jedyna liczba parzysta.
💎Wyjątkowe grupy liczb pierwszych
Już pierwsza para dwóch kolejnych liczb pierwszych jest wyjątkowa 2 i 3. To jedyne dwie kolejne liczby pierwsze. Żadne inne liczby nie spełniają tego warunku, ponieważ jedna z dwóch kolejnych liczb zawsze będzie parzysta.
Wyjątkową grupą liczb pierwszych są kolejne liczby 3, 5, 7, które są również kolejnymi liczbami nieparzystymi. To jedyny taki przypadek wśród liczb pierwszych! 🎯
Kolejne wyjątkowe grupy to liczby bliźniacze, czyli pary liczb pierwszych różniących się o 2, np.: 11,13 lub 17,19.
Matematycy od wieków zastanawiają się, czy takich par jest nieskończenie wiele. Do dziś nie znamy odpowiedzi na to pytanie.
💎Palindromiczne liczby pierwsze i liczby repunit
Ciekawymi liczbami pierwszymi są te, które są palindromem np. 101, 74747, 1003001. Warto zauważyć, że palindromiczne liczby pierwsze, poza liczbą 11, muszą mieć nieparzystą liczbę cyfr. Liczba 11, jak widać, też jest wyjątkową liczbą pierwszą.
Szczególnym przypadkiem takich palindromów są liczby repunit, czyli liczby złożone z samych jedynek, czyli liczby postaci 𝐑ₙ, gdzie n oznacza liczbę cyfr 1.
Liczby repunit, które są pierwsze, to m.in.:
𝐑₂ =11, czy 𝐑₁₉ =11...1 - liczba złożona z 19 jedynek
Największa na ten moment odkryta liczba pierwsza repunit 𝐑₄₉₀₈₁, która ma aż 49081 cyfr!
💎 Inne ciekawe liczby pierwsze
Ludzie szukają liczb pierwszych o pięknej dla nich budowie, np. liczbą pierwszą jest liczba 1234567891 czy innych liczb pierwszych inspirowanych liczbą π, gdzie liczba składa się z kolejnych cyfr rozwinięcia tej liczby, jak np. 314159, gdzie mamy 6 pierwszych cyfr liczby π. Pod tym względem robi niesamowite wrażenie liczba π z 38 cyframi, a wygląda ona tak:
31415926535897932384626433832795028841
♾️ Nieskończoność liczb pierwszych
Już starożytni Grecy wiedzieli, że liczb pierwszych jest nieskończenie wiele. Udowodnił to Euklides ponad 2300 lat temu! Jego dowód opiera się na prostym, ale genialnym rozumowaniu: jeśli przyjmiemy, że istnieje skończona liczba liczb pierwszych, to zawsze możemy znaleźć większą liczbę, która także jest pierwsza. Dlatego ich ciąg nigdy się nie kończy.
Liczby Mersenne’a – największe znane liczby pierwsze
Liczby Mersenne’a mają postać:
Mₚ = 2ᵖ − 1,
gdzie p jest liczbą pierwszą.
Nie każda liczba Mersenne’a jest liczbą pierwszą, ale te, które są, odgrywają szczególną rolę w matematyce. Obecnie znamy 52 liczb Mersenne’a, a największa z nich to:
2¹³⁶²⁷⁹⁸⁴¹ − 1, która ma 41 024 320 cyfr i jest to największa do tej pory odkryta liczba pierwsza.
Liczbę tę odkrył Luke Durant 12 października 2024 w ramach projektu GIMPS (ang. Great Internet Mersenne Prime Search, pol. Wielkie Internetowe Poszukiwanie Liczb Pierwszych Mersenne’a). To projekt obliczeniowy oparty na współpracy wolontariuszy z całego świata, mający na celu poszukiwanie liczb Mersenne’a, które są jednocześnie liczbami pierwszymi.
Odkrycie takich liczb wymaga lat pracy i ogromnej mocy obliczeniowej. Każda kolejna liczba Mersenne’a przesuwa granice możliwości technologicznych i matematycznych.
Rekordowe liczby pierwsze to dowód, że zawsze możemy przesuwać granice możliwości. W ich odkryciach uczestniczą tysiące ludzi z całego świata w ramach projektów takich jak GIMPS, łącząc matematykę, technologię i pasję.
🥇Nagroda i prestiż za odkrywanie nowych liczb pierwszych, czyli po co szukamy liczb pierwszych?
Odkrycie każdej kolejnej największej liczby pierwszej jest wydarzeniem matematycznym. Za takie odkrycia przyznawane są nagrody – np. za liczbę pierwszą mającą ponad 100 milionów cyfr można otrzymać 150 000 USD! Ale nagroda finansowa to tylko jeden z aspektów. Praca nad liczbami pierwszymi testuje granice ludzkiej pomysłowości i zaawansowania technologicznego
Może wydawać się, że to tylko matematyczna zabawa, ale nic bardziej mylnego! Liczby pierwsze mają realne, praktyczne zastosowania. Poszukiwanie rekordowych liczb pierwszych testuje granice naszych algorytmów i sprzętu komputerowego. To swoiste laboratorium, które pomaga rozwijać technologię także w innych dziedzinach, takich jak analiza danych czy sztuczna inteligencja.
Liczby pierwsze – strażnicy naszych danych 🔒
Liczby pierwsze – proste w definicji, ale kluczowe dla bezpieczeństwa cyfrowego świata. Bez nich internet, bankowość online czy ochrona prywatnych danych nie byłyby możliwe. Ale jak właściwie działają w kryptografii RSA – jednym z fundamentów współczesnych systemów szyfrowania?
Przyjrzyjmy się fundamentalnym założeniom tego algorytmu. RSA to algorytm szyfrowania, który działa na zasadzie dwóch kluczy: publicznego i prywatnego. Klucz publiczny jest dostępny dla każdego i służy do szyfrowania wiadomości. Klucz prywatny, znany tylko odbiorcy, pozwala odszyfrować wiadomość.
RSA opiera się na fascynującym problemie matematycznym: trudności rozkładu dużych liczb na czynniki pierwsze.
Klucz publiczny zawiera liczbę n, która jest iloczynem dwóch bardzo dużych liczb pierwszych p i q. Faktoryzacja to proces rozkładania liczby n na jej czynniki pierwsze, czyli znalezienie p i q. Choć łatwo jest obliczyć n=p⋅q, proces odwrotny, czyli faktoryzacja, staje się w przypadku ekstremalnie trudnym problemem, gdy p i q są liczbami o setkach cyfr. Na tej trudności opiera się bezpieczeństwo RSA.
Klucz publiczny zawiera liczbę n, która jest iloczynem dwóch bardzo dużych liczb pierwszych p i q.
Klucz prywatny zawiera te liczby pierwsze – p i q. Dzięki nim możliwe jest odszyfrowanie wiadomości.
W rzeczywistości RSA to bardziej skomplikowany algorytm, ale aby zrozumieć jego zasadę działania, skupimy się na kluczowym elemencie: rozkładzie liczby n na czynniki p i q. Algorytm zawiera kolejne kroki, ale bez tego rozkładu nie można przejść do dalszych działań. Zobaczmy jak to działa w praktyce.
Przykład 1️⃣
Weźmy dwie 3-cyfrowe liczby pierwsze: p=101, q=103
Mnożymy je razem, aby otrzymać n=p⋅q=101⋅103=10403
Załóżmy teraz, że ktoś zna tylko n=10403 i próbuje znaleźć liczby p i q. Aby to zrobić, należy sprawdzić, które liczby pierwsze są dzielnikami n.
Nie trzeba testować wszystkich możliwych liczb – wystarczy sprawdzić liczby pierwsze mniejsze od liczby √n:
√10403 ≈ 102
Liczby pierwsze mniejsze od 102 to:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101
Rozpoczynamy sprawdzanie – dzielimy n przez kolejne liczby pierwsze z listy. Jeśli idziemy po kolei, to dopiero 26. próba (ostatnia wyznaczona do testowania liczba pierwsza) zakończy się sukcesem, czyli podzieleniem bez reszty. W tym przypadku będzie to liczba 101. Po wykonaniu dzielenia mamy:
10403÷101=103
Rozkład zakończony: n=101⋅103
Teraz, znając p=101 i q=103, możemy wykorzystać te liczby w dalszych operacjach do odszyfrowania wiadomości w systemie kryptograficznym RSA.
Ale co się stanie, gdy liczby pierwsze będą większe?
Przykład 2️⃣
Weźmy dwie 5-cyfrowe liczby pierwsze: p=10007, q=10009
Ich iloczyn to n=10007⋅10009=100160063
Ponownie próbujemy rozłożyć n na czynniki. Obliczamy √n:
√100160063 ≈ 10008
Musimy przetestować liczby pierwsze mniejsze od 10008. Jest ich znacznie więcej niż poprzednio – dokładnie 1230. Nie będziemy ich już wypisywać, ale jeśli byśmy sprawdzali kolejno, czy liczba n dzieli się przez kolejne liczby pierwsze, to w 1230. próbie dojdziemy do dzielenia bez reszty.
100160063÷10007=10009
Rozkład zakończony!
Przykłady z liczbami 101 i 103, a także 10007 i 10009, to matematyczne rozgrzewki. W praktyce RSA korzysta z liczb p i q, które mają po setki cyfr. Ale zanim tam dojdziemy, zobaczmy, jak skaluje się trudność.
Przykład 3️⃣
Weźmy liczby pierwsze dziesięciocyfrowe: p=1000000007, q=1000000009
Iloczyn tych liczb będzie równy n=p⋅q=1000000007⋅1000000009=1000000016000000063
Ponownie próbujemy rozłożyć n na czynniki. Obliczamy √n:
√1000000016000000063≈1000000008
Liczb pierwszych mniejszych od tej liczby jest już aż 50 847 535 !
Prawie 51 milionów liczb pierwszych do przetestowania! Ten proces się niesamowicie szybko wydłuża. A daliśmy jako wyjściowe liczby tylko liczby 10-cyfrowe.
Już przy liczbach 25-cyfrowych robią się ogromnie uciążliwe obliczenia oraz niebotyczny czas, żeby ten proces przeprowadzić. Najlepsze i najdroższe komputery osobiste dostępne w roku 2025 i pracujące z prędkością ponad 80 bilionów operacji na sekundę potrzebowały by kilkudziesięciu lat. Przy liczbach 50-cyfrowych czas przekracza już wszelkie wyobrażenia.
I wiecie co? Dla algorytmu RSA to dalej niewiele znaczące liczby.⚡
Liczby 50- i 100-cyfrowe, choć na pierwszy rzut oka wydają się ogromne, są niczym w porównaniu do liczb używanych w rzeczywistych implementacjach algorytmu RSA. Bezpieczeństwo RSA opiera się na trudności faktoryzacji bardzo dużych liczb pierwszych, dlatego w praktyce operuje się na liczbach o setkach cyfr, a dokładniej na kluczach o długościach wyrażanych w bitach.
Jakie liczby są używane w RSA? 🔒
Długość klucza RSA (np. 1024, 2048, 3072 bitów) odnosi się do długości w bitach liczby n.
Przykłady rzeczywistych długości kluczy:
🗝️ 1024-bitowy klucz RSA:
n ma około 309 cyfr.
Liczby p i q mają po około 155 cyfr każda.
Obecnie uznawany za niebezpieczny, możliwy do złamania przy użyciu dużych zasobów.
🗝️ 2048-bitowy klucz RSA:
n ma około 617 cyfr.
Liczby p i q mają po około 309 cyfr.
Standardowy poziom bezpieczeństwa w większości systemów (w 2025 roku).
Szacowany czas złamania: przekracza wiek Wszechświata przy użyciu współczesnych komputerów.
🗝️ 3072-bitowy klucz RSA:
n ma około 926 cyfr.
Liczby p i q mają po około 463 cyfr.
Zalecany do zastosowań wymagających długoterminowego bezpieczeństwa.
🗝️ 4096-bitowy klucz RSA:
n ma około 1234 cyfr.
Liczby p i q mają po około 617 cyfr.
Używane w systemach o bardzo wysokich wymaganiach bezpieczeństwa, np. rządowych.
Rozkład takich liczb na czynniki zajmuje miliardy lat przy użyciu współczesnych technologii.
🖥️ Czy komputery kwantowe zagrażają szyfrowaniu?
Mówi się, że komputery kwantowe mogłyby zagrozić kryptografii RSA, ponieważ teoretycznie są w stanie rozłożyć liczbę na czynniki znacznie szybciej niż klasyczne komputery, dzięki algorytmowi Shora.
Na szczęście obecne komputery kwantowe są zbyt słabe, aby złamać szyfry RSA-2048.
Jednocześnie rozwijana jest postkwantowa kryptografia, która w przyszłości zabezpieczy nasze dane przed tym zagrożeniem.
Liczby pierwsze są fundamentem współczesnego bezpieczeństwa cyfrowego. Ich piękno tkwi nie tylko w prostocie definicji, ale także w potężnym wpływie, jaki mają na nasze życie. To nie tylko matematyczna ciekawostka, ale kluczowy element ochrony danych w erze cyfrowej. 📐🔒
Autor: Dariusz Kulma
Źródła:
Wikipedia:
Liczby pierwsze
Kryptografia RSA
SymPy (Python):
Obliczenia liczby liczb pierwszych (funkcja sympy.primepi), weryfikacja pierwszości (sympy.isprime) oraz testy numeryczne.
Projekt GIMPS (Great Internet Mersenne Prime Search):
Oficjalna strona projektu GIMPS – informacje o liczbach Mersenne’a, rekordowych liczbach pierwszych i ich odkrywaniu.
