Liczby pierwsze

Liczby pierwsze to liczby naturalne większe od jeden, które dzielą się tylko przez jeden i samą siebie. Są one fundamentem teorii liczb i mają szerokie zastosowanie w matematyce i kryptografii.

Definicja

Liczbą pierwszą nazywamy liczbę naturalną większą od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie.

Tabela liczb pierwszych do 100

12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100

Zbiór liczb pierwszych w przedziale od 1 do 100 jest następujący:

$$\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\}$$

Właściwości liczb pierwszych

  1. Każda liczba naturalna większa od 1 jest albo liczbą pierwszą, albo liczbą złożoną.
  2. Istnieje nieskończenie wiele liczb pierwszych (twierdzenie Euklidesa).
  3. Każdą liczbę naturalną większą od 1 można jednoznacznie rozłożyć na iloczyn liczb pierwszych (twierdzenie o rozkładzie na czynniki pierwsze).
  4. Jedyną parzystą liczbą pierwszą jest 2.

Liczby bliźniacze

Liczby bliźniacze to dwie liczby pierwsze, których różnica wynosi dwa. Oto przykłady liczb bliźniaczych w przedziale do 100:

  • 3 i 5
  • 5 i 7
  • 11 i 13
  • 17 i 19
  • 29 i 31
  • 41 i 43
  • 59 i 61
  • 71 i 73

Hipoteza Goldbacha

Hipoteza Goldbacha to jedno z najstarszych nierozwiązanych problemów w teorii liczb i całej matematyce. Stwierdza ona, że:

Każda parzysta liczba naturalna większa od 2 może być przedstawiona jako suma dwóch liczb pierwszych.

Na przykład:

  • 4 = 2 + 2
  • 6 = 3 + 3
  • 8 = 3 + 5
  • 10 = 5 + 5
  • 100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53

Mimo że hipoteza została sprawdzona dla bardzo dużych liczb, do tej pory nie udało się jej udowodnić dla wszystkich liczb parzystych.

RSA - zastosowanie liczb pierwszych w kryptografii

RSA (od nazwisk twórców: Rivest, Shamir, Adleman) to jeden z najpopularniejszych algorytmów kryptografii asymetrycznej, który opiera się na właściwościach liczb pierwszych. Podstawowe kroki algorytmu RSA to:

  1. Wybór dwóch dużych liczb pierwszych p i q.
  2. Obliczenie n = p * q (moduł) i funkcji Eulera φ(n) = (p-1) * (q-1).
  3. Wybór liczby e (klucz publiczny) względnie pierwszej z φ(n).
  4. Obliczenie d (klucz prywatny) jako odwrotności modularnej e modulo φ(n).
  5. Szyfrowanie: c = m^e mod n, gdzie m to wiadomość, a c to szyfrogram.
  6. Deszyfrowanie: m = c^d mod n.

Bezpieczeństwo RSA opiera się na trudności faktoryzacji dużych liczb na czynniki pierwsze, co pokazuje praktyczne znaczenie liczb pierwszych w nowoczesnej kryptografii.

Podsumowanie

Liczby pierwsze, mimo swojej prostej definicji, są fascynującym obiektem badań matematycznych. Ich właściwości i zastosowania, od podstawowych zagadnień teorii liczb po zaawansowane systemy kryptograficzne, sprawiają, że są one kluczowym elementem współczesnej matematyki i informatyki.