Zielony Smok

Jeszcze nie gotowe

Liczby pierwsze

Pojęcie liczby pierwszej

Liczby pierwsze znane są od wieków i przez wieki były przedmiotem dociekań wielu matematyków, co świadczy o skali problemu. Liczby pierwsze byłyby jednak do dziś matematyczną ciekawostką do dręczenia studentów matematyki, gdyby nie fakt, że znalazły intensywne zastosowanie w kryptografii.

Liczba pierwsza to taka liczba, która jest większa od 1 i jej jedynymi dzielnikami są 1 i ona sama.

2 jest liczbą pierwszą bo dzieli się się tylko przez 1 i 2. 3 jest liczbą pierwszą gdyż dzieli się jedynie przez 1 i 3. 4 nie jest liczbą pierwszą bo dzieli się przez 1,2 i 4.

Każda liczba naturalna większa od 2, która nie jest liczbą pierwszą jest liczbą złożoną.

0 nie jest ani liczbą pierwszą ani liczbą złożoną.

1 nie jest ani liczbą pierwszą ani liczbą złożoną.

Zbiór liczb pierwszych oznacza się znakiem ℙ.

Rozmieszczenie liczb pierwszych

A oto liczby pierwsze w zakresie od 2 do 1000:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 
563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 
653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 
761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 
991, 997

Jest ich 168.

Rozmieszczenie liczb pierwszych w zakresie od n = 1 do n = 10000

Jak do tej pory nikt nie znalazł wzoru określającego dokładne rozmieszczenie liczb pierwszych wśród liczb naturalnych.

Spirala Ulama

W 1963 r. Stanisław Ulam – polski matematyk – wypisał liczby pierwsze na spirali kwadratowej. Na niektórych przekątnych liczby pierwsze występują częściej niż na innych przekątnych. Fakt ten nie został do tej pory wyjaśniony.

Spirala Ulama

Spirala Archimedesa

Liczby od n = 2 do n = 1000 rozmieszczone na spirali Archimedesa.

Gęstość liczb pierwszych

Udział liczb pierwszych w zakresie od n = 1 do n = 100
000 000
Zakres: Liczb pierwszych % Narastająco %
1-10 4 40,00 4 40,00
10-100 21 21,00 25 25,00
100-1000 143 14,30 168 16,80
1000-10000 1061 10,61 1229 12,29
10000-100000 8363 8,36 9592 9,59
100000-1000000 68906 6,89 78498 7,85
1000000-10000000 586081 5,86 664579 6,65
10000000-100000000 5096876 5,10 5761455 5,76

Gęstość liczb pierwszych najczęściej określa się jako % stosunek liczb pierwszych do ogólnej liczby liczb w przedziałach zamkniętych od 2 do 2n, gdzie n jest kolejną liczbą naturalną.

Lp. Przedział Liczba liczb pierwszych %
a b
1 2 21 1 100.0
2 2 22 2 66.67
3 2 23 4 57.14
4 2 24 6 40.0
5 2 25 11 35.48
6 2 26 18 28.57
7 2 27 31 24.41
8 2 28 54 21.18
9 2 29 97 18.98
10 2 210 172 16.81
11 2 211 309 15.1
12 2 212 564 13.77
13 2 213 1028 12.55
14 2 214 1900 11.6
15 2 215 3512 10.72
16 2 216 6542 9.98
17 2 217 12251 9.35
18 2 218 23000 8.77
19 2 219 43390 8.28
20 2 220 82025 7.82
21 2 221 155611 7.42
22 2 222 295947 7.06
23 2 223 564163 6.73
24 2 224 1077871 6.42

Twierdzenie Gaussa i hipoteza Riemanna

Oba wzory dotyczą liczby π(n) liczb pierwszych w przedziale od [1, n].

Twierdzenie Gaussa

Gauss uważał, że liczba liczb pierwszych wynosi:

Wzór Gaussa na liczbę liczb pierwszych

gdzie Li(n) jest resztą logarytmu całkowego Wzór Gaussa

~ oznacza równość asymptotyczną oznaczającą, że:

Równośc asymptotyczna

Po rozwinięciu logarytmu całkowego w szereg otrzymujemy:

Rozwiniecie wzoru Gaussa

z którego do obliczeń przyjmuje się jedynie pierwszy człon, przy zachowaniu asymptotycznej równości:

Rozwinięcie wzoru Gaussa

Liczba liczba pierwszych mniejszych od 10000 powinna wynosić:

Liczba liczb pierwszych

Faktycznie n = 1229

Hipoteza Riemanna

Riemann twierdził, że liczba liczb pierwszych mniejszych od n wynosi:

Wzór Riemanna

