Liczby pierwsze to coś więcej niż tylko liczby, które można podzielić tylko przez siebie i jeden. Stanowią matematyczną tajemnicę, której sekrety matematycy próbują odkryć, odkąd Euklides dowiódł, że jest ich nieskończenie wiele.
Trwający projekt – Great Internet Mersenne Prime Search – którego celem jest odkrywanie coraz większej liczby liczb pierwszych, które zapisujemy w postaci 2^p-1, gdzie p jest liczbą pierwszą, zaowocował odkryciem jednej z największych znanych do tej pory liczb pierwszych. Liczba ta posiada 23 249 425 cyfr, jest tak duża, że z łatwością zapełniłaby 9000 stron książki. Dla porównania, szacuje się, że liczba atomów w całym obserwowalnym wszechświecie nie przekracza 100 cyfr.
Liczba, zapisana po prostu jako 2^77232917-1 została znaleziona przez wolontariusza, który poświęcił temu przedsięwzięciu 14 lat czasu obliczeniowego.
Być może zastanawiasz się, dlaczego liczba ta przekracza 23 miliony cyfr, dlaczego musimy o tym wiedzieć? Z pewnością najważniejsze liczby to te, których możemy użyć do ilościowego określenia naszego świata? Nie do końca o to chodzi o to. Musimy znać właściwości różnych liczb, abyśmy mogli nie tylko rozwijać technologię, na której polegamy, ale także zapewnić jej bezpieczeństwo.
Tajemnica liczb pierwszych
Jednym z najczęściej używanych zastosowań liczb pierwszych w informatyce jest system szyfrowania RSA. W 1978 Ron Rivest, Adi Shamir i Leonard Adleman połączyli kilka prostych, znanych faktów na temat liczb, aby stworzyć RSA. Opracowany przez nich system pozwala na bezpieczne przesyłanie informacji takich jak numery kart kredytowych.
Pierwszym składnikiem wymaganym w algorytmie są dwie duże liczby pierwsze. Im większe liczby, tym bezpieczniejsze szyfrowanie. Liczenie liczb jeden, dwa, trzy, cztery i tak dalej – zwane też liczbami naturalnymi – jest tu oczywiście niezwykle przydatne. Ale liczby pierwsze są budulcem wszystkich liczb naturalnych (patrz rozkład na czynniki pierwsze), a więc są jeszcze ważniejsze.
Weźmy na przykład liczbę 70. Podział pokazuje, że jest iloczynem 2*35. Ponadto 35 jest iloczynem 5*7. Zatem 70 jest iloczynem trzech mniejszych liczb: 2*5*7. To koniec drogi dla 70, bo żadnego z nich nie da się dalej rozbić. Znaleźliśmy czynniki pierwsze, które składają się na 70.
Mnożenie dwóch liczb, nawet bardzo dużych, jest być może żmudnym, ale prostym zadaniem. Z drugiej strony znalezienie rozkładu na czynniki pierwsze jest niezwykle trudne i właśnie to wykorzystuje system RSA.
Załóżmy, że Alicja i Marek chcą potajemnie komunikować się przez Internet. Wymagają systemu szyfrowania. Jeśli po raz pierwszy spotkają się osobiście, mogą wymyślić metodę szyfrowania i odszyfrowywania, którą tylko oni będą znali, ale jeśli początkowa komunikacja odbywa się online, muszą najpierw otwarcie przekazać informacje o samym systemie szyfrowania – ryzykowne przedsięwzięcie.
Jeśli jednak Alicja wybierze dwie duże liczby pierwsze, obliczy ich iloczyn i przekaże to otwarcie, ustalenie, jakie były jej pierwotne liczby pierwsze, będzie bardzo trudnym zadaniem, ponieważ tylko ona zna czynniki.
Więc Alicja przekazuje swój iloczyn Markowi, zachowując w tajemnicy swoje czynniki. Marek używa iloczynu do zaszyfrowania swojej wiadomości do Alicji, którą można odszyfrować tylko przy użyciu znanych jej czynników. Jeśli Ewa podsłuchuje, nie może odszyfrować wiadomości Marka, chyba że zdobędzie czynniki Alicji, które nigdy nie zostały przekazane. Jeśli Ewa spróbuje rozbić produkt na czynniki pierwsze – nawet przy użyciu najszybszego superkomputera – nie istnieje żaden znany algorytm, który mógłby to zrobić w czasie mniejszym niż milion lat.
Pierwotna misja
Duże liczby pierwsze są również używane w innych systemach kryptografii. Im szybsze komputery, tym większe liczby mogą złamać. W nowoczesnych zastosowaniach wystarczą liczby pierwsze mierzące setki cyfr. Te liczby są znikome w porównaniu z niedawno odkrytym gigantem. W rzeczywistości nowa liczba pierwsza jest tak duża, że – w chwili obecnej – żaden wyobrażalny postęp technologiczny w zakresie prędkości obliczeniowej nie może prowadzić do konieczności wykorzystania jej dla bezpieczeństwa kryptograficznego. Jest nawet prawdopodobne, że ryzyko stwarzane przez zbliżające się komputery kwantowe nie wymagałoby używania aż tak gigantycznych liczb do szyfrowania.
Słynny brytyjski matematyk Godfrey Harold Hardy powiedział: „Czysta matematyka jest ogólnie bardziej użyteczna niż stosowana. Przydatna jest bowiem przede wszystkim technika, a techniki matematycznej uczy się głównie przez czystą matematykę”. To, czy ogromne liczby pierwsze, takie jak liczba z początku artykułu z milionami cyfr, kiedykolwiek okażą się przydatne, jest, przynajmniej dla Hardy'ego, kwestią nieistotną.
Zasługa znajomości tych liczb polega na zaspokojeniu intelektualnego pragnienia rasy ludzkiej, które zaczęło się od dowodu Euklidesa na nieskończoność liczb pierwszych i trwa do dziś.
Dygresyjnie warto również wspomnieć tutaj o spirali Ulama oraz hipotezie Riemanna. Za pomocą tej drugiej da się określić funkcję, która określa liczbę liczb pierwszych aż do liczby naturalnej n. Na osobę, która wspomnianą hipotezę udowodni czeka nagroda miliona dolarów ufundowana przez Instytut Matematyczny Claya. Uwaga! Problem jest jednym z największych problemów współczesnej matematyki, więc nie jest to łatwy sposób na zarobek. Ta pierwsza natomiast to pewien geometryczny wzór, który ukazuje się, gdy liczby pierwsze zaczniemy wypisywać spiralnie. W wielkiej skali da się zauważyć, że liczby pierwsze układają się w sposób, któy sugeruje, że ich rozmieszczenie nie jest losowe. Google podrzuci mnóstwo grafik :)
