Jaki jest możliwy przypadek użycia .isProbablePrime () BigIntegera?

84

MetodaBigInteger.isProbablePrime() jest dość dziwna; na podstawie dokumentacji pokaże, czy liczba jest liczbą pierwszą z prawdopodobieństwem 1 - 1 / 2^arg, gdzie argjest argumentem całkowitym.

W JDK jest obecny od dość dawna, więc oznacza to, że musi mieć zastosowania. Moja ograniczona wiedza z zakresu informatyki i algorytmów (i matematyki) mówi mi, że nie ma sensu wiedzieć, czy liczba jest „prawdopodobnie” liczbą pierwszą, ale nie dokładnie.

Jaki jest więc możliwy scenariusz, w którym chciałoby się użyć tej metody? Kryptografia?

fge
źródło
6
Również test pierwszości Millera-Rabina . Główną zaletą jest szybkość . Np. Jeśli chcesz sprawdzić czynniki, możesz zrobić taki test, aby przyspieszyć proces faktoringu. Część „prawdopodobnie” można utrzymywać dość nisko i jest to przydatne w praktyce. Ale zgadzam się, że jest trochę chwiejny i dziwny, jak pływaki.
keyser
2
@ maxx777 to jest dane - proszę o rzeczywisty przypadek użycia
fge
4
Naprawdę chciałbym, aby ci, którzy przegrywali, wyjaśnili powody negatywnych głosów, proszę
fge
17
„Jest obecny w JDK od dłuższego czasu, więc oznacza to, że musi mieć zastosowania”. - lub został dodany z bezużytecznego powodu, a następnie nie został usunięty, ponieważ nic nie jest usuwane.
user253751

Odpowiedzi:

67

Tak, ta metoda może być używana w kryptografii. Szyfrowanie RSA polega na znajdowaniu ogromnych liczb pierwszych, czasami rzędu 1024 bitów (około 300 cyfr). Bezpieczeństwo RSA zależy od tego, że faktoryzacja liczby składającej się z 2 takich liczb pierwszych pomnożonych razem jest niezwykle trudna i czasochłonna. Ale żeby zadziałało, muszą być pierwsi.

Okazuje się, że udowodnienie tych liczb pierwszych jest również trudne. Ale test pierwszości Millera-Rabina , jeden z testów pierwszości stosowanych przez isProbablePrime, albo wykrywa, że ​​liczba jest złożona, albo nie daje żadnych wniosków. Przeprowadzenie tego testu npozwala stwierdzić, że istnieje prawdopodobieństwo 1 do 2 n, że ta liczba jest naprawdę złożona. Liczenie 100czasów daje akceptowalne ryzyko 1 na 2 100, że ta liczba jest złożona.

rgettman
źródło
3
@ Mr 777 Widziałem Rabina-Millera raz lub dwa, ale Millera-Rabina dziesiątki razy. Nie jestem jednak pewien, czy istnieje oficjalna nazwa.
keyser
3
@ Mr.777 Strona Wikipedii, do której odsyłam powyżej, podaje najpierw „Miller-Rabin”, ale uznaje obie nazwy: „Test pierwszości Millera – Rabina lub Test pierwszości Rabina – Millera”.
rgettman,
5
Implementacja isProbablyPrimejest (o ile wiem) w pełni deterministyczna. W jaki sposób przeprowadzanie testów npoprawiłoby szanse uzyskania prawidłowego wyniku? (Nawet gdyby był to element losowości, losowość wielu wywołań musiałaby być niezależna, aby wpływać na ryzyko w sposób, w jaki opisujesz.)
Ted Hopp,
11
@TedHopp Implementacja wykorzystuje generator losowy, a każda runda z nowymi liczbami losowymi daje 3/4 szansy na wykrycie złożonego. Domyślnym generatorem jest SecureRandom, z silnymi gwarancjami losowości.
ten inny facet
4
Może to być trudne, jednak pamiętaj, że PRIMES jest w P. Test AKS może być wolniejszy niż Miller-Rabin, ale nie ma między nimi wykładniczej różnicy ani wielomianu. Możesz użyć Millera-Rabina, aby znaleźć kilka prawdopodobnych liczb pierwszych i użyć AKS, aby zdecydowanie udowodnić, że są one liczbami pierwszymi.
Bakuriu,
20

Jeśli test powie ci, że liczba całkowita nie jest liczbą pierwszą , możesz z pewnością uwierzyć, że 100%.

To tylko druga strona pytania, jeśli test mówi ci, że liczba całkowita jest „prawdopodobną liczbą pierwszą”, możesz mieć wątpliwości. Powtórzenie testu z różnymi „zasadami” pozwala na zmniejszenie prawdopodobieństwa błędnego „imitowania” liczby pierwszej (będącej silną pseudopierwszą w odniesieniu do wielu zasad).

Przydatność testu polega na jego szybkości i prostocie. Niekoniecznie zadowalałby się status „prawdopodobnej liczby pierwszej” jako ostatecznej odpowiedzi, ale zdecydowanie można by uniknąć marnowania czasu na prawie wszystkie liczby złożone, stosując tę ​​procedurę przed wprowadzeniem wielkich dział testowania pierwszości .

