Liczby półpierwsze – Wikipedia, wolna encyklopedia
Liczba półpierwsza – liczba naturalna będąca iloczynem dokładnie dwóch, niekoniecznie różnych liczb pierwszych.
Liczby półpierwsze odgrywają znaczącą rolę w kryptografii, bowiem liczba czynników pierwszych ma bezpośredni związek ze złożonością obliczeniową faktoryzacji.
Liczby półpierwsze występują maksymalnie po trzy obok siebie. Wynika to z podzielności przez 4. Nie może być 4 kolejnych liczb półpierwszych, bo jedna z nich byłaby podzielna przez 4, a więc podzielna przez 2, zatem musiałaby być równa 4. Ale 4 nie należy do żadnej czwórki kolejnych liczb półpierwszych, bo 3 i 5 nie są półpierwsze.
Przykłady
[edytuj | edytuj kod]Oto trójki kolejnych liczb półpierwszych mniejszych niż 1000:
- (33, 34, 35)
- (85, 86, 87)
- (93, 94, 95)
- (121, 122, 123)
- (141, 142, 143)
- (201, 202, 203)
- (213, 214, 215)
- (217, 218, 219)
- (301, 302, 303)
- (393, 394, 395)
- (445, 446, 447)
- (633, 634, 635)
- (697, 698, 699)
- (841, 842, 843)
- (921, 922, 923)
Przykładowe faktoryzacje:
Interesującym przypadkiem jest liczba z której obu stron znajdują się trójki liczb półpierwszych.