[C/C++] Test rabina-millera

Czy ktoś z forumowiczów posiada działającą implementację tego algorytmu w C++?

Jeżeli chcesz, mogę podać ci słowny opis tego algorytmu - jeżeli znasz język C/C++, powinieneś być w stanie go zaimplementować ...

Czekam na odpowiedź i pozdrawiam

Nawe jak autor tego temaciku nie bedzie chcial to i tak ja chce wiec prosze o opis :) Z góry dziękuję

... podejrzewam że Dryo też się ucieszy na widok tego opisu (kiedyś już Tobie go obiecywałem, Dryo) ...

Aby nie było za wesoło, dwie uwagi:

1. Nie przedstawiam szczegółowego algorytmu (szerzej powiem o tym na koniec).
2. Nie udowadniam całkowitej bądź też częściowej poprawności (o tym może kiedyś w odległej przyszłości, sorry).

Zrobiło się smutno? To dobrze! to jest moja mała zemsta za wprowadzenie stopni, punktów i ocen na forum. (buachachacha)
:-8

Ponieważ temat jest ultra-ciekawy, spróbowałem (wyjątkowo) tak opisać problem, aby każdy mógł zrozumieć.

Test Rabina-Millera jest rozwiązaniem następującego problemu <font color="blue">decyzyjnego</span>:

Dane wejściowe:
liczba naturalna x.
Wynik:
tak - jeśli x jest liczbą pierwszą.
nie - w przeciwnym wypadku.

Inaczej mówiąc - zadajemy pytanie "czy x jest liczbą pierwszą ?".
Ponieważ odpowiedzią jest "tak" albo "nie", jest to problem <font color="blue">decyzyjny</span>.

Wpierw podam metodę rozwiązania, nie będącą jeszcze algorytmem:

[b]metoda test_rabina-millera[/b] (x)

1. Wybierz małą liczbę naturalną a!!

Dzieki chłopaki! Teraz na pewno poradzes obie z implementacją. Niestety zajme sie tym w okolicach soboty, bo tez mam teraz kolosy :-)

Zastanawia mnie wasze milczenie.
Może nie dostrzegliście piękna tej metody?

Oto bowiem mamy algorytm, który czasami się myli! (A dokładnie myli się średnio raz na cztery odpowiedzi "tak"). Zdumiewające!

... na marginesie- takie algorytmy, które udzielają odpowiedzi z pewnym prawdopodobieństwem błędu nazywamy algorytmami (metodami) <font color="blue">probabilistycznymi</span>.

szukając przyczyn waszego milczenia -
Zapytam wprost - czy podany algorytm jest czytelny ?

szukając przyczyn waszego milczenia -
Zapytam wprost - czy podany algorytm jest czytelny ?

Jak najbadziej czytelny.
Moje milczenie jest spowodowane inną rzeczą: też koła :(
Poza tym w nocy (godzina 4) to ja jeszcze śpię (szczerze mówiąc to mimo dzisiejszej serii kół to mi się bardzo dobrze spało do 10).

A wracając do algorytmu. Nie mogę za bardzo zrozumieć na jakiej podstawie wywnioskowano poprawność 75%. Domyślam się, że musi to być związane z podzielnością przez dwa oraz potęgami dwójki.
Skoro tak, to ciekaw jestem też jak taki algorytm działałby dla innych wartości np. 3, 5, 7 (czuję, że musiałby to być liczby pierwsze).
I jeszcze jedno. Jeżeli zakładamy wystarczającą 75% skuteczność, to dla jak dużych liczb ten algorytm byłby szybszy niż np. sito eratostenesa (lub inne znane algorytmy wyznaczania liczba pierwszych)?

W tej chwili mogę powiedzieć tylko tyle (zjada mnie brak czasu)

• dowód tego, że prawdopodobieństwo = 75% jest niebotycznie trudny i długi
• ten algorytm w porównaniu z sitem Eratostenesa "po prostu śmiga" hehe, praktycznie dla wszystkich wartości
  (no może za wyjątkiem tych wyjątkowo małych np. z przedziału 0-100, może 200).

Powiem więcej - gdybyś miał liczbę 30 cyfrową, i chciałbyś sprawdzić czy jest ona pierwsza - to za pomocą sita Eratostenesa mogłoby ci nie starczyć życia ... przy tak dużych liczbach (a naprawdę dużych liczb pierwszych używa się np. w kryptografii) metody probabilistyczne stają się po prostu koniecznością.

Zresztą nie tylko w tak skrajnych przypadkach zachodzi konieczność odwołania się do probabilistyki, mamy taką, na pozór niewinną sytuację:

Dane jest liceum, tzn. lista klas, lista nauczycieli, lista przedmiotów dla każdej z klas (i ilość godzin tygodniowo), preferencje i zastrzeżenia nauczycieli (Chemiczka nie może w poniedziałek ...), lista pomieszczeń.

Okazuje się, że dla typowego liceum możliwych do ułożenia planów lekcji jest zbyt wiele... trzeba odwołać się do metody probabilistycznej (przykład ten jest opisany w książce "algorytmika - rzecz o istocie informatyki"). Naszą odpowiedzią na ten problem, jest "ten plan lekcji jest optymalny" z pewnym prawdopodobieństwem. Aczkolwiek nawet jeśli nie jest on optymalny, to jest on na tyle niezły, że można go zaakceptować.