Porównanie z trudnością faktoringu liczb całkowitych jest czymś w rodzaju czerwonego śledzia. Wiadomo, że prymat liczby całkowitej można określić w czasie wielomianowym i rzeczywiście istnieje dowód na to, że rozszerzenie testu Millera-Rabina na wystarczającą liczbę zasad jest ostateczne (w wykrywaniu liczb pierwszych, w przeciwieństwie do prawdopodobnych liczb pierwszych), ale to zakłada uogólnioną hipotezę Riemanna, więc nie jest tak pewna, jak (droższy) test pierwszości AKS .

twarda matematyka
źródło
4
Warto zauważyć, że AKS odkryto dopiero w sierpniu 2002 r., Podczas gdy ta metoda jest w JDK od lutego 2002 r.
James_pic
3
Nie, czekaj, to jest w JDK od lutego 1997 roku (patrzyłem na probablePrimemetodę, a nie isProbablePrimemetodę)
James_pic
1
Rzeczywiście, tytuł artykułu Agrawala, Kayala i Saxeny z 2002 r. „PRIMES jest w P” sygnalizuje pierwszy bezwarunkowy dowód złożoności wielomianu (w bitach o długości n ) dla deterministycznych (ogólnych liczb całkowitych) testów pierwszości. Miller (1975) wykazał, że zakładając GRH , prymat liczby całkowitej można testować deterministycznie w krokach proporcjonalnych do czwartej potęgi długości bitu, co jest znacznie lepszym wykładnikiem niż jest to obecnie znane dla AKS lub jego wariantów.
hardmath
Chociaż AKS jest asymptotycznie szybszy, metody takie jak ECPP byłyby znacznie bardziej wydajne w przypadku liczb pierwszych „kryptograficznych” lub „przemysłowych”.
Brett Hale
2
AKS jest niesamowicie powolny i nie będzie szybszy niż APR-CL dla dowolnej liczby obliczalnej w czasie skali geologicznej, znacznie mniej w skali ludzkiej. APR-CL i ECPP istniały już w 1997 roku. Jak wspomina Brett, ECPP to dobry wybór, jeśli chcemy dowodu. Wszystkie z nich są powolne w porównaniu z prawdopodobnymi metodami podstawowymi (np. MR, BPSW, Frobenius).
DanaJ
19

Standardowy przypadek użycia BigInteger.isProbablePrime(int)to kryptografia. W szczególności niektóre algorytmy kryptograficzne, takie jak RSA , wymagają losowo wybranych dużych liczb pierwszych. Jednak co ważne, te algorytmy nie wymagają, aby te liczby były gwarantowane jako pierwsze - po prostu muszą być liczbami pierwszymi z bardzo dużym prawdopodobieństwem.

Jak wysoko jest bardzo wysoko? Cóż, w aplikacji kryptograficznej zwykle dzwoniłoby się .isProbablePrime()z argumentem między 128 a 256. Zatem prawdopodobieństwo, że liczba inna niż pierwsza przejdzie taki test jest mniejsze niż jeden na 2 128 lub 2 256 .

Spójrzmy na to z perspektywy: gdybyś miał 10 miliardów komputerów, z których każdy generował 10 miliardów prawdopodobnych liczb pierwszych na sekundę (co oznaczałoby mniej niż jeden cykl zegara na liczbę na dowolnym nowoczesnym procesorze), a pierwotność tych liczb została przetestowana .isProbablePrime(128)na spodziewałby się, że jedna liczba inna niż pierwsza pojawi się raz na 100 miliardów lat .

To znaczy, że tak by było, gdyby te 10 miliardów komputerów mogło w jakiś sposób działać przez setki miliardów lat bez żadnych awarii sprzętu. W praktyce jednak, jest to dużo bardziej prawdopodobne w przypadku losowego promieniowania kosmicznego uderzyć komputer w odpowiednim czasie i miejscu, aby odwrócić wartości zwracanej z .isProbablePrime(128)z false na true, nie powodując żadnych innych efektów wykrywalne, niż jest to dla nie -liczba pierwsza, która faktycznie przejdzie probabilistyczny test pierwszości na tym poziomie pewności.

Oczywiście to samo ryzyko przypadkowych promieni kosmicznych i innych usterek sprzętowych dotyczy również deterministycznych testów pierwszości, takich jak AKS . Dlatego w praktyce nawet te testy mają (bardzo mały) podstawowy wskaźnik fałszywie pozytywnych wyników z powodu przypadkowych awarii sprzętu (nie wspominając o wszystkich innych możliwych źródłach błędów, takich jak błędy implementacji).

Ponieważ łatwo jest przesunąć wewnętrzny odsetek fałszywie dodatnich wyników testu pierwszości Millera – Rabina, stosowanego .isProbablePrime()znacznie poniżej tego wskaźnika podstawowego, po prostu powtarzając test dostatecznie wiele razy, a ponieważ, nawet powtarzany tak wiele razy, test Millera – Rabina jest nadal znacznie szybszy w praktyce niż najbardziej znane deterministyczne testy pierwszości, takie jak AKS, pozostaje standardowym testem pierwszości dla aplikacji kryptograficznych.

