Тест Бейли — Померанца — Селфриджа — Уогстаффа

Тест Бейли — Померанца — Селфриджа — Уогстаффа (БПСВ, BPSW) — вероятностный алгоритм проверки на простоту, который определяет, является число составным или вероятно простым. Назван по фамилиям его изобретателей — Роберта Бэйли, Карла Померанца, Джона Селфриджа, Сэмюэля Вагстаффа.

Тест сочетает тест Ферма на сильную псевдопростоту по основанию 2 и тест Люка на сильную псевдопростоту. Для тестов Ферма и Люка существуют отдельные списки псевдопростых чисел, то есть составных чисел, которые проходят испытание на простоту. Например, первые десять сильных псевдопростых чисел для испытания Ферма по основанию 2:

2047, 3277, 4033, 4681, 8321, 15 841, 29 341, 42 799, 49 141 и 52 633[1]

Первые десять псевдопростых чисел теста Люка (с параметрами ):

5459, 5777, 10 877, 16 109, 18 971, 22 499, 24 569, 25 199, 40 309 и 58 519[2].

Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка. Существуют основания полагать, что в эти списки попадают, как правило, различные типы чисел. Например, псевдопростые по основанию 2, как правило, попадают в класс вычетов 1 по модулю m для многих малых m, в то время как псевдопростые числа Люка, как правило, попадают в класс вычетов −1 по модулю [3]:§6[4]:Table 2 & §5. В результате число, которое проходит как сильный тест Ферма, так и сильное испытание Люка, с большой вероятностью будет простым.

Ни одно составное число, меньшее 264 (что примерно равно 1,845 · 1019), не проходит тест БПСВ[5]. Таким образом, этот тест можно считать детерминированным тестом простоты для чисел, меньших указанной границы. Также пока не известно ни одно составное число, большее границы, которое проходит тест.

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

Алгоритм

Пусть  — нечётное натуральное число, которое необходимо проверить на простоту.

  1. По желанию[уточнить] провести перебор простых делителей, меньших заданной верхней границы, и проверить, является ли число полным квадратом. Если найден простой множитель или число является полным квадратом, проверка завершена - число не простое.
  2. Произвести сильную проверку на простоту по основанию 2. Если не является сильно вероятно простым по основанию 2, то является составным; на этом проверка завершается.
  3. Найти первое в последовательности 5, −7, 9, −11, 13, −15, …, для которого символ Якоби равен −1. Положим и .
  4. Выполнить сильный тест Люка на простоту с параметрами . Если не является сильно вероятно простым, то является составным; на этом проверка заканчивается. В противном случае, с высокой вероятностью является простым.

Комментарии:

  1. Первый этап лишь повышает эффективность. Тест БПСВ работает и без этого шага, однако, если имеет небольшие простые делители, то самый быстрый способ показать, что является составным — найти такой делитель серией проверок.
  2. На втором этапе однократно применяется тест Миллера — Рабина на простоту. Выбор основания не влияет на эффективность конкретной проверки. Однако, многочисленные исследования показали, что сочетание сильного теста на простоту именно по основанию 2 и сильного теста Люка на простоту показывает хорошие результаты в проверке чисел на простоту.
  3. Бейли и Уогстафф доказали[4], что среднее количество , которое необходимо перебрать, примерно равно 3,147755149.
  4. Если является полным квадратом, то на этапе 3 никогда не найдется , такое что ; однако, это не станет проблемой, поскольку полные квадраты легко обнаружить при помощью метода Ньютона для квадратных корней. Если на шаге 3 не удается найти за короткое время, следует проверить, является ли полным квадратом.
  5. Для заданного существуют и другие методы подбора коэффициентов [4]:1401, 1409. Важно то, что символ Якоби должен быть равен −1. Брессон и Вэгон доказали, что для эффективности тестирования символ Якоби должен быть равен −1, а значение [10]:266–269.

Ошибки при использовании теста Ферма отдельно от теста Люка

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

Если  — псевдопростое по некоторому основанию , то , вероятно, является псевдопростым и по многим другим основаниям[11].

Например, псевдопросто по основанию 2. Бейли и Вагстафф доказали[4], что существует 100 значений (по модулю 341), для которых 341 псевдопросто по основанию . (Первые десять из них: 1, 2, 4, 8, 15, 16, 23, 27, 29, и 30). Количество таких по сравнению с обычно гораздо меньше.

Поэтому, если  — псевдопросто по основанию , высока вероятность того, что псевдопросто и по какому-то ещё основанию. Например, существует 21853 псевдопростых чисел по основанию 2 на отрезке от 0 до 25·109. Это лишь около двух чисел на миллион из всех нечетных на этом отрезке. Однако:

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

29341 — наименьшее псевдопростое по основаниям от 2 до 10. (и по всем 7-гладким основаниям). Это указывает на то, что вероятностные тесты простоты по разным основаниям не независимы, таким образом проведение теста Ферма по все большему количеству результатов будет отсеивать с каждым разом все меньшее количество псевдопростых. С другой стороны, вычисления вплоть до 264, упомянутые выше, говорят о том, что тесты Ферма и Люка являются независимыми, таким образом, комбинация этих тестов является мощным тестом на простоту, особенно при использовании сильных форм этих тестов.

