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

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

Он присутствует в JDK довольно долгое время, поэтому означает, что он должен использовать. Мои ограниченные знания в области компьютерных наук и алгоритмов (и математики) говорят мне, что на самом деле не имеет смысла знать, является ли число "вероятно" простым, но не совсем простым.

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

Ответ 1

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

Оказывается, слишком сложно доказать, что эти числа превалируют. Но критерий примиренности Миллера-Рабина, один из тестов примитивности использует isProbablePrime, либо обнаруживает, что число является составным, либо не дает никакого заключения. Выполнение этого теста n times позволяет сделать вывод о наличии 1 из 2 ⁿ коэффициентов, что это число действительно композитно. Запуск 100 times дает приемлемый риск 1 в 2 ¹⁰⁰ что это число является составным.

Ответ 2

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

Это только другая сторона вопроса, если тест говорит вам, что целое число является "вероятным простым", что вы можете усомниться в сомнении. Повторение теста с различными "основаниями" позволяет получить вероятность ложного преуспевания "имитации" простого (будучи сильным псевдопростым по отношению к множеству оснований) как можно меньше.

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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

Также см. О генерации вероятных простых чисел путем инкрементного поиска от Brandt and Damgård.

Ответ 6

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

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

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

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