Liczby pierwsze

W poprzednim artykule dość szczegółowo opisałem test Millera-Rabina służący do szybkiego sprawdzania pierwszości liczb. Tym razem porównajmy sobie jego działanie z innymi szybkimi, probabilistycznymi testami pierwszości i sprawdźmy, jak wypadają one w porównaniu do bezbłędnej metody naiwnej.

Wiemy już: czym są liczby pierwsze, jak sprawdzać, czy liczba jest pierwsza, jak w najprostszy sposób znajdować je, a także poznaliśmy teorię stojącą za znajdowaniem dużych liczb pierwszych. Przejdźmy zatem do praktyki. Czas napisać algorytm, który w krótkim czasie pozwoli nam znaleźć bardzo duże liczby pierwsze, tak jak to się robi w codziennych zastosowaniach.

Do tej pory przedstawiłem, czym są liczby pierwsze, ich zastosowania, jak możemy sprawdzać pierwszość liczb oraz jak możemy prostymi sposobami znajdować je. Jednak wszystko to, co do tej pory opowiedzieliśmy sobie, jest w dużej mierze zabawą. Jak poruszyłem już na samym początku serii, w kryptografii wykorzystuje się liczby pierwsze 2048-bitowe, więc w systemie dziesiętnym mogą one mieć nawet 617 cyfr. Dowiedzmy się więcej, jak jesteśmy w stanie odkryć tak duże, a nawet i większe liczby pierwsze. Na razie tylko w teorii.

Ostatnio opisałem, czym są liczby pierwsze, a także pokazałem prosty, niemal 800-letni algorytm do ich testowania. Jednak nie kończmy na tym tematu. O liczbach pierwszych można mówić dużo, dlatego kontynuujmy. Tym razem pokażę, jakie mamy najprostsze sposoby na znajdowanie liczb pierwszych.

Liczby pierwsze to jeden z ważniejszych terminów w matematyce, do tego mający dość istotne zastosowanie praktyczne. Na samym początku przygody z tym tematem przedstawmy sobie teorię, a także najprostsze testy pierwszości.