Liczby pseudopierwsze
Liczby pseudopierwsze to liczby naturalne, które wykazują pewne cechy liczb pierwszych, ale same do nich nie należą. Najważniejszą grupą w tej kategorii są liczby pseudopierwsze Fermata, które spełniają warunki małego twierdzenia Fermata: dla pewnego a, ap−1 − 1 jest podzielne przez p. Liczba p, która nie jest pierwsza, nazywana jest pseudopierwszą przy podstawie a.
Liczba, która jest pseudopierwsza dla każdej podstawy względnie pierwszej z nią, nosi nazwę liczby Carmichaela. Najmniejszą liczbą pseudopierwszą przy podstawie 2 jest 341, która nie jest liczbą pierwszą (341 = 11 • 31), ale spełnia warunki twierdzenia: 2340 ≡ 1 (mod 341).
Zastosowanie w kryptografii
Rzadkość liczb pseudopierwszych ma znaczenie w praktycznych zastosowaniach, takich jak algorytmy kryptografii asymetrycznej, w tym RSA. W tych algorytmach generuje się losowe liczby nieparzyste i testuje, czy są pierwsze. Zamiast stosować czasochłonne metody deterministyczne, wykorzystuje się probabilistyczne testy, takie jak test pierwszości Fermata.
Inne kategorie liczb pseudopierwszych
- Liczby silnie pseudopierwsze
- Liczby pseudopierwsze Eulera-Jacobiego
Dla tych kategorii nie istnieją odpowiedniki liczb Carmichaela, a algorytmy testowania to Solovaya-Strassena oraz Millera-Rabina.
Rzadkość liczb pseudopierwszych
Choć istnieje nieskończoność liczb pseudopierwszych przy danej podstawie, są one dość rzadkie. Na przykład, przy podstawie 2 istnieją tylko 3 liczby pseudopierwsze mniejsze od 1000 oraz 245 takich liczb mniejszych od miliona. Liczby pseudopierwsze przy podstawie 2 nazywane są również liczbami Pouleta.
Podsumowanie
Liczby pseudopierwsze odgrywają istotną rolę w kryptografii i teorii liczb. Ich unikalne właściwości i rzadkość sprawiają, że są przedmiotem intensywnych badań oraz praktycznych zastosowań w bezpiecznej transmisji danych.