gdzie:

ζ jest funkcją dzeta Riemanna.

Porównanie dokładności

Gdy dokonamy stosownych obliczeń:

Udział liczb pierwszych w zakresie od n = 1 do n = 100
000 000
Zakres do: Liczba liczb pierwszych
faktyczna wg Gaussa wg Riemanna
100 25 22 30
1000 168 145 178
10000 1229 1086 1246
100000 9592 8686 9630
1000000 78498 72382 78628
10000000 664579 620421 664918
100000000 5761455 5428681 5762209

Liczba liczb pierwszych

Liczb pierwszych jest nieskończenie wiele.

Generowanie liczb pierwszych

Brute force

Bierzemy kolejne liczby n. Każdą z n dzielimy przez wszystkie liczby od 2 do n – 1. Jeśli liczba dzieli się przez jakąkolwiek liczbę – nie jest liczbą pierwszą.

Sito Eratostenesa

Ze zbioru liczb naturalnych wybieramy przedział [2,n).

Pierwszą liczbą pierwszą jest 2. Wykreślamy wszystkie wielokrotności 2, a więc 4, 6, etc.

Przechodzimy do pierwszej niewykreślonej liczby, która jest liczbą pierwszą (nie została wykreślona). W naszym przykładzie jest to 3. Wykreślamy wszystkie wielokrotności tej liczby, np. 3, 9 (6 już zostało wykreślone bo jest podzielne przez 2).

Wykreślanie powtarzamy. Jeżeli wykreślana liczba jest większa od pierwiastka z n (u nas 11 bo pierwiastek a n = 10) – wykreślanie przerywamy.

Niewykreślone liczby z przedziału [2,n) to liczby pierwsze.

Animowane sito Ertostenesa

Sito Atkina

Jest bardzo dokładnie opisane na stronie Wikipedii pod hasłem “Sito Atkina”.

Porównanie sit

Algorytmy napisane były przeze mnie. Czas obejmuje czas wpisania liczb do tablicy i wykreślenia z niej liczb nie będących liczbami pierwszymi. Czas był obliczany na moim komputerze o dość przeciętnych parametrach:

Parametry komputera

Zakres liczb od 2 do n Czas w sek
Sito Eratostenesa Sito Atkina
1 000 000 0,011 0,020
10 000 000 0,098 0,085
100 000 000 1,807 1,324
1 000 000 000 21,655 15,585

Inne sita

Istnieje kilka innych sit, z których najpopularniejsze jest sito Sundarama.

Liczby pierwsze Mersenne’a

Liczby Mersenne’a to liczby typu:

Wzór na liczby Mersenne'a

Liczby pierwsze Mersenne’a to liczby Mersenne’a, które są zarazem liczbami pierwszymi.

Jeżeli liczba n w 2n jest złożona, to M(n) nigdy nie jest liczbą pierwszą.

Jeżeli liczba n w 2n jest pierwsza to M(n) może być liczbą pierwszą.

Aby przekonać się, że liczba jest pierwsza należy wykonać odpowiedni test pierwszości. Najczęściej używa się testu Lucasa – Lehmera.

Większość największych znanych liczb pierwszych to liczby Mersenne’a.

Znamy 49 liczb pierwszych Mersenne’a.

Miałem kłopoty z odpowiednim łamaniem liczb Mersenne’a w tabeli – prawdopodobnie jakieś interakcje z CSS. Dlatego tabelę umieściłem zewnętrznym pliku HTML.

Wzór Fermata i inne wzory

Liczby Fermata

Liczby pierwsze Fermata to liczby obliczane według wzoru:

Liczby pierwsze Fermata

które są pierwsze.

Na razie znamy 4 liczby Fermata:

Liczba Fermata

Liczba Fermata

Liczba Fermata

Liczba Fermata

Niestety liczba F5:

Błedna liczba Fermata

nie jest liczbą pierwszą podobnie jak F6.

n2 – n + 41

Dla liczb od n = 1 do n = 40 wyrażenie daje liczby pierwsze. Natomiast dla n = 41 otrzymujemy liczbę złożoną (412)

Liczby pierwsze Eulera

Są to liczby postaci:

Liczby pierwsze Eulera

Wzór generuje liczby pierwsze od n = 1 do n = 79. Zawodzi niestety przy n = 80

Specjalne liczby pierwsze

Liczby pierwsze bliźniacze

Liczby bliźniacze to dwie liczby pierwsze różniące się o 2.

  • (3, 5)
  • (5, 7)
  • (11, 13)
  • (17, 19)
  • (29, 31)
  • (41, 43)
  • (59, 61)
  • (71, 73)
  • (1619, 1621)

