Kiedy test pierwotności AKS jest rzeczywiście szybszy niż inne testy?

Próbuję dowiedzieć się, jak należy interpretować test pierwotności AKS, gdy się o nim dowiem, np. Następstwo dla udowodnienia, że ​​PRIMES ⊆ P, lub faktycznie praktyczny algorytm do testowania pierwotności na komputerach.

Test ma wielomianowy czas działania, ale z wysokim stopniem i możliwymi wysokimi stałymi. A więc w praktyce, w którym momencie przewyższa inne testy pierwotności? Tutaj jest liczbą cyfr liczby pierwszej, a „przekroczenie” odnosi się do przybliżonego czasu wykonywania testów na typowych architekturach komputerowych.$n$$n$

Interesują mnie algorytmy funkcjonalnie porównywalne, czyli deterministyczne, które nie wymagają domysłów do poprawności.

Ponadto, czy stosowanie takiego testu w porównaniu do innych jest praktyczne, biorąc pod uwagę wymagania dotyczące pamięci testu?

Szybka odpowiedź: nigdy, ze względów praktycznych. Obecnie nie ma praktycznego zastosowania.

Najpierw oddzielmy „praktyczne” testowanie złożoności od dowodów pierwotności. Ten pierwszy jest wystarczający do prawie wszystkich celów, chociaż istnieją różne poziomy testów, które ludzie uważają za odpowiednie. W przypadku liczb poniżej 2 ^ 64 nie więcej niż 7 testów Millera-Rabina lub jeden test BPSW jest wymagany dla odpowiedzi deterministycznej. Będzie to znacznie szybsze niż AKS i tak samo poprawne we wszystkich przypadkach. Dla liczb powyżej 2 ^ 64, BPSW jest dobrym wyborem, z kilkoma dodatkowymi losowymi testami Millera-Rabina, dodającymi pewnej pewności przy bardzo niskich kosztach. Prawie wszystkie metody sprawdzania zaczną (lub powinny) od takiego testu, ponieważ jest tani i oznacza, że ​​wykonujemy ciężką pracę tylko na liczbach, które prawie na pewno są liczbą pierwszą.

Przechodząc do dowodów. W każdym przypadku wynikowy dowód nie wymaga żadnych przypuszczeń, więc można je funkcjonalnie porównać. „Gotcha” APR-CL polega na tym, że nie jest ona dość wielomianowa, a „gotcha” ECPP / fastECPP polega na tym, że mogą istnieć liczby, które zajmują więcej niż oczekiwano.

Na wykresie widzimy dwie implementacje AKS typu open source - pierwsza pochodzi z wersji v6, druga zawiera ulepszenia Bernsteina i Volocha oraz miłą heurystykę r / s z Bornemann. Wykorzystują one binarną segmentację w GMP dla mnożników wielomianowych, więc są dość wydajne, a użycie pamięci nie jest problemem dla rozważanych tutaj rozmiarów. Tworzą ładne proste linie o nachyleniu ~ 6,4 na wykresie log-log, co jest świetne. Ale ekstrapolacja do 1000 cyfr dociera w przybliżonym czasie w setkach tysięcy do milionów lat, w porównaniu do kilku minut dla APR-CL i ECPP. Istnieją dalsze optymalizacje, które można wykonać na podstawie pracy Bernsteina z 2002 r., Ale nie sądzę, aby to istotnie zmieniło sytuację (choć dopóki nie zostanie to wdrożone, nie zostanie to udowodnione).

Ostatecznie AKS pokonuje podział próbny. Metoda twierdzenia BLS75 5 (np. Dowód n-1) wymaga częściowego faktorowania n-1. Działa to świetnie w małych rozmiarach, a także, gdy mamy szczęście i n-1 jest łatwe do uwzględnienia, ale w końcu utkniemy, gdy musimy wziąć pod uwagę dużą półpierwszą. Istnieją bardziej wydajne implementacje, ale tak naprawdę nie skaluje się do 100 cyfr niezależnie. Widzimy, że AKS przejdzie tę metodę. Więc jeśli zadałeś to pytanie w 1975 r. (I miałeś wtedy algorytm AKS), moglibyśmy obliczyć zwrotnicę, dla której AKS był najbardziej praktycznym algorytmem. Ale pod koniec lat 80. APR-CL i inne metody cyklotomiczne były poprawnym porównaniem, a do połowy lat 90. musielibyśmy uwzględnić ECPP.

