Test Millera-Rabina - Google

Test Millera-Rabina

Z Wikipedii

Skocz do: nawigacji, szukaj

Test Millera-Rabina jest testem pierwszości, czyli algorytmem określającym czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovay-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.

[edytuj] Algorytm i czas działania

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

Wejście: n > 1: nieparzysta liczba naturalna do przetestowania; k: parametr określający dokładność testu
Wyjście: złożona jeśli n jest złożona, prawdopodobnie pierwsza jeśli nie uda się stwierdzić złożoności
wylicz maksymalną potęgę dwójki dzielącą n − 1 i przedstaw n − 1 jako 2^s \cdot d;
powtórz k razy:
wybierz a losowo z przedziału [ 1, n - 1\ ]
jeśli a^d \ne 1\ \bmod\ n i a^{{2^r}d} \ne\ -1\ \bmod\ n dla wszystkich r z przedziału [ 0, s - 1\ ], zwróć wynik złożona
zwróć wynik prawdopodobnie pierwsza

Używając algorytmu szybkiego potęgowania możemy tę procedurę przeprowadzić w czasie O(k × log3 n), gdzie k jest liczbą różnych wartości a które testujemy.

[edytuj] Dokładność testu i wersje deterministyczne

Można pokazać że dla dowolnej złożonej nieparzystej liczby naturalnej n co najmniej 3/4 możliwych wartości a jest dobrymi świadkami złożoności tej liczby. Jeśli zatem przeprowadzamy k losowych prób, prawdopodobieństwo że określimy liczbę złożoną jako pierwszą wynosi co najwyżej 4 − k.

Istnieją deterministyczne wersje tego testu, jednak w ogólności są znacznie wolniejsze od niego i nie mają zastosowania praktycznego. Dla małych n udowodniono że można test przeprowadzić znacznie szybciej:

  • jeśli n < 4,759,123,141, wystarczy sprawdzić a = 2, 7 i 61,
  • jeśli n < 341,550,071,728,321, wystarczy sprawdzić a = 2, 3, 5, 7, 11, 13 i 17.

(inne tego typu kryteria opisane są w [1])

Daje to bardzo szybki deterministyczny test pierwszości dla liczb z tego zakresu, bez żadnych dodatkowych założeń. Udowodniono jednak że żaden skończony zbiór a nie wystarcza do testowania wszystkich liczb złożonych.

[edytuj] Link zewnętrzny


840 osób biegiem uczciło 64.rocznicę Powstania Warszawskiego
Dominika Stawczyk (KB Entre.pl Warszawa) i Bogusław Andrzejuk (Podlasie Białystok) zwyciężyli w XVIII Nocnym Biegu Powstania Warszawskiego, który miał rekordową obsadę. Dystans 10 km na terenie Akademii Wychowania Fizycznego Józefa Piłsudskiego pokonało aż 840 osób.
Polskie koszykarki przegrały z Francją
Reprezentacja Polski koszykarek przegrała z Francją 61:77 w drugim dniu międzynarodowego turnieju w Strasbourgu. W niedzielę, w ostatnim spotkaniu turnieju, Polki zmierzą się z Kanadą.
Heidfeld: w tym Robert jest ode mnie lepszy
- Obecny sezon jest dla nas niezwykle udany - mamy na koncie trzy znaczące osiągnięcia: pierwsze najszybsze okrążenie, pierwsze pole position i pierwsze zwycięstwo - powiedział w wywiadzie dla jednej z niemieckich gazet Nick Heidfeld, kierowca BMW Sauber.
ME w klasie 29-er: Polacy nie obronili tytułu
Brytyjczycy triumfowali w zakończonych w holenderskim Medemblik żeglarskich mistrzostwach Europy w klasie 29-er. Polska załoga Łukasz Przybytek (DKŻ Dobrzyń), Krzysztof Mongird (YK Stal Gdynia) zajęła ósme miejsce.
Lubelskie szczypiornistki mistrzyniami Europy szkół wyższych
Słuchaczki Wyższej Szkoły Społeczno-Przyrodniczej im. Wincentego Pola w Lublinie zostały mistrzyniami Europy szkół wyższych w piłce ręcznej.
Linki: Strona gwna