Wszystkie liczby bliźniacze od 2 do 100000:

Liczby pierwsze czworacze

Liczby czworacze to cztery liczby pierwsze różniące się od p o 2, 6 i 8, czyli równe p, p+ 2, p+6, p + 8:

  • (5, 7, 11, 13)
  • (101, 103, 107, 109)
  • (821, 823, 827, 829)

Wszystkie liczby czworacze od 2 do 100000:

Liczby pierwsze izolowane

Liczba pierwsza p jest izolowana, jeśli najbliższa liczba pierwsza różni się od niej co najmniej o 4.

  • 89, 157, 173

Wszystkie liczby izolowane od 2 do 1000:

Liczby pierwsze Sophie Germain

Liczba pierwsza jest liczbą Sophie Germain, jeśli liczba 2p+1 także jest liczbą pierwszą.

  • 2 (3)
  • 3 (7)
  • 5 (11)
  • 11 (23)
  • 23 (47)
  • 29 (59)
  • 41 (83)
  • 53 (107)
  • 83 (167)

Wszystkie liczby Sophie Germain od 2 do 10000:

Liczby pierwsze lustrzane

Liczby pierwsze lustrzane to dwie liczy, z których druga ma odwrotną kolejność cyfr dziesiętnych niż pierwsza.

  • 13 i 31
  • 17 i 71
  • 37 i 73
  • 79 i 97
  • 107 i 701

Wszystkie liczby lustrzane od 1 do 10000:

Liczby palindromiczne

Są to liczby, które po zapisaniu ich cyfr dziesiętnych w odwrotnej kolejności pozostają tymi samymi liczbami

  • 11
  • 101
  • 131
  • 191
  • 929

Wszystkie liczby palindromiczne od 1 do 100000:

Największe liczby pierwsze

Największą znaną liczbą pierwszą sprzed epoki komputerów była 44-cyfrowa liczba Ferriera Duża liczba pierwsza = 20988936657440586486151264256610222593863921

Liczba ma 44 cyfry.

Największą znaną liczbą pierwszą, która nie jest liczbą Mersenne’a jest:

Duża liczba pierwsza

W zapisie 10-nym liczy 3918990 (2177 stron maszynopisu). Jest 11 na liście największych liczb pierwszych.

Dziesięć największych znanych cyfr to liczby pierwsze Mersenne’a (stan na styczeń 2013)

Poprzednią największą znaną liczbą pierwszą to 48 liczba Mersenne’a:

48 liczba Mersenne'a

Składa się z 17425170 cyfr dziesiętnych (9681 stron maszynopisu). Została odkryta 25 stycznia 1013 r.

Największą znaną liczbą pierwszą jest 49 liczba Mersenne’a znaleziona przez Curtisa Coopera z Uniwersytetu w Missouri:

49 liczba Mersenne'a

Składa się z 22 338 618 cyfr (12 411 stron maszynopisu). Doniesienie pojawiło się w dn. 21.01.2016.

Testy pierwszości

Testy pierwszości to testy pozwalające określić czy dana liczba jest liczbą pierwszą.

Dzielenie

Oczywiście najprostszą metodą jest próba dzielenia liczby. Metoda zawodzi przy dużych liczbach, ze względu na czas potrzebny do wykonania dzieleń.

Sito Erastotenesa i Atkina

Jeśli liczba pozostanie na sicie – jest liczbą pierwszą. Ta metoda zawodzi przy bardzo dużych n, ale ze względu na prostotę jest często wykorzystywana.

Test Millera – Rabina

Przy dużych liczbach praktyczne zastosowanie mają testy probabilistyczne, które pozwalają, z dostatecznie dużym prawdopodobieństwem, określić czy liczba jest liczbą pierwszą.

Do badania pierwszości dużych liczb najczęściej stosuje się test Millera – Rabina., który w odpowiedzi daje true albo false. False oznacza, że liczba z całą pewnością nie jest pierwsza. Odpowiedź true znaczy, że liczba ta jest z dużym prawdopodobieństwem liczbą pierwszą. Im większa liczba iteracji algorytmu tym większe prawdopodobieństwo, że badana liczba jest liczbą pierwszą.

Test Millera – Rabina wykorzystuje arytmetykę modularną.

Postępowanie

  1. Wybierz k ≥ małych liczb a < N i względnie pierwszych z N.
  2. Zapisz N – 1 w postaci 2sd
  3. Sprawdzaj, czy zachodzi któryś z warunków
    • Warunek pierwszości
    • Warunek pierwszości
  4. Jeśli, dla pewnego a nie zaszedł któryś z powyższych warunków, to N jest złożone. W przeciwnym
    wypadku uważaj N za pierwsze, z prawdopodobieństwem błędu (1/4)k

