Тест простоты Бейли-ПСВ
Алгоритм вероятностной проверки простоты
Нерешенная задача по математике :
Существует ли составное число, которое проходит тест на простоту Бейли–ПСВ?
(еще нерешенные проблемы по математике)

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

Тест Бейли-ПСВ представляет собой комбинацию сильного теста Ферма на вероятные простые числа по основанию 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 ). [1] : §6  [2] : Таблица 2 и §5  В результате число, которое проходит как сильный тест Ферма по основанию 2, так и сильный тест Люка, с большой вероятностью будет простым. Если вы выберете случайное основание, может быть некоторое составное n, которое пройдет как тесты Ферма, так и тесты Люка. Например, n=5777 является сильным psp по основанию 76, а также сильным псевдопростым числом Люка.

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

В 1980 году авторы Померанс, Селфридж и Вагстафф предложили 30 долларов за открытие контрпримера, то есть составного числа, которое прошло этот тест. Ричард Гай неверно заявил, что стоимость этого приза была увеличена до 620 долларов, но он путал последовательность Лукаса с последовательностью Фибоначчи , и его замечания на самом деле применимы только к гипотезе Селфриджа . [4] По состоянию на июнь 2014 года приз остается невостребованным. Однако эвристический аргумент Померанса предполагает, что существует бесконечно много контрпримеров. [5] Более того, Чен и Грин [6] [7] построили множество 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. Выполните сильный тест Люка на вероятное простое число n с использованием параметров D , P и Q . Если n не является сильным вероятным простым числом Люка, то n является составным. В противном случае n почти наверняка является простым числом.

Замечания.

  1. Первый шаг нужен только для эффективности. Тест Бейли–ПСВ работает и без этого шага, но если n имеет небольшие простые множители, то самый быстрый способ показать, что n является составным, — найти множитель методом пробного деления.
  2. Шаг 2, по сути, является одним применением теста простоты Миллера-Рабина , но с использованием фиксированного основания 2. Нет ничего особенного в использовании основания 2; псевдопростые числа с разными основаниями, похоже, имеют одинаковую скорость роста [1] , : §8,  поэтому другие основания могут работать так же хорошо. Однако было проделано много работы (см. выше) для проверки того, что комбинация сильного вероятного теста простоты с основанием 2 и сильного теста Лукаса хорошо справляется с различением простых чисел от составных.
  3. Бейли и Вагстафф доказали в теореме 9 на странице 1413 [2] , что среднее число D , которые необходимо перепробовать, составляет около 3,147755149.
  4. Если n — полный квадрат, то шаг 3 никогда не даст D с ( D / n ) = −1; это не проблема, поскольку полные квадраты легко обнаружить с помощью метода Ньютона для квадратных корней. Если шаг 3 не даёт D быстро, следует проверить, является ли n полным квадратом.
  5. При заданном n существуют другие методы выбора D , P и Q. [2] : 1401, 1409  Важно то, что символ Якоби ( D / n ) равен −1. Брессо и Вагон объясняют, почему мы хотим , чтобы символ Якоби был равен −1, а также почему получаются более мощные тесты на простоту, если Q ≠ ±1. [8] : 266–269 
  6. Раздел 6 [2] рекомендует, что если Q ≠ ±1, хороший тест на простоту должен также проверять два дополнительных условия конгруэнтности. Эти два конгруэнтности не требуют почти никаких дополнительных вычислительных затрат и редко бывают верными, если n является составным: и . В н + 1 ≡ 2 В ( мод н ) {\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}} В ( н + 1 ) / 2 = В ⋅ В ( н − 1 ) / 2 ≡ В ⋅ ( В н ) ( мод н ) {\displaystyle Q^{(n+1)/2}=Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left({\tfrac {Q}{n}}\right){\pmod {n}}}
  7. Существуют более слабые версии теста Бейли–PSW, и этот иногда называют сильным тестом Бейли–PSW.
  8. Если тест Лукаса заменить тестом Фибоначчи, то его следует называть не тестом Бейли–PSW, а тестом Селфриджа или тестом PSW. См. гипотезу Селфриджа о тестировании на простоту .
  9. Померанс, Селфридж и Вагстафф предложили $30 в 1980 году за составное число, прошедшее более слабую версию теста Бейли-PSW. Такое число, прошедшее (сильный) тест Бейли-PSW, будет соответствовать требованиям. [1]
  10. При соответствующем методе выбора D , P , и Q , существует только пять нечетных, составных чисел (также называемых псевдопростыми числами Диксона второго рода) меньших 10 15 , для которых . [9] Авторы [9] предлагают более сильную версию теста простоты Бейли-ПСВ, которая включает это соответствие; авторы предлагают вознаграждение в размере 2000 долларов за составное число, которое пройдет этот более сильный тест. Эта версия алгоритма уже используется в Mathematica. В н + 1 ≡ 2 В ( мод н ) {\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}

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

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

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

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

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

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

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

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

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

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

Следующие системы компьютерной алгебры и пакеты программного обеспечения используют некоторые версии теста простоты Бейли–ПСВ.

