Почему функция BigInteger.isProbablePrime() в Java возвращает true для отрицательных чисел?

Question

Я реализую криптографический алгоритм открытого ключа RSA в Java. Это требует генерации двух случайных простых чисел. Я использовал класс SecureRandom для генерации двух 1024-битных чисел для создания ключа с 2048 бит. Я обрабатываю числа, используя класс BigInteger. Я использую функцию isProbablePrime(), чтобы определить, является ли она простой, с определенностью 100. Однако я заметил, что эта функция вернулась для отрицательных чисел, хотя по определению простые числа не могут быть отрицательными.

Answer 1

Мы не можем дать окончательный ответ на вопрос «почему». Для этого вам нужно поговорить с людьми, которые разработали API.

Я склонен согласиться с гипотезой @ Weston о том, что «это не имеет значения»; см. это link. И еще одна вынос из ссылки состоит в том, что это зависит от , которое определение простого номера используется относительно того, являются ли простые числа отрицательными. (По наиболее широко используемому определению они не являются, но ...)

Однако могу сказать, что поведение внедрения является преднамеренным. Реализация этого метода заключается в следующем:

Обратите внимание на то, как перед тестированием требуется абсолютное значение кандидата.

Это поведение было на месте в течение длительного времени (из того, что я вижу). ZERO записал отчеты об ошибках Java. Это поддерживает гипотезу @ Weston.

---

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

Answer 2

Что касается простых чисел, я указал, что он может not matter. Но то, что имеет значение - это преобразование 1024 случайных битов в целое число, вы должны рассмотреть, какой из них правильный; рассматривать его как подписанный (например, вы) или относиться к нему без знака?

Так, например, в 8 бит, если я произвольно генерирую 11010011, то есть 211, когда рассматривается как целое число без знака, которое является простым числом.

Если я обрабатываю одни и те же биты 11010011 как целое число со знаком, я получаю -45, который не является простым, даже если вы принимаете отрицательные простые числа.

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

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