Производительность Java probablePrime

Question

Производительность Java probablePrime

Возвращает положительный BigInteger, который, вероятно, является простым, с
указанная длина битла. Вероятность того, что Бигинтегер вернется мимо
этот метод композиционный не превышает 2-100.

Мой вопрос в том, насколько большую производительность это дает, не гарантируя простое число, но делая его почти определенным? Кроме того, действительно ли эта разница в производительности стоит того, чтобы в какой-то момент в будущем возникла ошибка? Особенно если достоверность шифрования зависит от того, что это число простое.

613 2

java performance biginteger

2 ответов:

Comments

Ничего не найдено.

kiheru · Accepted Answer · 2013-10-11 18:57:16

В основе probablePrime() лежит сериятестов Миллера-Рабина (количество выполняемых раундов зависит от размера бита числа) в сочетании стестом на примитивность Лукаса-Лемера . Временная сложность этих задач довольно сильно зависит от остальной части реализации BigInteger. Принимая во внимание" медленные " оценки из Википедии, будет O (K log (n)^3) и O(log(n)^3) соответственно.

С другой стороны, тест AKS-primality , без недоказанных гипотез, может выполняться в (Log(n)^6).
Таким образом, если предположить, что ваши числа достаточно велики, вероятностный тест может быть намного быстрее, чем детерминированный. Для чего-либо достаточно большого для криптографии асимптотическое поведение вполне вероятно наблюдаемо. Конечно, единственный способ узнать наверняка-это реализовать модифицированный АКС и засечь время получения результатов.
(k это число циклов в Милле-Рабине).

Adam Arold · Accepted Answer · 2013-10-11 18:22:05

Если у вас есть это:

Особенно если достоверность шифрования зависит от того, что это число простое

Вид ограничения, то вы не должны использовать probablePrime на мой взгляд. Потому что вы не можете гарантировать правильность вашего алгоритма.

Но если вероятность получения не-простого настолько мала, что сравнима, например, с вероятностью столкновения SHA-1, то вы с этим согласны. (Если git в порядке с этим, так что Вы)

Если вы используете пул простых чисел в заданном диапазоне, то вы можете просто предварительно сгенерировать список простых чисел и поместить их в таблицу поиска. это даст вам O(1) временную сложность.