Test Aks i inne;

Archiwum kompendium.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 747 razy

Test Aks i inne;

Post autor: mol_ksiazkowy »

:arrow: :arrow: Def. \(\displaystyle{ p \in P}\) Zbiór liczb pierwszych \(\displaystyle{ p_1, p_2, ....., p_n}\), .... jest on nieskończony i oznaczać go będziemy przez P. Jeśli n jest pewną l. naturalną, to wtedy należy ona do P, gdy ma tylko dwa dzielniki: 1 i n, i żadnych innych. :arrow: Definicja jest prosta i wydaje się, że nic tu trudnego, ale........ Już dawno wiedziano, że liczb pierwszych jest nieskończenie wiele*. -jak już było mowa, Liczbę większą od jedynki, która nie jest podzielna przez żadną liczbę od niej mniejszą i różną od jedynki, nazywamy liczbą pierwszą. Liczby te są ważne z tego powodu, że stanowią "cegiełki " z których zbudowane są wszystkie liczby naturalne za pomocą mnożenia. - Warto tu przytoczyć jak tego dowodził*:

:arrow: Dowód nie wprost: Euklides Przypuśćmy, że istnieje tylko skończona ilość liczb pierwszych : \(\displaystyle{ p_1, p_2, ....., p_n}\) . Niech M = \(\displaystyle{ p_1*p_2.....*p_n + 1}\) tj. liczba M jest iloczynem wszystkich tych liczb powiększonym o jeden. M jest większa od od każdej z tych liczb \(\displaystyle{ p1, p_2, ....., p_n}\). A więc nie jest liczbą pierwszą. Musi mieć jednak pewien dzielnik pierwszy, powiedzmy \(\displaystyle{ p}\). Ale nie jest to możliwe, gdyż M nie dzieli się przez żadną z tych liczb \(\displaystyle{ p_j}\). Ta sprzeczność kończy dowód !


Teoria liczb zajmuje sie m.in badaniem rozmieszczenia l.p. w zb l. naturalnych, a także innymi dylematami (np. hipotezą Goldbacha, iz każda l. naturalna >5 jest sumą trzech liczb pierwszych.....), bada się też różnice między kolejnymi l. pierwszymi...i wiemy iż : :arrow:
\(\displaystyle{ sup \ (p_{n+1}-p_n) =+\infty}\) , tj istnieją dowolnie długie skończone ciągi kolejnych l. naturalnych, nie zawierające żadnej l. pierwszej.-choć nie wiadomo, czy dla każdej l. parzystej \(\displaystyle{ 2k}\) istnieje takie n, że \(\displaystyle{ 2k=p_{n+1}-p_n}\) Wartosc liczby a= \(\displaystyle{ lim \ inf (p_{n+1}-p_n)}\) nie jest znana do dzis (2000 r.) Nie widomo czy granica ta jest skończona, choć przypuszcza się, że \(\displaystyle{ a=2}\), ale znany jest dowód, iż \(\displaystyle{ p_{n+1} \leq 2p_n}\). :arrow: postulat Bertranda. Nie wiadomo, czy dla dostatecznie dużych n jest :arrow: \(\displaystyle{ p_{n+1}-p_n \leq \sqrt{p_n}}\), ani tym bardziej, czy istnieje taka stała \(\displaystyle{ c>0}\), że \(\displaystyle{ p_{n+1}-p_n \leq c (log (p_n))^2}\) :arrow: hipoteza Cramera. :arrow:
Nietrudno i pokażac, że \(\displaystyle{ \ inf_{n \in N} (\sqrt{p_{n+1}}-\sqrt{p_n)}=0}\), a sądzi się iż nawet mocniej: tj ze :arrow: :arrow: :!: \(\displaystyle{ lim_{n \to \infty} (\sqrt{p_{n+1}}-\sqrt{p_n)}=0}\), itd. Otwartą jest takze tzw. hipoteza Schinzla. itd *

