Тест на простоту Бэйли – PSW - Baillie–PSW primality test

Тест на простоту Бэйли-PSW является вероятностной проверки простоты алгоритм , который определяет , является ли число составное или является вероятным премьер . Он назван в честь Роберта Бэйли, Карла Померанса , Джона Селфриджа и Сэмюэля Вагстаффа .

Тест Бейли – PSW представляет собой комбинацию сильного критерия вероятного простого числа Ферма с основанием 2 и сильного критерия вероятного простого числа Люка . Каждый тест Ферма и Лукаса имеет свой собственный список псевдопростых чисел, то есть составных чисел, которые проходят тест. Например, первые десять сильных псевдопростых чисел с основанием 2:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141 и 52633 (последовательность A001262 в OEIS ).

Первые десять сильных псевдопространств Лукаса (с параметрами Лукаса ( P , Q ), определенными методом A Селфриджа):

5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309 и 58519 (последовательность A217255 в OEIS ).

Нет никаких известных совпадений между этими списками сильных псевдопредставлений Ферма и сильных псевдопредставлений Лукаса, и даже есть свидетельства того, что числа в этих списках, как правило, являются числами разных типов. Например, псевдопростые числа Ферма с основанием 2 имеют тенденцию попадать в класс остатка 1 (mod m ) для многих малых m , тогда как псевдопростые числа Лукаса имеют тенденцию попадать в класс остатка -1 (mod m ). В результате число, которое проходит и строгий тест Ферма, и сильный тест Лукаса, с большой вероятностью будет простым.

Ни одно составное число ниже 2 64 (приблизительно 1,845 · 10 19 ) не проходит тест Бейли – PSW. Следовательно, этот тест является детерминированным тестом на простоту чисел ниже этой границы. Также нет известных составных чисел выше, которые проходят проверку, другими словами, нет известных псевдопростых чисел Бейли – PSW. Несмотря на это, предполагается, что их бесконечно много.

В 1980 году авторы Померанс, Селфридж и Вагстафф предложили 30 долларов за открытие контрпримера, то есть составного числа, прошедшего этот тест. Ричард Гай неправильно указано , что стоимость этой премии был увеличен до $ 620, но он путает последовательность Лукаса с последовательностью Фибоначчи , и его замечания действительно относятся только к одной гипотезе Селфридж - х . По состоянию на июнь 2014 года приз остается невостребованным. Однако эвристический аргумент Померанса предполагает, что существует бесконечно много контрпримеров. Более того, Чен и Грин построили набор S из 1248 простых чисел, так что среди почти 2 1248 произведений различных простых чисел в S может быть около 740 контрпримеров. Однако они говорят о более слабом тесте PSW, который заменяет тест Фибоначчи тестом Лукаса.

Тест

Пусть n будет нечетным положительным целым числом, которое мы хотим проверить на простоту.

  1. При желании можно выполнить пробное деление, чтобы проверить , делится ли n на небольшое простое число, меньшее некоторого удобного предела.
  2. Выполните тест на сильное вероятное простое число с основанием 2 . Если n не является сильным вероятным основанием 2 простых чисел, то n составное; покидать.
  3. Найдите первую букву D в последовательности 5, −7, 9, −11, 13, −15, ..., для которой символ Якоби ( D / n ) равен −1. Установите P = 1 и Q = (1 - D ) / 4.
  4. Выполните сильный Lucas вероятное простое испытание на п с использованием параметров D , P и Q . Если n не является сильным вероятным простым числом Люка, то n составное. В противном случае n почти наверняка простое.

