• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Test Millera-Rabina



    Podstrony: [1] 2 [3] [4]
    Przeczytaj także...
    Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np.Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi Θ ( log ⁡ n ) {displaystyle Theta (log n)} , gdzie n oznacza wykładnik obliczanej potęgi.
    Dowód poprawności[ | edytuj kod]

    Poprawność tego algorytmu opiera się na następujących dwóch twierdzeniach:

    Twierdzenie 1[ | edytuj kod]

    Załóżmy, że jest liczbą pierwszą oraz że

    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).

    Niech dalej gdzie Wówczas albo albo istnieje dla którego .

    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.

    Liczbę która nie spełnia warunków powyższego twierdzenia nazywa się świadkiem złożoności liczby

    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.

    Twierdzenie 2[ | edytuj kod]

    Jeśli jest nieparzystą liczbą złożoną, to w zbiorze jest co najwyżej liczb niebędących świadkami jej złożoności.

    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.

    Przykład[ | edytuj kod]

    Należy określić, czy liczba jest pierwsza.

    Zapisując w postaci otrzymuje się oraz Następnie trzeba wybrać losowo liczbę Jeśli wylosowaną liczbą jest wtedy dla ze zbioru

    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.
  • i więc nierównoważne
  • Ponieważ to albo liczba 221 jest pierwsza, albo 174 jest fałszywym świadkiem dla 221. W tym przypadku następuje losowanie kolejnej wartość tym razem

  • i więc nierównoważne
  • A zatem 137 jest świadkiem złożoności 221, a 174 jest faktycznie fałszywym świadkiem. W tym przypadku test pozwala także dokonać rozkładu liczby: NWD(137−1, 221) = 17 221 / 17 = 13 zatem 221 = 17 · 13

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



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

    Reklama

    Czas generowania strony: 1.447 sek.