Liczba pierwsza co to

Liczba pierwsza – liczba naturalna, która ma dokładnie dwa dzielniki należące do zbioru liczb naturalnych (tj. dzieli się tylko przez jedynkę i samą siebię).

1. Algorytmy wyznaczania.
Algorytm wyznaczania – ciąg (schemat) czynności potrzebnych to uzyskania danego rezultatu, tutaj wyszukania wszystkich liczb pierwszych w danym zbiorze.
Najpopularniejszy algorytm wyznaczania liczb pierwszych, datowany na ok. 240 r p.n.e., przypisywany jest Eratostenesowi z Cyreny. Polega na wybraniu najmniejszej liczby z przedziału <2;n> (przedziału obustronnie domkniętego od 2 do n, gdzie n jest dowolną liczbą naturalną większą od 2), a następnie wykreśleniu z tego zbioru wszystkich jej wielokrotności oprócz niej samej. Analogicznie postępujemy z każdą kolejną niewykreśloną liczbą, aż nie będzie ona większa od . Każda niewykreślona liczba jest liczbą pierwszą.

2. Rozkład na czynniki pierwsze.
Jest to sposób zapisu dowolnej liczby naturalnej jako iloczynu liczb pierwszych. Aby rozłożyć liczbę, należy dzielić ją przez liczby pierwsze (nie możemy otrzymać reszty z dzielenia, więc liczby te muszą być jej dzielnikami) aż do uzyskania liczby 1.
Przykład rozkładu liczby na czynniki pierwsze:
265|:5
53|:53
1|
Więc rozkład liczby 265 na czynniki pierwsze to 5 53.
Inny przykład rozkładu liczby na czynniki pierwsze:
13650|:5
2730|:3
910|:2
455|:5
91|:7
13|:13
1|
Oznacza to, że rozkład liczby 13650 na czynniki pierwsze to 2 3 5 5 7 13.
Przy zapisywaniu rozkładu liczby warto pamiętać o dobrej kolejności. Uporządkowane rosnąco liczby wyglądają dużo lepej zarówno pod względem estetycznym jak i praktycznym.

3. Dowód Euklidesa.
Euklides udowodnił, że zbiór liczb pierwszych jest nieskończenie wielki. Oznacza to że dla dowolniej liczby naturalnej, zawsze znajdziemy liczbę pierwszą, która jest od niej większa.

4. Zastosowanie liczb pierwszych w kryptografii.
Najpopularniejszą metodą szyfrowania z wykorzystaniem liczb pierwszych jest algorytm RSA (od nazwisk twórców- R. Rivesta,
A. Shamira i L. Adlemana)- zaprojektowany w 1977 roku. Jest stosowany zarówno do szyfrowania i podpisów elektronicznych. Opiera się na trudności rozkładu na czynniki dużych liczb złożonych, nie jest jednak nie do złamania, gdyż pierwsza udana tego próba przebiegła w 1999 roku (w ramach konkursu RSA Factoring Challenge).

5. Rodzaje liczb pierwszych.
-liczby pierwsze bliźniacze- liczby pierwsze różniące się od siebie o 2 (p i p+2), tak, że obie są liczbami pierwszymi.
Przykładami par liczb bliźniaczych są 3 i 5, 5 i 7, 11 i 13.
-liczby pierwsze czworacze- cztery liczby różniące się o kolejno 2, 6, 8 od liczby p – najmniejszej z tych liczb (p, p+2, p+6, p+8), tak,
że wszystkie są liczbami pierwszymi.
Przykładami liczb czworaczych są 5, 7, 11, 13.
-liczby pierwsze palindromiczne (z gr. palindromos- biegnący na powrót)– liczby pierwsze czytane tak samo od prawej jak od lewej
strony. Przykładami liczb pierwszych palindromicznych są 11, 101, 929, 10601.

Oznaczenia w tym punkcie: p- dowolna liczba pierwsza.