Существуют также пересечения между сильными псевдопростыми числами по разным основаниям. Например, 1373653 является наименьшим сильным псевдопростым по всем основаниям от 2 до 4 (и по всем 3-гладким), а 3215031751 — наименьшее сильное псевдопростое по всем основаниям от 2 до 10 (и всем 7-гладким). Арнольд[12] предъявляет 397-значное составное число N, который является сильным псевдопростым по всем основаниям, меньшим 307. (и по всем 293-гладким). Поскольку N является числом Кармайкла, N также будет (не обязательно сильно) псевдопростым по всем основаним меньшим р, где р — наименьший 131-значный простой делитель N. В то же время, быстрый подсчет показывает, что N не является псевдопоростым числом Люка, если D, P, Q были выбраны методом, описанным выше, таким образом тест БПСВ определит, что это число составное.

Применения сочетания тестов Ферма и Люка на простоту

Нижеперечисленные компьютерные системы и программные пакеты используют различные версии теста БПСВ.

Функции IsPrime в Maple[13], PrimeQ в Mathematica[14], is_pseudoprime в Sage[15] и функции isprime и ispseudoprime в PARI/GP[16] используют сочетание теста Миллера — Рабина (сильного теста Ферма) и теста Люка. Функция Primep в Maxima использует такой тест для чисел, превосходящих 341550071728321[17].

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

Класс BigInteger в стандартных версиях Java и в версиях с открытым исходным кодом, таких как OpenJDK, имеет метод isProbablePrime. Этот метод проводит один или несколько тестов Миллера — Рабина по случайными основаниям. Если проверяемое число содержит 100 и более битов, этот метод также проводит тест Люка, который проверяет, что [19][20]. Использование случайных оснований в тестах Миллера — Рабина имеет как преимущества, так и недостатки по сравнению с проверкой лишь по основанию 2, как в тесте БПСВ. Преимуществом использования случайных оснований является то, что можно получить вероятностную оценку того, что n является составным. Недостатком является то, что, в отличие от теста БПСВ, нельзя с уверенностью сказать, что если n меньше, чем некоторая фиксированная граница, например 264, то n является простым.

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

Функция mpz_probab_prime_p из GNU Multiple Precision Arithmetic Library использует тест Миллера — Рабина, но не использует тест Люка[25]. Функции IsProbablePrime и IsProbablyPrime из Magma проводят 20 тестов Миллера — Рабина для чисел больших 34·1013, однако не используют их сочетание с тестом Люка[26].

Примечания

  1. последовательность A001262 в OEIS
  2. последовательность A217255 в OEIS
  3. Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. The pseudoprimes to 25·109 (англ.) // Mathematics of Computation : journal. — 1980. — July (vol. 35, no. 151). P. 1003—1026. doi:10.1090/S0025-5718-1980-0572872-7.
  4. Robert Baillie; Samuel Wagstaff. Lucas Pseudoprimes (англ.) // Mathematics of Computation : journal. — 1980. — October (vol. 35, no. 152). P. 1391—1417. doi:10.1090/S0025-5718-1980-0583518-6.
  5. The Baillie-PSW Primality Test (недоступная ссылка). Thomas R. Nicely. Дата обращения: 5 декабря 2015. Архивировано 28 августа 2013 года.
  6. Guy, R. (1994). «Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.» §A12 in Unsolved Problems in Number Theory. 2nd ed., p. 28, New York: Springer-Verlag. ISBN 0-387-20860-7.
  7. Pomerance, C. (1984), Are There Counterexamples to the Baillie-PSW Primality Test?, <http://www.pseudoprime.com/dopo.pdf>
  8. Baillie-PSW John R. Greene’s website.
  9. Zhuo Chen; John Greene. Some Comments on Baillie-PSW Pseudoprimes (англ.) // The Fibonacci Quarterly : journal. — 2003. — August (vol. 41, no. 4). P. 334—344.
  10. David Bressoud; Stan Wagon A Course in Computational Number Theory (неопр.). — New York: Key College Publishing in cooperation with Springer, 2000. — ISBN 978-1-930190-10-8.
  11. Samuel S. Wagstaff, Jr. Pseudoprimes and a generalization of Artin's conjecture (англ.) // Acta Arithmetica : journal. — 1982. Vol. 41, no. 2. P. 141—150.
  12. F. Arnault. Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases (англ.) // Journal of Symbolic Computation : journal. — 1995. — August (vol. 20, no. 2). P. 151—161. doi:10.1006/jsco.1995.1042.
  13. isprime — Maple Help документация по maplesoft.com.
  14. Some Notes on Internal Implementation-Wolfram Mathematica 9 Documentation документация по wolfram.com.
  15. Sage Reference Manual Release 5.7 Архивная копия от 18 января 2013 на Wayback Machine документация по Sage.
  16. User’s Guide to PARI/GP (version 2.5.1) Архивная копия от 4 марта 2016 на Wayback Machine документация по PARI/GP.
  17. Maxima Manual Ver. 5.28.0 документация по Maxima.
  18. FLINT: Fast Library for Number Theory документация по FLINT 2.3.0.
  19. BigInteger.java DocJar: Search Open Source Java API.
  20. BigInteger.java документация по OpenJDK.
  21. Math::Primality модуль Perl с тестом БПСВ
  22. Math::Prime::Util модуль Perl с тестами на простоту, в том числе БПСВ
  23. Math::Prime::Util::GMP модуль Perl с тестами на простоту, в том числе БПСВ, использующий C+GMP
  24. NZMATH Архивировано 17 января 2013 года. система для работы с задачами, связанными с теорией числ в Python
  25. Prime Testing Algorithm — GNU MP 5.1.1 документация по GMPLIB
  26. Magma Computational Algebra System — Primes and Primality Testing документация по Magma.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.