Каков возможный вариант использования BigInteger .isProbablePrime ()?

84

МетодBigInteger.isProbablePrime() довольно странный; из документации это покажет, является ли число простым с вероятностью 1 - 1 / 2^arg, где arg- целочисленный аргумент.

Он присутствует в JDK довольно давно, значит, у него обязательно есть применение. Мои ограниченные знания в области информатики и алгоритмов (и математики) говорят мне, что на самом деле не имеет смысла знать, является ли число «вероятно» простым, но не совсем простым.

Итак, каков возможный сценарий, в котором можно было бы использовать этот метод? Криптография?

fge
источник
6
А также критерий простоты Миллера-Рабина . Главное преимущество - скорость . Например, если вы хотите проверить факторы, вы можете провести такой тест, чтобы ускорить процесс факторинга. Вы можете оставить его «вероятно» довольно низким, и это полезно на практике. Но согласен, что это немного шатко и странно, как поплавки.
keyser
2
@ maxx777 это данность - я прошу реальный вариант использования
fge
4
Мне бы очень хотелось, чтобы те, кто проголосовал против, объяснили причины таких голосов, пожалуйста
fge
17
«Он присутствует в JDK довольно долгое время, так что это означает, что он должен иметь применение». - или он был добавлен по бесполезной причине, а затем не удален, потому что ничего не удаляется.
user253751

Ответы:

67

Да, этот метод можно использовать в криптографии. Шифрование RSA включает обнаружение огромных простых чисел, иногда порядка 1024 бит (около 300 цифр). Безопасность RSA зависит от того факта, что разложение числа, состоящего из двух этих простых чисел, умноженных вместе, чрезвычайно сложно и требует много времени. Но чтобы это сработало, они должны быть первыми.

Оказывается, доказать простоту этих чисел тоже сложно. Но тест на простоту Миллера-Рабина , один из тестов на простоту, который использует автор isProbablePrime, либо обнаруживает составное число, либо не дает никаких выводов. Выполнение этого теста nпозволяет сделать вывод, что вероятность того, что это число действительно составное, составляет 1 из 2 n . Выполнение этого числа 100раз дает приемлемый риск 1 из 2 100, что это число является составным.

rgettman
источник
3
@ Mr.777 Я видел Рабина-Миллера пару раз, а Миллера-Рабина десятки раз. Я не уверен, есть ли официальное название.
keyser
3
@ Mr.777 На странице Википедии, на которую я ссылался выше, сначала указано «Миллер-Рабин», но признаются оба названия: «Тест простоты Миллера – Рабина или тест простоты Рабина – Миллера».
rgettman
5
Реализация isProbablyPrime(насколько я могу судить) полностью детерминирована. Как увеличение времени тестирования nповысит шансы на получение правильного результата? (Даже если бы это был элемент случайности, нужно было бы, чтобы случайность множественных вызовов была независимой, чтобы повлиять на риск так, как вы описываете.)
Тед Хопп
11
@TedHopp Реализация использует генератор случайных чисел, и каждый раунд с новыми случайными числами дает 3/4 шанс обнаружения составного элемента. Генератор по умолчанию - SecureRandom с надежными гарантиями случайности.
тот другой парень
4
Это может быть сложно, однако помните, что PRIMES находится в P. Тест AKS может быть медленнее, чем тест Миллера-Рабина, но между ними нет экспоненциальной разницы или полинома. Вы можете использовать Миллера-Рабина, чтобы найти кучу вероятных простых чисел, и использовать AKS, чтобы определенно доказать, что они являются простыми числами.
Bakuriu
20

Если тест показывает, что целое число не является простым , вы можете верить на 100%.

Это только другая сторона вопроса: если тест говорит вам, что целое число является «вероятным простым числом», у вас могут возникнуть сомнения. Повторение теста с различными «основаниями» позволяет снизить вероятность ложного успеха при «имитации» простого числа (являющегося сильным псевдопростым числом по отношению к нескольким основаниям).

Полезность теста заключается в его скорости и простоте. Никто не обязательно будет удовлетворен статусом «вероятное простое число» в качестве окончательного ответа, но можно определенно избежать траты времени на почти все составные числа, используя эту процедуру, прежде чем применять большие пушки проверки простоты .