Функция isprime в Maple [12] , функция PrimeQ в Mathematica (которая уже использует версию Baillie–PSW 2020 года [13] , функции isprime и ispseudoprime в PARI/GP [14] и функция is_pseudoprime в SageMath [15] — все они используют комбинацию сильного вероятного теста Ферма на простоту и теста Лукаса. Функция primep в Maxima использует такой тест для чисел больше 341550071728321. [16]

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

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

В Perl модули Math::Primality [20] и Math::Prime::Util [21] [22] имеют функции для выполнения сильного теста Бейли–PSW, а также отдельные функции для сильных тестов псевдопростых чисел и Люка. В Python библиотека NZMATH [23] имеет сильные тесты псевдопростых чисел и Люка, но не имеет объединенной функции. Библиотека SymPy [ 24] реализует это.

Начиная с версии 6.2.0, функция mpz_probab_prime_p библиотеки арифметики множественной точности GNU использует сильный тест Лукаса и тест Миллера–Рабина; предыдущие версии не использовали тест Бейли–PSW. [25] Функции IsProbablePrime и IsProbablyPrime библиотеки Magma используют 20 тестов Миллера–Рабина для чисел > 34·10 13 , но не объединяют их с тестом Люка на вероятное простое число. [26]

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

Ссылки

  1. ^ abcde Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Samuel S. Jr. (июль 1980 г.). "Псевдопростые числа до 25·109" (PDF) . Mathematics of Computation . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.
  2. ^ abcdef Бейли, Роберт; Вагстафф, Сэмюэл С. младший (октябрь 1980 г.). «Псевдопростые числа Лукаса» (PDF) . Математика вычислений . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR  2006406. MR  0583518.
  3. ^ Nicely, Thomas R. (2012-01-13) [Впервые опубликовано 2005-06-10]. "Тест на первичность Бейли–ПСВ". trnicely.net . Архивировано из оригинала 2019-11-21 . Получено 2013-03-17 .
  4. ^ Гай, Р. (1994). «Псевдопростые числа. Псевдопростые числа Эйлера. Сильные псевдопростые числа». §A12 в Unsolved Problems in Number Theory . 2nd ed., p. 28, New York: Springer-Verlag. ISBN 0-387-20860-7 . 
  5. ^ Померанс, К. (1984). «Существуют ли контрпримеры к тесту простоты Бейли–ПСВ?» (PDF) .
  6. ^ Грин, Джон Р. (nd). "Baillie–PSW". Университет Миннесоты в Дулуте . Получено 29 мая 2020 г.
  7. ^ Чэнь, Чжо; Грин, Джон (август 2003 г.). «Некоторые комментарии о псевдопростых числах Бейли–ПСВ» (PDF) . The Fibonacci Quarterly . 41 (4): 334–344.
  8. ^ Брессо, Дэвид ; Вагон, Стэн (2000). Курс по вычислительной теории чисел . Нью-Йорк: Key College Publishing в сотрудничестве с Springer. ISBN 978-1-930190-10-8.
  9. ^ ab Роберт Бейли; Эндрю Фиори; Сэмюэл С. Вагстафф, младший (июль 2021 г.). «Усиление теста простоты Бейли-ПСВ». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . doi : 10.1090/mcom/3616. ISSN  0025-5718. S2CID  220055722.
  10. ^ Вагстафф, Сэмюэл С. младший (1982). «Псевдопростые числа и обобщение гипотезы Артина». Акта Арифметика . 41 (2): 141–150. дои : 10.4064/aa-41-2-141-150 .
  11. ^ Арно, Ф. (август 1995 г.). «Построение чисел Кармайкла, являющихся сильными псевдопростыми числами с несколькими основаниями». Журнал символических вычислений . 20 (2): 151–161. doi : 10.1006/jsco.1995.1042 .
  12. ^ isprime - Справочная документация Maple на maplesoft.com.
  13. ^ Wolfram Language & System Documentation Center — некоторые заметки о внутренней документации по реализации на wolfram.com.
  14. ^ Руководство пользователя PARI/GP (версия 2.11.1) документация для PARI/GP.
  15. ^ Документация SageMath Документация по SageMath.
  16. ^ Maxima Руководство по документации для Maxima.
  17. ^ FLINT: Документация по быстрой библиотеке теории чисел для FLINT 2.5.
  18. ^ BigInteger.java DocJar: Поиск API Java с открытым исходным кодом.
  19. ^ Документация BigInteger.java для OpenJDK.
  20. ^ Модуль Math::Primality Perl с тестом BPSW
  21. ^ Math::Prime::Util Модуль Perl с тестами на простоту, включая BPSW
  22. ^ Math::Prime::Util::GMP Модуль Perl с тестами на простоту, включая BPSW, с использованием C+GMP
  23. ^ NZMATH Архивировано 17.01.2013 в системе расчета теории чисел Wayback Machine на Python
  24. ^ "SymPy". SymPy — библиотека Python для символьной математики .
  25. ^ Документация по алгоритму тестирования GNU MP 6.2.0 Prime для GMPLIB.
  26. ^ Система вычислительной алгебры Magma — документация по простым числам и проверке простоты для Magma.
  27. ^ Альбрехт, Мартин Р.; Массимо, Джейк; Патерсон, Кеннет Г.; Соморовски, Юрай (15 октября 2018 г.). Prime and Prejudice: Primality Testing Under Adversarial Conditions (PDF) . Конференция ACM SIGSAC по компьютерной и коммуникационной безопасности 2018 г. Торонто: Ассоциация вычислительной техники . стр. 281–298. doi :10.1145/3243734.3243787.

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

  • Якобсен, Дана Статистика псевдопростых чисел, таблицы и данные (списки псевдопростых чисел с основанием 2, Лукаса и других псевдопростых чисел до 10 14 )
  • Nicely, Thomas R., Тест на простоту Baillie–PSW., архивировано из оригинала 28.08.2013 , извлечено 07.08.2007
  • Вайсштейн, Эрик В. «Тест на примитивность Бэйли – PSW». Математический мир .
Взято с "https://en.wikipedia.org/w/index.php?title=Baillie–PSW_primality_test&oldid=1185817026"