Замечания.

  1. Первый шаг - только для повышения эффективности. Тест Бейли – PSW работает без этого шага, но если n имеет малые простые множители, то самый быстрый способ показать, что n составное, - это найти множитель путем пробного деления.
  2. Шаг 2, по сути, представляет собой однократное применение теста простоты Миллера – Рабина , но с использованием фиксированной базы 2. В использовании базы 2 нет ничего особенного; другие базы могут работать так же хорошо. Однако была проделана большая работа (см. Выше) для проверки того, что комбинация сильного вероятного простого простого числа с основанием 2 и сильного критерия Лукаса хорошо помогает отличить простые числа от составных.
  3. Бэйли и Вагстафф доказали в теореме 9 на стр. 1413, что среднее количество D s, которое необходимо попробовать, составляет около 3,147755149.
  4. Если n - полный квадрат, то шаг 3 никогда не даст D с ( D / n ) = −1; это не проблема, потому что полные квадраты легко обнаружить с помощью метода Ньютона для квадратных корней. Если на шаге 3 не удается быстро получить D , следует проверить, является ли n идеальным квадратом.
  5. С учетом п , существуют и другие методы для выбора D , P и Q . Важно то, что символ Якоби ( D / n ) равен −1. Брессуд и Вагон объясняют, почему мы хотим, чтобы символ Якоби был равен -1, а также почему получаются более мощные тесты простоты, если Q ≠ ± 1.
  6. Раздел 6 рекомендует, чтобы если Q ≠ ± 1, хороший тест на простоту также проверял два дополнительных условия конгруэнтности. Эти два сравнения почти не требуют дополнительных вычислительных затрат и только в редких случаях верны, если n составное: и .
  7. Существуют более слабые версии теста Baillie – PSW, и этот иногда называют сильным тестом Baillie – PSW.
  8. Если тест Лукаса заменяется тестом Фибоначчи, его следует называть не тестом Бейли – PSW, а скорее тестом Селфриджа или тестом PSW. См . Гипотезу Селфриджа о проверке на первичность .
  9. Померанс, Селфридж и Вагстафф предложили в 1980 году 30 долларов за составное число, прошедшее более слабую версию теста Бейли – PSW. Такое число, прошедшее (сильный) тест Бэйли – PSW, будет квалифицировано.
  10. При соответствующем методе выбора D , P и Q остается только пять нечетных составных чисел меньше 10 15, для которых . Авторы предлагают более сильную версию критерия простоты Baillie-PSW, которая включает это соответствие; Авторы предлагают вознаграждение в размере 2000 долларов за составное число, которое проходит этот более строгий тест.

Опасность полагаться только на тесты Ферма

Списки псевдопреступлений по разным основаниям существенно пересекаются.

Выберите базу a . Если n - псевдопростое число для основания a , то n , вероятно, будет одним из тех немногих чисел, которые являются псевдопервичным числом для многих оснований.

Например, n = 341 является псевдопростом по основанию 2. Из теоремы 1 на стр. 1392 следует, что существует 100 значений a (mod 341), для которых 341 является псевдопервичным основанием a . (Первые десять таких : 1, 2, 4, 8, 15, 16, 23, 27, 29 и 30). Доля таких a по сравнению с n обычно намного меньше.

Следовательно, если n является псевдопервичным числом для основания a , то n с большей вероятностью, чем среднее значение, будет псевдопервичным числом для некоторого другого основания. Например, существует 21853 псевдопростых чисел с основанием 2 до 25 · 10 9 . Это примерно два из миллиона нечетных целых чисел в этом диапазоне. Тем не мение:

  • 4709 из этих 21853 чисел (более 21 процента) также являются псевдопростыми числами по основанию 3;
  • 2522 из этих 4709 чисел (более 53 процентов) являются псевдопростыми числами по основанию 2, 3 и 5;
  • 1770 из этих 2522 чисел (более 70 процентов) являются псевдопростыми числами по основаниям 2, 3, 5 и 7.

29341 - это наименьшее псевдопростое число для оснований от 2 до 12. Все это говорит о том, что вероятные проверки простых чисел для разных оснований не являются независимыми друг от друга, так что выполнение проверки вероятных простых чисел Ферма для все большего числа оснований будет давать убывающую отдачу. С другой стороны, расчеты в и расчеты до 2 64 , упомянутых выше , показывают , что Ферма и Лукас вероятными простых тесты являются независимыми, так что сочетание этих видов испытаний будет сделать мощный тест на простоту, особенно если сильные формы Используются тесты.