Test nie daje pewności, że badana liczba jest pierwsza, ale przy odpowiednio dużym k można się do pewności zbliżyć.

Przykład

Sprawdzamy, czy liczba 577 jest pierwsza.

Mamy Liczba do zbadania

Przyjmujemy a=2

Mamy Badanie liczby pierwszej

Badanie liczby pierwszej dla k = 1

Badanie liczby pierwszej dla k = 2

a = 2 spełnia więc jeden z warunków

Przyjmujemy teraz a = 3

Badanie liczby pierwszej

Liczba a = 3 również spełnia warunki testu. Zatem z prawdopodobieństwem:

Badanie liczby pierwszej

577 jest liczbą pierwszą

Test Lucasa – Lehmera

Często używa się testu Lucasa – Lehmera, również opartego na arytmetyce modularnej.

Test służy do badania pierwszości liczb Mersenne’a.

Można wykazać, że la nieparzystych p liczba 2p – 1 jest liczbą pierwszą wtedy i tylko wtedy, gdy 2p – 1 dzieli S(p – 1). Funkcja S(k) jest określona rekurencyjnie jako:

S(1) = 4 oraz S(n+1) = S(n)2 – 2

Przykład

Badamy p = 5, 25 – 1 = 31

Badanie liczby pierwszej

A zatem 31 jest liczbą pierwszą.

Przykład

Badamy p = 9, 29 – 1 = 511

Badanie liczby pierwszej

A zatem 511 nie jest liczbą pierwszą.

Inne testy

Istnieje mnóstwo testów pierwszości, łatwych do znalezienia w Internecie.

Faktoryzacja

Każda liczba złożona większa od 2 może być przedstawiona w postaci iloczynu liczb pierwszych.

Np. liczba 100010001000 = 2*2*2*3*5*5*5*7*13*37*9901

Aby ułatwić odczytanie liczby powtarzające się liczby zapisujemy w postaci odpowiedniej potęgi tej liczby:

Np. liczba 100010001000 = 23*3*53*7*13*37*9901

Rozkład liczb od n = 2 do n = 1000 na czynniki pierwsze

Schemat algorytmu faktoryzacji:

Scheta algorytmu faktoryzacji

Ciekawe liczby pierwsze

Liczba 11111111111111111111111 (23 jedynki) też jest liczbą pierwszą.

Liczba 31415926535897932384626433832795028841 złożona z pierwszych 38 cyfr liczby π – jest liczbą pierwszą.

Liczba 73939133 jest liczbą pierwszą. Gdy odetniemy jej kolejno po 1 cyfrze z prawej strony:

  • 739391
  • 73939
  • 7393
  • 739
  • 73
  • 7

to każda z powstałych liczb jest liczbą pierwszą.

Czego nie wiadomo?

  • Formuła rozkładu liczb pierwszych wśród liczb naturalnych.
  • Czy dla każdego n > 0 w przedziale między n2, a (n + 1)2 istnieje liczba pierwsza?
  • Czy każda liczba parzysta jest sumą dwóch liczb pierwszych?
  • Czy istnieje nieskończenie wiele liczb pierwszych bliźniaczych, Fermata, Mersenne’a, Germain?
  • Czy istnieje nieskończenie wiele liczb pierwszych postaci n2 + 1?
  • Czy ciąg Fibonacciego zawiera nieskończenie wiele liczb pierwszych?

Zastosowania

Zastosowania praktyczne

Liczby pierwsze są stosowane głównie w kryptografii do tworzenia podpisów cyfrowych np. w algorytmach typu RSA. Trudność złamania szyfru i odgadnięcia klucza polega na trudności związanej z faktoryzacją liczby, która jest iloczynem 2 bardzo dużych liczb pierwszych.

Liczby pierwsze w naturze

Cykady z rodzaju Magicicada większość czasu spędzają w postaci larwalnej pod ziemią. Na wiosnę wychodzą z ziemi, przobrażają się, odlatują, rozmnażają, składają jaja zamykając w ten sposób cykl życiowy.

Istnieją gatunki, u których cykl życiowy jest wstrzymywany na 7, 13 albo nawet 17 lat, czyli larwy pojawiają się i przeobrażają jedynie co 7, 13 albo 17 lat.

Prawdopodobnie jest to zabezpieczenie przed koewolucją drapieżców i pasożytów, zjadających lub atakujących cykady. Drapieżce i pasożyty mają problemy z odpowiednią synchronizacją swoich cykli życiowych z cyklem życia cykad. Im okres cyklu jednego gatunku jest większą liczbą pierwszą tym trudniejsza synchronizacja.