Losowy test pierwszości (rozgrzewka)

Najpierw opracujmy koncepcję dla nowego typu algorytmów losowych, które przyjmują wartość wejściową n i jeśli to n jest liczbą pierwszą, to algorytm poda wynik „pierwsza” ze stuprocentową pewnością. Nigdy nie oznaczy jej jako liczby złożonej. Jeśli jednak n jest liczbą złożoną, istnieje małe prawdopodobieństwo błędu, że algorytm nazwie n liczbą pierwszą. Inaczej: z prawdopodobieństwem 1 minus ten margines błędu algorytm poprawnie zidentyfikuje liczbę jako złożoną. Najpierw - coś prostego. Z podzbioru liczb całkowitych do jakiejś granicy, wybierzemy liczbę i nazwiemy ją liczbą całkowitą n. Wprowadzimy ją do maszyny. Wcześniej, w metodzie próbnych dzieleń, przechodziliśmy przez wszystkie wartości od 1 do pierwiastka kwadratowego z n i sprawdzaliśmy, czy liczby te dzielą n. Dla oszczędności czasu idealnie byłoby sprawdzać same liczby pierwsze. Jeśli a dzieli n, to wiemy, że n jest liczbą złożoną, bo znaleźliśmy świadka złożoności. Jeśli nie – pewności nie ma. Cofamy się, powiększamy a i sprawdzamy znowu. Po wyczerpaniu wszystkich możliwości powiemy: „Tak, n jest liczbą pierwszą”. Bo nie znaleźliśmy dzielników. Ale bądźmy leniwi. Wybierzmy losowo kilka liczb całkowitych i zróbmy kilka testów podzielności. Można to uznać za pytania losowe. Ponieważ wiemy, że jakaś liczba n, jeśli jest złożona, to musi mieć jakieś dzielniki. Ma co najmniej jeden dzielnik. Niektóre liczby złożone mają ich wiele. Wybieramy losowo liczbę całkowitą a, z przedziału od 1 do pierwiastka z n. I już. Teraz sprawdzamy, czy a dzieli n. Jak przedtem: jeśli a dzieli n, to n na pewno jest liczbą złożoną. Mamy świadka. W przeciwnym razie… wiemy tylko, że n może być liczbą pierwszą. Dla bezpieczeństwa wygenerujmy jeszcze kilka losowych a i sprawdzajmy dalej. Może po przeprowadzeniu stu lub tysiąca prób powiemy: „Prawdopodobnie to liczba pierwsza”. Z jakąś dozą pewności. Powiedzmy, że 99,9%. To przypomina przykładową grę nt prawdopodobieństwa warunkowego. W najprostszej wersji próbowaliśmy zgadnąć, czy moneta była normalna, czy taka sama z obu stron. W tym przypadku orzeł jest jak znalezienie dzielnika. To świadek, że moneta jest dobra. Gdy wypadnie reszka, prosimy osobę o następny rzut. Tu, po pięciokrotnym wypadnięciu reszki, mamy więcej niż 90% pewności. Możemy przerwać i powiedzieć: „Sądzimy, że moneta ma dwie reszki”. Oto program, który napisałem, porównujący starą metodę próbnych dzieleń z tym nowym testem dzieleń losowych. Celowo używam programu „Trial division speed leader”, autorstwa Dino. W nagłówku zamieściłem link. Zauważcie zmienną liczbę prób. To liczba prób zgadywania losowego. Zaczniemy od małej liczby, np. 3. Przy małej wartości wejściowej, jeśli jest to liczba pierwsza, algorytm dzieleń losowych zawsze da wynik „pierwsza”. Ale gdy wartość wejściowa jest liczbą złożoną, to w losowych dzieleniach zdarzają się błędy i liczba jest niesłusznie oznaczana jako pierwsza. Możemy temu zaradzić, zwiększając liczbę prób. Wtedy prawdopodobieństwo błędu maleje. Widzimy, że wyniki mniej więcej się zgadzają. Gdy sprawdzam większe wartości wejściowe, błąd znów rośnie. Muszę więc odpowiednio zwiększyć liczbę testów losowych. A wtedy wyniki będą się ładnie zgadzać. Wydają się identyczne. Przy wielkich wartościach wejściowych potrzebuję tysięcy testów losowych, by metoda była rzetelna. Nie poprawiliśmy liczby potrzebnych kroków. Metoda próbnych dzieleń wydaje się lepsza. To dlatego, że procent błędów w teście dzieleń jest wysoki. Jesteśmy blisko. Mamy słuszny pomysł. Musimy użyć innego testu. Potrzebujemy równania, łatwego do rozwiązania, którym udowodnimy, czy liczba jest złożona. Musi przyjmować nie tylko wejściową liczbę całkowitą n, ale też losową liczbę całkowitą a i w ten sam sposób przeprowadzić test losowy.