Liczba pierwsza - Polski Serwis Naukowy

Liczba pierwsza – liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np. 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, itp.

Zbiór wszystkich liczb pierwszych oznacza się symbolem $\mathbb{P}$ . Liczby naturalne większe od 1, które nie są pierwsze, nazywa się liczbami złożonymi. Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożone.

RSA - jeden z pierwszych i obecnie jeden z najpopularniejszych asymetrycznych algorytmów kryptograficznych, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy, który można stosować zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.
Dzielnik – w matematyce dla danej liczby całkowitej liczba całkowita, która dzieli ją bez reszty. W matematyce elementarnej dzielnikiem nazywa się dowolną liczbę, przez którą się dzieli.

Podstawowe własności

Najmniejszy różny od jedynki dzielnik naturalny liczby naturalnej, większej od jedności, jest liczbą pierwszą.

Euklides pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych: Niech X będzie skończonym zbiorem liczb pierwszych. Niech x będzie iloczynem wszystkich liczb występujących w X (gdy X jest puste, to x=1). Jedynym wspólnym dzielnikiem liczb x oraz x+1 jest 1. Zatem żadna liczba pierwsza, występująca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Więc x+1 ma dzielnik p, który jest liczbą pierwszą. Liczba pierwsza p nie należy do X (bo jest dzielnikiem liczby x+1).

Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych. Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero Gauss. Twierdzenie to oznacza, że liczby pierwsze są w pewnym sensie atomami, z których przy pomocy mnożenia zbudowane są pozostałe liczby.

Wyznaczanie

Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym można posłużyć się algorytmem sito Eratostenesa: jeśli liczba naturalna N większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z N, to N jest liczbą pierwszą.

Test pierwszości to algorytm określający czy dana liczba jest pierwsza czy złożona. Nie jest to równoważne znalezieniu jej rozkładu na czynniki pierwsze. W obecnej chwili (2009 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.
Szereg – konstrukcja umożliwiająca wykonanie uogólnionego dodawania przeliczalnej liczby składników. Przykładem znanego szeregu jest dychotomia Zenona z Elei

Sito Eratostenesa - metoda znajdowania liczb pierwszych

Natomiast metoda, która daje odpowiedź na pytanie czy dana liczba naturalna jest pierwsza, czy nie – nosi nazwę testu pierwszości. Wśród takich metod praktyczne zastosowanie mają testy probabilistyczne, to znaczy takie, które pozwalają określić pierwszość liczby z dostatecznie dużym prawdopodobieństwem np: test pierwszości Millera-Rabina, test pierwszości Solovaya-Strassena.

Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.
Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – nauka o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.

Rozkład n! na czynniki pierwsze

Niech $\operatorname{ord}_p(n)$ oznacza wykładnik, z którym liczba pierwsza p występuje w rozkładzie liczby naturalnej n. Wtedy $\operatorname{ord}_p(n!) = \sum_{k=1}^{\infty}\left\lfloor \tfrac{n}{p^k}\right\rfloor$

gdzie $\lfloor x \rfloor$ jest jedyną liczbą całkowitą, spełniającą nierówność $x-1 < \lfloor x \rfloor \leqslant x$

dla dowolnego rzeczywistego x. Liczbę $\lfloor x \rfloor$ nazywamy częścią całkowitą liczby rzeczywistej x. Powyższa suma jest skończona, gdyż tylko skończona liczba jej składników jest różna od 0 – mianowicie pierwsze $\left\lfloor \tfrac{\ln n}{\ln p}\right\rfloor$ wyrazów.

Literatura: na przykład – rozdział 7.0; – rozdział 6.3, Twierdzenie 6.9.

Rozkład środkowego współczynnika dwumianowego

Zbadajmy $o_p(n) := \operatorname{ord}_p \binom{2n}{n}$ . Oczywiście $o_p(n) = 1$ , gdy liczba pierwsza $p$ należy do przedziału $n < p \leqslant 2n$ . Ogólnie

Ciąg arytmetyczny – ciąg liczbowy, w którym każdy wyraz można otrzymać dodając wyraz bezpośrednio go poprzedzający oraz ustaloną liczbę, zwaną różnicą ciągu. Zwykle mówiąc o ciągu arytmetycznym zakładamy, iż jego wyrazy są liczbami rzeczywistymi, choć sporadycznie rozważa się również ciągi arytmetyczne o wyrazach zespolonych.
3 (trzy) – liczba naturalna następująca po 2 i poprzedzająca 4. 3 jest też cyfrą wykorzystywaną do zapisu liczb w różnych systemach, np. w ósemkowym, dziesiętnym i szesnastkowym systemie liczbowym. Cechą podzielności zapisanej w systemie dziesiętnym liczby przez 3 w systemie dziesiętnym jest podzielność sumy cyfr danej liczby przez 3, np.

$o_p(n) = \operatorname{ord}_p((2n)!) - 2\operatorname{ord}_p(n!)$

Ponieważ $0 \leqslant \lfloor 2x \rfloor - 2\lfloor x \rfloor \leqslant 1$

dla dowolnej liczby rzeczywistej $x$ , to ze wzoru na $\operatorname{ord}_p(n!)$ , z poprzedniego fragmentu, wynika, że $o_p(n) \leqslant \left\lfloor \tfrac{\ln (2n)}{\ln p}\right\rfloor$

Równość $p ^{(\ln x)/(\ln p)} = x$ pozwala powyższą nierówność wyrazić równoważnie jako $p^{o_p(n)} \leqslant 2n$

czyli

Twierdzenie Jeżeli $p^k | \binom{2n}{n}$ , to $p^k \leqslant 2n$ .

Prawdziwe jest także twierdzenie:

Twierdzenie Jeżeli $n > 2$ jest liczbą naturalną, oraz $p$ – liczbą pierwszą z przedziału $\tfrac{2}{3}n < p \leqslant n$ , to $p$ nie jest dzielnikiem współczynnika $\binom{2n}{n}$ .

Silnią liczby naturalnej n (w notacji matematycznej: n!, co czytamy „n silnia”) nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie n! wprowadził w 1808 roku Christian Kramp.
Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)