Test Millera-Rabina

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Test Millera-Rabinatest pierwszości, czyli algorytm określający czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci.

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 (2011 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).

Algorytm i czas działania[ | edytuj kod]

Algorytm można zapisać w następującej postaci:

Wejście: nieparzysta liczba naturalna do przetestowania;

W informatyce, algorytm deterministyczny to algorytm, którego działanie jest całkowicie zdeterminowane przez warunki początkowe (wejście). Oznacza to, że kilkukrotne uruchomienie takiego algorytmu doprowadzi za każdym razem do takiego samego wyniku. Algorytmy deterministyczne stanowią główny obszar badań informatycznych i są najczęściej stosowane, ponieważ mogą być łatwo realizowane na współczesnych komputerach.Test pierwszości AKS (lub Test pierwszości Agrawal-Kayal-Saxena) jest deterministycznym testem pierwszości opublikowanym przez Manindra Agrawal, Neeraj Kayal i Nitin Saxena z IIT Kanpur 6 sierpnia 2002 roku w artykule zatytułowanym PRIMES is in P. Za jego opracowanie autorzy zostali uhonorowani Nagrodą Gödla w 2006 roku.
parametr określający dokładność testu.

Wyjście: złożona, jeśli jest złożona, prawdopodobnie pierwsza, jeśli nie uda się stwierdzić złożoności; wylicz maksymalną potęgę dwójki dzielącą i przedstaw jako powtórzyć razy: wybrać losowo ze zbioru jeśli i dla wszystkich ze zbioru zwróć wynik złożona. zwróć wynik prawdopodobnie pierwsza.

Używając algorytmu szybkiego potęgowania można tę procedurę przeprowadzić w czasie , gdzie jest liczbą różnych testowanych wartości

Test Solovaya-Strassena – test pierwszości opracowany przez Roberta M. Solovaya i Volkera Strassena. Jest to test probabilistyczny, który określa czy dana liczba jest liczbą złożoną czy prawdopodobnie pierwszą. W większości zastosowań test ten został wyparty przez test Millera-Rabina, lecz ma wysoki historyczny wkład w pokazaniu praktycznego wykorzystania RSA.Test pierwszości Fermata to probabilistyczny test umożliwiający sprawdzenie czy dana liczba jest złożona czy prawdopodobnie pierwsza. Jest jednym z najprostszych testów pierwszości i pomimo swoich wad jest wykorzystywany w algorytmach szyfrowania PGP.


Podstrony: 1 [2] [3] [4]




Warto wiedzieć że... beta

Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
Michael Oser Rabin (ur. 1931 we Wrocławiu, w ówczesnych Niemczech) - specjalista w dziedzinie kryptografii, laureat Nagrody Turinga w 1976, profesor nauk komputerowych w Harvard University.
Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa losowości. W praktyce oznacza to że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w "średnim przypadku", dzięki czemu złośliwe dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie.
Największy wspólny dzielnik – dla danych dwóch (lub więcej) liczb całkowitych największa liczba naturalna dzieląca każdą z nich. Pojęcie to ma wiele uogólnień, które przedstawiono w dalszej części artykułu.

Reklama