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

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?

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.

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 .

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 ¹²⁸ lub 2 ²⁵⁶ .

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

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.

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.

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.