Обратите внимание, что число, которое является псевдопервичным для всех простых оснований 2, ..., p , также является псевдопервичным для всех p-гладких оснований .

Также существует совпадение сильных псевдопреступлений по разным основаниям. Например, 1373653 - это наименьшее сильное псевдопростое число для оснований 2–4, а 3215031751 - наименьшее сильное псевдопростое число для оснований 2–10. Арно дает 397-значное число Кармайкла N, которое является сильным псевдопростом для всех простых оснований меньше 307. Поскольку это N является числом Кармайкл, Н является также (не обязательно сильно) псевдопростое число всех баз менее р , где р представляет собой 131-значный наименьший простой делитель N . Быстрый расчет показывает , что N является не Лукас вероятным простым , когда Д , Р , и Q выбирают способом , описанные выше, так что это число будет правильно определенно с помощью теста Бэйлей-PSW быть составными.

Применение комбинированных тестов на простоту Ферма и Лукаса

Следующие ниже системы компьютерной алгебры и программные пакеты используют некоторую версию теста простоты Бэйли – PSW.

Maple «сек IsPrime функция, Mathematica » s PrimeQ функция, PARI / GP «s IsPrime и ispseudoprime функции и SageMath » s is_pseudoprime функция все используют сочетание сильного вероятного простого теста Ферма и тест Лукаса. Maxima «s primep функция использует такое испытание для чисел больше , чем 341550071728321.

В библиотеке FLINT есть функции n_is_probabprime и n_is_probabprime_BPSW, которые используют комбинированный тест, а также другие функции, которые выполняют тесты Ферма и Лукаса по отдельности.

Класс BigInteger в стандартных версиях Java и в реализациях с открытым исходным кодом, таких как OpenJDK , имеет метод isProbablePrime . Этот метод выполняет один или несколько тестов Миллера – Рабина со случайным основанием. Если n , проверяемое число, имеет 100 бит или более, этот метод также выполняет несильный тест Лукаса, который проверяет, равно ли U n + 1 0 (mod n ). Использование случайных оснований в тестах Миллера – Рабина имеет преимущество и недостаток по сравнению с выполнением теста с одним основанием 2, как указано в тесте Бейли – PSW. Преимущество состоит в том, что с помощью случайных оснований можно получить оценку вероятности того, что n составное. Недостатком является то, что, в отличие от теста Бейли – PSW, нельзя с уверенностью сказать, что если n меньше некоторой фиксированной границы, например 2 64 , то n простое.

В Perl , в Math :: простоте и Math :: Prime :: Util модули имеют функции для выполнения сильного теста Бэйлей-PSW, а также отдельные функций для сильного и сильных псевдопростого числа испытаний Lucas. В Python , то NZMATH библиотека имеет сильное псевдопростое число и тесты Лукаса, но не имеет комбинированную функцию. Библиотека SymPy это реализует.

Начиная с версии 6.2.0, функция mpz_probab_prime_p библиотеки множественной точной арифметики GNU использует строгий тест Лукаса и тест Миллера – Рабина; предыдущие версии не использовали Baillie – PSW. Магма «s IsProbablePrime и IsProbablyPrime функция использует 20 Миллер-Рабин тестов для чисел> 34 · 10 13 , но не объединить их с вероятным премьером - тестом Лукаса.

Криптографические библиотеки часто имеют функции первичного тестирования. Альбрехт и др. обсудить тесты, используемые в этих библиотеках. Некоторые используют комбинированный тест Ферма и Лукаса; многие этого не делают. Для некоторых из последних Альбрехт и др. смогли составить составные числа, которые библиотеки объявили простыми.

Рекомендации

дальнейшее чтение