Kluczowe dowody nt l. pierwszych uzyskano dzieki metodom analitycznym- głównie w oparciu o własności, tzw. funkcji dzeta Riemanna i jej uogólnień. Całkiem inaczej wykazano, że ..istnieje wielomian o współcz. całkowitych zależny od 21 zmiennych stopnia 21, którego wszystkie dodatnie wartości są l.pierwszymi i wszystkie l. pierwsze mogą być otrzymane za pomocą tego wielomianu (nie istnieje taki wielomian zależny tylko od jednej zmiennej).
Znany jest wynik, że szereg \(\displaystyle{ \sum_{n=1}^{\infty} \frac{1}{p_n}=+\infty}\). A także zbiór l. pierwszych P ma gęstość naturalną równą 0, piszemy \(\displaystyle{ gn(P)=0}\). Uwaga: Mówimy, że gdy \(\displaystyle{ A \subset N}\) i A(n) to liczba tych elementów zbioru A, które są mniejsze lub równe od n. Gn istnieje tylko dla niektórych zbiorów A, ale o ile istnieje , to \(\displaystyle{ 0 \leq gn(A) \leq 1}\), ale gn nie jest miarą, bo nie jest przeliczalnie -a jedynie skończenie - addytywna, i monotoniczna :arrow:
\(\displaystyle{ gn(A)= \lim_{n \to \infty} \frac{A(n)}{n}}\)

:arrow: tw. Dirichleta -1837 r. :arrow: w każdym ciągu arytmetycznym, którego pierwszy wyraz i róznica są względnie pierwszymi l naturalnym, istnieje nieskończenie wiele l. pierwszych.
Tw Fermat Każda l. pierwsza postaci 4k+1 jest sumą kwadratów dwóch liczb całkowitych. Liczby pierwsze postaci 4k+3 takiego przedstawienia nie mają....


:!: :arrow: Sprawdzenie, czy dana liczba \(\displaystyle{ n}\) jest pierwszą, jet dla dużych n zadaniem trudnym. Służą do tego testy pierwszości, tj. kryteria, które w skończonej liczbie króków pozwalają stwierdzić, czy \(\displaystyle{ n}\) jest l. pierwszą (testy deterministyczne) czy też określić prawdopodobieństwo, że \(\displaystyle{ n}\) jest l. pierwszą (testy probabilistyczne.) Dla stosunkowo małych n użyć można klasycznych metod (np. sita Eratostenesa, czy cech podzielności...etc)

:arrow: Testy deterministyczne
:arrow: 1. Najprostszy test polega na dzieleniu n przez kolejne liczby naturalne mniejsze niż \(\displaystyle{ \sqrt{n}}\). Jeżeli żaden z ilorazów nie jest l. całkowitą, to n jest l. pierwszą. Ze względu na dużą złożoność obliczeniową test ten nadaje się dla stosunkowo małych n.
:arrow: 2. Test oparty na małym tw. Fermata: dla wybranej l. naturalnej \(\displaystyle{ a}\) względnie pierwszej z n, sprawdza się, czy \(\displaystyle{ a^{n-1} \equiv 1 \ (mod \ n)}\). Jeśli tak nie jest, to n jest l. złozoną. A gdy kongruencja jest spełniona, to test nie daje rozstrzygnięcia. Nazywa się ja wtedy pseudopierwszą przy podstawie a. Test nalezy powtórzyć z inną liczbą a. Ale nawet przy nieskończonej liczbie prób nie można zagwarantować sukcesu tej metody, gdyż istnieją l. złożone będące l. pseudopierwszymi przy każdej podstawie \(\displaystyle{ a \geq 1}\) :arrow: l. Carmichaela.


TEST AKS
Autorzy testu: Manindra Agrawal i Neraj Kayal i Nitin Saxen z Politechniki w Kanpur (Indie), 2002 r. Algorytm jest dość prosty , zawiera trzy etapy, o wiele trudniej pokazać jego poprawność, Istotnie nowym pomysłem w alg AKS jest Krok 3. Niestety trudno to zilustorwać na prostym przykłądzie, bo dla zbadania czy "mała" liczba , np mniejsza od \(\displaystyle{ 10^8}\) jest pierwsza wystarczy zastosować tylko dwa pierwsze kroki tego algorytmu. Algorytm działa w czasie \(\displaystyle{ O(log(n))}\).
opr wg art prof J. Browkina
Krok 1
Badamy, czy istnieją takie l. naturalne \(\displaystyle{ r \geq 2 \ , s \geq 2}\), że \(\displaystyle{ n=r^s}\), Jeśli tak, to n jest złożona, jeśli nie, to przechodzimy do następnego kroku.