Сравнение со сложностью факторизации целых чисел - отвлекающий маневр. Известно, что простота целого числа может быть определена за полиномиальное время, и действительно есть доказательство того, что расширение критерия Миллера-Рабина на достаточно много оснований является окончательным (при обнаружении простых чисел, в отличие от вероятных простых чисел), но это предполагает обобщенную гипотезу Римана, поэтому она не так надежна, как (более дорогой) тест простоты AKS .

хардмат
источник
4
Стоит отметить, что AKS был обнаружен только в августе 2002 года, тогда как этот метод находится в JDK с февраля 2002 года
James_pic
3
Нет, подождите, это было в JDK с февраля 1997 года (я смотрел на probablePrimeметод, а не на isProbablePrimeметод)
James_pic
1
Действительно, название статьи Агравала, Каяла и Саксены 2002 года «PRIMES is in P» сигнализирует о первом безусловном доказательстве полиномиальной (в битах n ) сложности для детерминированного (общего целочисленного) тестирования на простоту. Миллер (1975) показал, что, предполагая GRH , простота целого числа может быть детерминированно проверена с шагом, пропорциональным четвертой степени длины в битах, что является гораздо лучшим показателем, чем в настоящее время известно для AKS или его вариантов.
hardmath
Хотя AKS асимптотически быстрее, такие методы, как ECPP, были бы намного эффективнее для «криптографических» или «промышленных» простых чисел.
Бретт Хейл
2
AKS безумно медленный и не будет быстрее, чем APR-CL, для любого числа, вычисляемого в геологическом масштабе времени, не говоря уже о человеческом масштабе. APR-CL и ECPP существовали уже в 1997 году. Как упоминает Бретт, ECPP - хороший выбор, если нам нужно доказательство. Все они медленны по сравнению с вероятными простыми методами (например, MR, BPSW, Frobenius).
DanaJ
19

Стандартный вариант использования BigInteger.isProbablePrime(int)- в криптографии. В частности, некоторые криптографические алгоритмы, такие как RSA , требуют произвольно выбранных больших простых чисел. Однако важно отметить, что эти алгоритмы на самом деле не требуют, чтобы эти числа гарантированно были простыми - они просто должны быть простыми с очень высокой вероятностью.

Насколько высока очень высокая? Что ж, в криптографическом приложении обычно вызывается .isProbablePrime()с аргументом где-то между 128 и 256. Таким образом, вероятность того, что непростое число пройдет такой тест, меньше одного из 2 128 или 2 256 .

Давайте посмотрим на это в перспективе: если бы у вас было 10 миллиардов компьютеров, каждый из которых генерировал 10 миллиардов вероятных простых чисел в секунду (что означало бы менее одного тактового цикла на число на любом современном процессоре), и простота этих чисел была проверена с помощью .isProbablePrime(128), вы в среднем можно было бы ожидать, что одно непростое число будет проскакивать каждые 100 миллиардов лет .

То есть, это было бы так, если бы все эти 10 миллиардов компьютеров могли каким-то образом работать в течение сотен миллиардов лет без каких-либо сбоев оборудования. На практике, однако, это намного более вероятно , для случайного космических лучей , чтобы ударить ваш компьютер в нужное время и место , чтобы переворачивать возвращаемое значение из .isProbablePrime(128)от ложного к истине, не вызывая никаких других обнаруживаемых эффектов, чем для не -простое число, чтобы действительно пройти вероятностный тест на простоту на этом уровне достоверности.

Конечно, такой же риск случайных космических лучей и других аппаратных сбоев применим и к детерминированным тестам на простоту, таким как AKS . Таким образом, на практике даже эти тесты имеют (очень маленькую) базовую частоту ложных срабатываний из-за случайных отказов оборудования (не говоря уже обо всех других возможных источниках ошибок, таких как ошибки реализации).

Так как это легко подтолкнуть внутреннюю ложных срабатываний от теста на простоту Миллера-Рабина используется .isProbablePrime()намного ниже этой базовой скорости, просто повторить тест достаточно много раз, и с тех пор, даже повторенные много раз, тест Миллера-Рабина до сих пор намного быстрее на практике, чем самые известные детерминированные тесты на простоту, такие как AKS, он остается стандартным тестом на простоту для криптографических приложений.