(Poza tym, nawet jeśli przypadkowo wybrałeś silną liczbę pseudopierwszą jako jeden z czynników twojego modułu RSA, generalnie nie doprowadziłoby to do katastrofalnej awarii. Zazwyczaj takie liczby pseudopierwsze byłyby iloczynami dwóch (lub rzadko więcej) liczb pierwszych w przybliżeniu połowę długości, co oznacza, że ​​otrzymasz klucz RSA o wielu liczbach pierwszych . Dopóki żaden z tych czynników nie będzie zbyt mały (a jeśli tak, to test pierwszości powinien je wychwycić), algorytm RSA będzie nadal działa dobrze, a klucz, chociaż nieco słabszy w przypadku niektórych typów ataków niż zwykłe klucze RSA o tej samej długości, powinien być wystarczająco bezpieczny, jeśli nie będziesz niepotrzebnie skąpić na długości klucza.)

Ilmari Karonen
źródło
Problem z usterką jest jednym z powodów, dla których AKS nie jest w rzeczywistości używany (drugą jest zadziwiająco niska prędkość), a ECPP jest bardziej powszechne. Jak zauważyłeś, błędy implementacji algorytmów są całkiem możliwe, więc posiadanie certyfikatu weryfikowanego niezależnym kodem jest pomocne.
DanaJ
8

Możliwym przypadkiem użycia jest testowanie pierwszości podanej liczby (w teście, który sam w sobie ma wiele zastosowań). isProbablePrimeAlgorytm będzie działał znacznie szybciej niż dokładnego algorytmu, więc jeżeli liczba awarii isProbablePrime, a następnie jeden nie musi iść na koszt prowadzenia droższej algorytmu.

Ted Hopp
źródło
Więc czy to ze względów praktycznych? A ze względu na fakt, że faktoryzacja podstawowa jest problemem NP?
fge
@fge - Tak, zaproponowany przeze mnie przypadek użycia dotyczy praktyczności. Nie wiem, czy to pomaga w rozkładaniu na czynniki pierwsze, co jest znacznie trudniejszym problemem niż testowanie pierwotności. W przypadku tego drugiego istnieje algorytm wielomianowy: test pierwszości AKS .
Ted Hopp,
5
@fge: Faktoryzacja jest rzeczywiście w NP, ale podejrzewam, że miałeś na myśli „NP-zupełny”, co nie jest znane. Wręcz przeciwnie, podejrzewa się, że nie jest to NP-trudne.
hmakholm zostawił Monikę w
6

Znalezienie prawdopodobnych liczb pierwszych jest ważnym problemem w kryptografii. Okazuje się, że rozsądną strategią znajdowania prawdopodobnej k-bitowej liczby pierwszej jest wielokrotne wybieranie losowej liczby k-bitowej i testowanie jej pod kątem prawdopodobnej pierwszości przy użyciu metody takiej jak isProbablePrime().

Dalsza dyskusja znajduje się w sekcji 4.4.1 podręcznika Handbook of Applied Cryptography .

Zobacz także O generowaniu prawdopodobnych liczb pierwszych przez wyszukiwanie przyrostowe Brandta i Damgårda.

NPE
źródło
5

Algorytmy, takie jak generowanie kluczy RSA, polegają na możliwości określenia, czy liczba jest liczbą pierwszą, czy nie.

Jednak w czasie, gdy isProbablePrimemetoda została dodana do JDK (luty 1997 r.), Nie było udowodnionego sposobu, aby w sposób deterministyczny zdecydować, czy liczba jest liczbą pierwszą w rozsądnym czasie. Najbardziej znanym podejściem w tamtym czasie był algorytm Millera-Rabina - algorytm probabilistyczny, który czasami dawał fałszywe alarmy (tj. Zgłaszał liczby niebędące liczbami pierwszymi jako liczby pierwsze), ale można go było dostroić w celu zmniejszenia prawdopodobieństwa fałszywych trafień kosztem niewielkich wzrostów czasu działania.

Od tego czasu odkryto algorytmy, które mogą deterministycznie decydować o tym, czy liczba jest odpowiednio szybko pierwsza, na przykład algorytm AKS, który został odkryty w sierpniu 2002 roku. Należy jednak zauważyć, że algorytmy te nadal nie są tak szybkie jak Miller-Rabin.

Być może lepszym pytaniem jest, dlaczego żadna isPrimemetoda nie została dodana do JDK od 2002 roku.

James_pic
źródło
Dzięki za historyczną perspektywę! Wygląda na to, że @immibis był na dobrej drodze ze swoim komentarzem na temat „w JDK, ale nigdy nie został usunięty”? :)
fge
1
Wiem, że Java nigdy nie usuwa rzeczy ze standardowej biblioteki, ale nie jestem pewien, czy usunęliby je, nawet gdyby mogli. W przypadku niektórych aplikacji posiadanie 99,999999999% pewności, że coś jest pierwsze, jest wystarczająco dobre i znacznie szybsze niż uzyskanie 100% pewności.
James_pic