Krok 2
Bierzemy liczbę \(\displaystyle{ r=2}\) i badamy, czy r dzieli n. Jeśli tak, to n jest l. złozoną, gdy r jest mniejsze od n , i jest l. pierwszą, gdy r=n.
Jeśli zaś nie, to badamy, czy:
1) liczba r-1 ma "duży" dzielnik pierwszy q, tzn. t. że \(\displaystyle{ q > 4\sqrt{r}log(n)}\)
2) liczba \(\displaystyle{ n^{\frac{r-1}{q}}-1}\) jest podzielna przez \(\displaystyle{ r}\)
Jeśli 1) lub 2) nie zachodzi, to jako r bierzemy następną l. pierwszą i postępujemy analogicznie.

Krok 3
Mamy liczbę pierwszą r, spełniającą warunki 1) i 2). Dla każdego a, gdzie \(\displaystyle{ 1 q a q 2\sqrt{r}log(n)}\) , dzielimy wielomian
\(\displaystyle{ (X-a)^n- X^n -a}\) przez \(\displaystyle{ X^r-1}\)
Jeżeli za każdym razem reszta z tego dzielenia jest wielomianem o wszystkich współczynnikach podzielnych przez n, to liczba n jest pierwsza. W przeciwnym razie jest ona złożona.



Testy probabilistyczne
Test Solovaya-Strassena polega na losowym wyborze \(\displaystyle{ k}\) liczb naturalnych b wzgl. pierwszych z n, \(\displaystyle{ 0 1}\) \(\displaystyle{ Aln(n) q \frac{p_n}{n} q Bln(n)}\)
I wreszcie z tegoż łatwy zwiazek między l. pierwszymi a liczba \(\displaystyle{ e}\)
\(\displaystyle{ \lim_{n \to } \sqrt[p_n]{p_1...p_n}=e}\)

Duże l. pierwsze -tabela, wg
liczba pierwsza, liczba jej cyfr, Rok odkrycia, Autor:
\(\displaystyle{ 2^{127} -1 \ *, \ \ 39, \ \ 1876, \ \ Lucas}\)
\(\displaystyle{ \frac{1}{17}(2^{148} +1), \ \ 44, \ \ 1951, \ \ Ferrier}\)
\(\displaystyle{ 180(2^{127} -1)^2 +1, \ \ 79, \ \ 1951, \ \ Miller, \ Wheeler}\)
\(\displaystyle{ 2^{2281}-1, \ \ 687, \ \ 1951, \ \ Lehmerer \ Robinson}\)
\(\displaystyle{ 2^{216091}-1, \ \ 65050, \ \ 1985, \ \ Slowinski}\)
\(\displaystyle{ 2^{1257787}-1, \ \ 378632, \ \ 1996, \ \ Slowinski, \ Cage}\)


* oznacza, że daną l. pierwszą znaleziono bez pomocy komputera

Literatura:
W. Sierpiński - Co wiemy, a czego nie wiemy o licznach pierwszych?!
...................... - Arytmetyka teoretyczna
Aigner, Ziegler, Dowody z księgi
Paulo Ribenboim, Wielkie twierdzenie Fermata dla laików
i.... Mała księga wielkich liczb pierwszych.
Conway J.H., Księga liczb

Linki z forum:
Kółko matematyczne � Schemat pierwszości, autor: polskimisiek
Dyskusje o matematyce � Wzór na liczbę pierwszą, autor: robomanus
Kompendium 2+2 � Kongruencja, autor: grandslam

Indian Institute of Technology Kanpur,
Test Lukasa Lehmera

Twin Primes http://www.utm.edu/research/primes/list ... /twin.html
http://www.cmmsigma.eu/do_pobrania/matematyka.html
PL wikipedia link [url=http://pl.wikipedia.org/wiki/Liczby_pierwsze]Liczby pierwsze[/url]
[url=http://en.wikipedia.org/wiki/Primality_test]Primality test[/url]
http://jknow.republika.pl/pierwsze/pierwsze.html
Zablokowany