Metody APR-CL i ECPP są implementacjami typu open source. Primo (darmowy, ale nie open source ECPP) będzie szybszy dla większych cyfr i jestem pewien, że ma ładniejszą krzywą (nie przeprowadziłem jeszcze nowego testu porównawczego). APR-CL nie jest wielomianem, ale wykładnik ma współczynnik który jak ktoś żartuje „idzie w nieskończoność, ale nigdy nie zaobserwowano tego”. To prowadzi nas do przekonania, że ​​teoretycznie linie nie przecinałyby się dla żadnej wartości n, w której AKS skończyłoby się przed wypaleniem naszego słońca. ECPP jest algorytmem Las Vegas, w którym, gdy otrzymamy odpowiedź, jest w 100% poprawna, oczekujemy wyniku w domniemanym (ECPP) lub$\log \log \log n$$O(\log^{5+\epsilon}(n))$$O(\log^{4+\epsilon}(n))$(„fastECPP”), ale mogą istnieć liczby, które zajmują więcej czasu. Oczekujemy więc, że standardowy AKS będzie zawsze wolniejszy niż ECPP dla prawie wszystkich liczb (z pewnością się tak wykazał dla liczb do 25 000 cyfr).

AKS może mieć więcej ulepszeń czekających na odkrycie, co czyni go praktycznym. Artykuł Bernsteina Quartic omawia oparty na AKS losowy algorytm , a artykuł Morain fastECPP odwołuje się do innych niedeterministycznych metod opartych na AKS. Jest to fundamentalna zmiana, ale pokazuje, w jaki sposób AKS otworzył nowe obszary badań. Jednak prawie 10 lat później nie widziałem, aby ktokolwiek używał tej metody (ani nawet jakichkolwiek implementacji). We wstępie pisze: „Czy czas dla nowego algorytmu jest mniejszy niż czas do znalezienia eliptycznego- certyfikaty krzywej? Moje obecne wrażenie jest takie, że odpowiedź brzmi „nie”, ale dalsze wyniki [...] mogą zmienić odpowiedź. ”$O(\log^{4+\epsilon}(n))$$(\lg n)^{4+o(1)}$$(\lg n)^{4+o(1)}$

Niektóre z tych algorytmów można łatwo zrównoleglać lub rozpowszechnić. AKS bardzo łatwo (każdy test jest niezależny). ECPP nie jest zbyt trudne. Nie jestem pewien co do APR-CL.

Metody ECPP i BLS75 tworzą certyfikaty, które można niezależnie i szybko zweryfikować. Jest to ogromna zaleta w stosunku do AKS i APR-CL, gdzie musimy tylko zaufać implementacji i komputerowi, który ją wyprodukował.

(Asymptotycznie) najbardziej wydajny deterministyczny algorytm testowania pierwotności wynika z Lenstry i Pomerance , działających w czasie . Jeśli wierzysz w rozszerzoną hipotezę Riemanna, algorytm Millera działa w czasie . Istnieje wiele innych deterministycznych algorytmów testowania pierwotności, na przykład praca Millera ma algorytm , a innym znanym algorytmem jest Adleman – Pomerance – Rumley, działający w czasie .$\tilde{O}(\log^6 n)$$\tilde{O}(\log^4 n)$$\tilde{O}(n^{1/7})$$O(\log n^{O(\log\log\log n)})$

W rzeczywistości nikt nie używa tych algorytmów, ponieważ są one zbyt wolne. Zamiast tego stosuje się algorytmy probabilistyczne, przede wszystkim Millera – Rabina, który jest modyfikacją wyżej wspomnianego algorytmu Millera (innym ważnym algorytmem jest Solovay – Strassen). Każda iteracja Millera – Rabina działa w czasie , a więc dla stałego prawdopodobieństwa błędu (powiedzmy ) cały algorytm działa w czasie , czyli znacznie szybciej niż Lenstra – Pomerance.$\tilde{O}(\log^2 n)$$2^{-80}$$\tilde{O}(\log^2 n)$

We wszystkich tych testach pamięć nie stanowi problemu.

W swoim komentarzu jbapple podnosi kwestię decydowania, który test pierwotności zastosować w praktyce. Jest to kwestia implementacji i testów porównawczych: zaimplementuj i zoptymalizuj kilka algorytmów oraz eksperymentalnie określ, który z nich jest najszybszy. Dla ciekawskich kodery PARI właśnie to zrobili i wymyślili funkcję deterministyczną isprimei funkcję probabilistyczną ispseudoprime, które można znaleźć tutaj . Zastosowany test probabilistyczny to Miller – Rabin. Ten deterministyczny to BPSW.

Oto więcej informacji od Dany Jacobsen :

Pari od wersji 2.3 używa isprime(x)testu APR-CL na próbę pierwszeństwa oraz prawdopodobnego testu BPSW (z „prawie bardzo silnym” testem Lucasa) dla ispseudoprime(x).

Biorą argumenty, które zmieniają zachowanie:

• isprime(x,0) (domyślnie.) Używa kombinacji (BPSW, szybkie Pocklington lub BLS75 twierdzenie 5, APR-CL).
• isprime(x,1) Wykorzystuje test Pocklington – Lehmera (prosty ).$n-1$

• isprime(x,2) Wykorzystuje APR-CL.

• ispseudoprime(x,0) (domyślnie.) Używa BPSW (MR z bazą 2, „prawie wyjątkowo silny” Lucas).

• ispseudoprime(x,k) (dla ) Czy testy MR z losowymi zasadami. RNG jest rozsiewany identycznie w każdym przebiegu Pari (więc sekwencja jest deterministyczna), ale nie jest ponownie przesyłany między wywołaniami, jak robi to GMP (losowe zasady GMP są w rzeczywistości tymi samymi zasadami przy każdym wywołaniu, więc jeśli jest błędne, to zawsze będzie błędne).$k\geq 1$$k$mpz_is_probab_prime_p(x,k)

Pari 2.1.7 zastosował znacznie gorszą konfigurację. isprime(x)były tylko testy MR (domyślnie 10), które doprowadziły do ​​zabawnych rzeczy, takich jak isprime(9)powracanie często. Użycie isprime(x,1)zrobiłoby dowód Pocklington, który był w porządku dla około 80 cyfr, a następnie stał się zbyt wolny, aby był ogólnie przydatny.

Ty też piszesz W rzeczywistości nikt nie używa tych algorytmów, ponieważ są one zbyt wolne. Wierzę, że wiem, co masz na myśli, ale myślę, że jest to zbyt silne, w zależności od odbiorców. AKS oczywiście jest niesamowicie powolny, ale APR-CL i ECPP są wystarczająco szybkie, że niektóre osoby z nich korzystają. Są przydatne do paranoicznego szyfrowania i przydatne dla osób wykonujących takie rzeczy primegapslub factordbtam, gdzie ma się wystarczająco dużo czasu, aby chcieć sprawdzonych liczb pierwszych.

[Mój komentarz na ten temat: szukając liczby pierwszej w określonym zakresie, stosujemy pewne podejście do przesiewania, a następnie stosunkowo szybkie testy probabilistyczne. Tylko wtedy, jeśli w ogóle, przeprowadzamy test deterministyczny.]

We wszystkich tych testach pamięć nie stanowi problemu. Jest to problem związany z AKS. Zobacz na przykład ten eprint . Niektóre z nich zależą od implementacji. Jeśli zaimplementujemy wideo, które numerphile nazywa AKS (co jest tak naprawdę uogólnieniem Małego Twierdzenia Fermata), użycie pamięci będzie bardzo wysokie. Użycie implementacji NTL algorytmu v1 lub v6, takiego jak przywoływany papier, spowoduje głupie duże ilości pamięci. Dobra implementacja GMP v6 nadal będzie wykorzystywać ~ 2 GB na 1024-bitową liczbę pierwszą, co jest bardzo dużopamięci dla tak małej liczby. Korzystanie z niektórych ulepszeń Bernsteina i segmentacji binarnej GMP prowadzi do znacznie lepszego wzrostu (np. ~ 120 MB dla 1024-bitów). Jest to wciąż znacznie większe niż wymagają inne metody i nic dziwnego, że będzie miliony razy wolniejsze niż APR-CL lub ECPP.

jest to skomplikowane pytanie ze względu na tak zwane „duże / stałe galaktyczne” związane z odmiennością wydajności różnych algorytmów. innymi słowy, związane z każdym innym algorytmem może ukryć bardzo duże stałe, tak że bardziej wydajny stosunku do innego oparty tylko na złożoności asymptotycznej / funkcyjnej ” kopie w ”dla bardzo dużego . rozumiem, że AKS jest „bardziej wydajny” (niż konkurencyjne algorytmy) tylko dla „znacznie większego ” poza zakresem obecnego praktycznego zastosowania (i że precyzyjneO ( f ( n ) ) O ( g ( n ) ) n n $O(f(n))$$O(f(n))$$O(g(n))$$n$$n$$n$ jest bardzo trudny do dokładnego obliczenia), ale teoretyczne ulepszenia implementacji algorytmu (aktywnie poszukiwane przez niektórych) mogą to zmienić w przyszłości.

widziałem ten ostatni artykuł na temat arxivu, który analizuje ten temat dogłębnie / szczegółowo, nie jestem pewien, co ludzie o nim myślą, nie słyszeli do tej pory reakcji, wydaje się być może tezą stworzoną przez studentów, ale być może jedną z najbardziej szczegółowych / kompleksowych analiz praktyczne wykorzystanie dostępnego algorytmu.

• Deterministyczne testowanie pierwotności - rozumienie algorytmu AKS Vijay Menon

• Potężne algorytmy zbyt złożone, aby wdrożyć tcs.se