(Кроме того, даже если вы случайно выбрали сильное псевдопростое число в качестве одного из факторов вашего модуля RSA, это, как правило, не приведет к катастрофическому сбою. Обычно такие псевдопростые числа являются продуктом двух (или редко более) простых чисел приблизительно половина длины, что означает, что вы получите ключ RSA с несколькими простыми числами . Пока ни один из факторов не был слишком мал (а если бы они были, то тест на простоту их должен был бы уловить), алгоритм RSA будет по-прежнему работает нормально, и ключ, хотя и несколько более слабый против определенных типов атак, чем обычные ключи RSA той же длины, все же должен быть достаточно безопасным, если вы не экономите напрасно на длине ключа.)

Илмари Каронен
источник
Проблема с ошибкой - это одна из причин, по которой AKS на самом деле не используется (другая - удивительно низкая скорость), а ECPP встречается чаще. Как вы заметили, ошибки реализации в алгоритмах вполне возможны, поэтому полезно иметь сертификат, проверенный независимым кодом.
DanaJ
8

Возможный вариант использования - проверка простоты данного числа (в тесте, который сам по себе имеет множество применений). isProbablePrimeАлгоритм будет работать намного быстрее , чем точный алгоритм, поэтому , если номер не удается isProbablePrime, то одна потребность не идти в счет запуска более дорогой алгоритм.

Тед Хопп
источник
Значит, это из соображений практичности? И из-за того, что факторизация на простые множители - это проблема NP?
fge
@fge - Да, я предложил вариант использования для практичности. Я не знаю, помогает ли это при разложении на простые множители, что является значительно более сложной проблемой, чем проверка простоты. Для последнего существует алгоритм с полиномиальным временем: тест на простоту AKS .
Тед Хопп
5
@fge: факторизация действительно в НП, но я подозреваю , что вы имели в виду «NP-полной», что факторизация не известно , чтобы быть. Напротив, есть серьезные подозрения, что он не является NP-трудным.
хмахольм ушел из-за Моники
6

Поиск вероятных простых чисел - важная проблема в криптографии. Оказывается, разумная стратегия для поиска вероятного k-битового простого числа состоит в том, чтобы многократно выбирать случайное k-битное число и проверять его на вероятную простоту с помощью такого метода, как isProbablePrime().

Для дальнейшего обсуждения см. Раздел 4.4.1 Справочника по прикладной криптографии .

См. Также статью Брандта и Дамгарда о генерации вероятных простых чисел путем инкрементного поиска .

NPE
источник
5

Такие алгоритмы, как генерация ключей RSA, полагаются на способность определять, является ли число простым или нет.

Однако в то время, когда этот isProbablePrimeметод был добавлен в JDK (февраль 1997 г.), не было проверенного способа детерминированно решить, является ли число простым за разумный промежуток времени. Самым известным подходом в то время был алгоритм Миллера-Рабина - вероятностный алгоритм, который иногда давал ложные срабатывания (т. Е. Сообщал непростые числа как простые числа), но его можно было настроить для уменьшения вероятности ложных срабатываний за счет скромного увеличения времени выполнения.

С тех пор были открыты алгоритмы, которые могут детерминированно решить, является ли число простым достаточно быстро, например алгоритм AKS, который был открыт в августе 2002 года. Однако следует отметить, что эти алгоритмы все еще не так быстры, как алгоритм Миллера-Рабина.

Возможно, лучший вопрос - почему isPrimeс 2002 года в JDK не было добавлено ни одного метода.

James_pic
источник
Спасибо за историческую перспективу! Похоже, что @immibis был на правильном пути со своим комментарием о «в JDK, но никогда не удалялся»? :)
fge
1
Я знаю, что Java, как известно, никогда не удаляет вещи из стандартной библиотеки, но я не уверен, что они удалили бы это, даже если бы могли. Для некоторых приложений быть уверенным на 99,999999999% достаточно хорошо, и это намного быстрее, чем быть уверенным на 100%.
James_pic