Liczba półpierwsza

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Liczba półpierwsza – liczba rozkładająca się na iloczyn dokładnie dwóch liczb pierwszych (na dokładnie dwa czynniki pierwsze).

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.

Interesującą własnością takich liczb jest następujące stwierdzenie:

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 i przez dwa, 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:

  • 33 = 3 • 11, 34 = 2 • 17, 35 = 5 • 7
  • 85 = 5 • 17, 86 = 2 • 43, 87 = 3 • 29
  • 93 = 3 • 31, 94 = 2 • 47, 95 = 5 • 19

Interesującym przypadkiem jest liczba 216 = (2 • 3)3, z której obu stron znajdują się trójki liczb półpierwszych.