• 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.
    Przypisy[ | edytuj kod]
    1. Pomerance, C.; Selfridge, J. L. & Wagstaff, S. S., Jr. (1980), „The pseudoprimes to 25·10”, Mathematics of Computation 35 (151): 1003–1026, doi:10.2307/2006210.
    2. Jaeschke, Gerhard (1993), „On strong pseudoprimes to several bases”, Mathematics of Computation 61 (204): 915–926, doi:10.2307/2153262.
    3. Zhang, Zhenxiang & Tang, Min (2003), „Finding strong pseudoprimes to several bases. II”, Mathematics of Computation 72 (44): 2085–2097, doi:10.1090/S0025-5718-03-01545-X.

    Linki zewnętrzne[ | edytuj kod]

  • Eric W. Weisstein, Rabin-Miller Strong Pseudoprime Test, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12] (ang.).
  • 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).


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



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

    Warto wiedzieć że... beta

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

    Reklama

    Czas generowania strony: 1.153 sek.