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

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

Тест сочетает [[Тест Миллера — Рабина#Сильно псевдопростые числа|тест Ферма на сильную псевдопростоту]] по основанию 2 и [[Псевдопростое число Люка|тест Люка на сильную псевдопростоту]]. Для тестов Ферма и Люка существуют отдельные списки псевдопростых чисел, то есть составных чисел, которые проходят испытание на простоту. Например, первые десять сильных псевдопростых чисел для испытания Ферма по основанию 2:

: {{nums|xx=и|2047|3277|4033|4681|8321|15841|29341|42799|49141|52633}}<ref>{{OEIS|A001262}}</ref>

Первые десять псевдопростых чисел теста Люка (с параметрами <math>P=1, Q= -1</math>):

: {{nums|xx=и|5459|5777|10877|16109|18971|22499|24569|25199|40309|58519}}<ref>{{OEIS|A217255}}</ref>.

Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка. Существуют основания полагать, что в эти списки попадают, как правило, различные типы чисел. Например, псевдопростые по основанию 2, как правило, попадают в класс вычетов 1 по модулю m для многих малых m, в то время как псевдопростые числа Люка, как правило, попадают в класс вычетов −1 по модулю <math>m</math><ref name="PSW">{{статья |заглавие=The pseudoprimes to 25·10<sup>9</sup> |издание={{Нп3|Mathematics of Computation}} |том=35 |номер=151 |страницы=1003—1026 |ссылка=https://math.dartmouth.edu/~carlp/PDF/paper25.pdf |doi=10.1090/S0025-5718-1980-0572872-7 |язык=en |автор=[[Carl Pomerance]]; [[John L. Selfridge]]; [[Samuel S. Wagstaff, Jr.]] |месяц=7 |год=1980 |тип=journal |archivedate=2014-10-19 |archiveurl=https://web.archive.org/web/20141019004745/https://math.dartmouth.edu/~carlp/PDF/paper25.pdf }}</ref>{{rp|§6}}<ref name="lpsp">{{статья |заглавие=Lucas Pseudoprimes |издание={{Нп3|Mathematics of Computation}} |том=35 |номер=152 |страницы=1391—1417 |ссылка=http://mpqs.free.fr/LucasPseudoprimes.pdf |mr=583518 |doi=10.1090/S0025-5718-1980-0583518-6 |язык=en |автор=Robert Baillie; [[Samuel Wagstaff]] |месяц=10 |год=1980 |тип=journal |archivedate=2016-03-04 |archiveurl=https://web.archive.org/web/20160304032340/http://mpqs.free.fr/LucasPseudoprimes.pdf }}</ref>{{rp|Table 2 & §5}}.
В результате число, которое проходит как сильный тест Ферма, так и сильное испытание Люка, с большой вероятностью будет простым.

Ни одно составное число, меньшее 2<sup>64</sup> (что примерно равно 1,845 · 10<sup>19</sup>), не проходит тест БПСВ<ref name="TRNicely">{{cite web |title=The Baillie-PSW Primality Test |url=http://www.trnicely.net/misc/bpsw.html |publisher=Thomas R. Nicely |accessdate=2015-12-05 |archiveurl=https://web.archive.org/web/20130828131627/http://www.trnicely.net/misc/bpsw.html |archivedate=2013-08-28 |deadlink=yes }}</ref>. Таким образом, этот тест можно считать детерминированным тестом простоты для чисел, меньших указанной границы. Также пока не известно ни одно составное число, большее границы, которое проходит тест.

В 1980 году Померанц, Селфридж и Вагстафф предложили вознаграждение в размере $30 тому, кто отыщет контрпример, то есть найдет составное число, которое проходит этот тест. [[Гай, Ричард Кеннет|Ричард Гай]] ошибочно полагал, что размер вознаграждения составляет $620, но он перепутал последовательности [[Последовательность Люка|Люка]] и [[Числа Фибоначчи|Фибоначчи]], и его замечания оказались применимы лишь к одной гипотезе Селфриджа<ref>[[Richard K. Guy|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.</ref>. По состоянию на июнь 2014 года приз так и не был востребован. Тем не менее, эвристический аргумент Померанца указывает на то, что таких контрпримеров существует бесконечно много<ref>{{citation|authorlink = Carl Pomerance|last = Pomerance|first = C.|year = 1984|url = http://www.pseudoprime.com/dopo.pdf|title = Are There Counterexamples to the Baillie-PSW Primality Test?|access-date = 2015-12-05|archive-date = 2016-03-04|archive-url = https://web.archive.org/web/20160304003247/http://www.pseudoprime.com/dopo.pdf|url-status = dead}}</ref>. Кроме того, Чен и Грин<ref>[http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html Baillie-PSW] {{Wayback|url=http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html |date=20151224182345 }} John R. Greene’s website.</ref>
<ref name="ChenAndGreene">{{статья
|заглавие=Some Comments on Baillie-PSW Pseudoprimes
|издание={{Нп3|Fibonacci Quarterly|The Fibonacci Quarterly||Fibonacci Quarterly}}
|том=41
|номер=4
|страницы=334—344
|ссылка=http://www.fq.math.ca/Scanned/41-4/chen.pdf
|язык=en
|автор=Zhuo Chen; John Greene
|месяц=8
|год=2003
|тип=journal
|archivedate=2011-08-28
|archiveurl=https://web.archive.org/web/20110828123126/http://www.fq.math.ca/Scanned/41-4/chen.pdf
}}</ref> построили множество S, состоящее из 1248 таких простых чисел, что среди 2<sup>1248</sup> произведений различных простых чисел из S может быть около 740 контрпримеров. Однако, они рассматривали более слабый БПСВ-тест, который вместо теста Люка использует тест Фибоначчи.

== Алгоритм ==
Пусть <math>n</math> — нечётное натуральное число, которое необходимо проверить на простоту.
# По желанию{{Уточнить}}<!--так и надо?--> провести [[Перебор делителей|перебор простых делителей]], меньших заданной верхней границы, и проверить, является ли число полным квадратом. Если найден простой множитель или число является полным квадратом, проверка завершена - число не простое.
# Произвести сильную проверку на простоту по основанию 2. Если <math>n</math> не является сильно вероятно простым по основанию 2, то <math>n</math> является составным; на этом проверка завершается.
# Найти первое <math>D</math> в последовательности 5, −7, 9, −11, 13, −15, …, для которого [[символ Якоби]] <math>(D / n)</math> равен −1. Положим <math>P = 1</math> и <math>Q=(1-D)/4</math>.
# Выполнить сильный [[Псевдопростое число Люка|тест Люка]] на простоту с параметрами <math>D, P, Q</math>. Если <math>n</math> не является сильно вероятно простым, то <math>n</math> является составным; на этом проверка заканчивается. В противном случае, <math>n</math> с высокой вероятностью является простым.

Комментарии:
# Первый этап лишь повышает эффективность. Тест БПСВ работает и без этого шага, однако, если <math>n</math> имеет небольшие простые делители, то самый быстрый способ показать, что <math>n</math> является составным — найти такой делитель серией проверок.
# На втором этапе однократно применяется [[тест Миллера — Рабина]] на простоту. Выбор основания не влияет на эффективность конкретной проверки. Однако, многочисленные исследования показали, что сочетание сильного теста на простоту именно по основанию 2 и сильного теста Люка на простоту показывает хорошие результаты в проверке чисел на простоту.
# Бейли и Уогстафф доказали<ref name="lpsp"/>, что среднее количество <math>D</math>, которое необходимо перебрать, примерно равно 3,147755149.
# Если <math>n</math> является полным квадратом, то на этапе 3 никогда не найдется <math>D</math>, такое что <math>(D/n)=-1</math>; однако, это не станет проблемой, поскольку полные квадраты легко обнаружить при помощью [[Метод Ньютона|метода Ньютона]] для квадратных корней. Если на шаге 3 не удается найти <math>D</math> за короткое время, следует проверить, является ли <math>n</math> полным квадратом.
# Для заданного <math>n</math> существуют и другие методы подбора коэффициентов {{r|lpsp}}{{rp|1401, 1409}}. Важно то, что символ Якоби <math>(D/n)</math> должен быть равен −1. Брессон и Вэгон доказали, что для эффективности тестирования символ Якоби должен быть равен −1, а значение <math>Q \neq \pm 1</math><ref name="Bressoud">
{{книга |заглавие=A Course in Computational Number Theory |издательство=Key College Publishing in cooperation with Springer |место=New York |год=2000 |isbn=978-1-930190-10-8 |язык=und |автор={{Нп3|David Bressoud}}; {{Нп3|Stan Wagon}}}}</ref>{{rp|266–269}}.

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

Если <math>n</math> — псевдопростое по некоторому основанию <math>a</math>, то <math>n</math>, вероятно, является псевдопростым и по многим другим основаниям<ref name="SSW2">{{статья |заглавие=Pseudoprimes and a generalization of Artin's conjecture |издание={{Нп3|Acta Arithmetica}} |том=41 |номер=2 |страницы=141—150 |язык=en |тип=journal |автор=Samuel S. Wagstaff, Jr. |год=1982}}</ref>.

Например, <math>n = 341</math> псевдопросто по основанию 2. Бейли и Вагстафф доказали<ref name="lpsp"/>, что существует 100 значений <math>a</math> (по модулю 341), для которых 341 псевдопросто по основанию <math>a</math>. (Первые десять из них: 1, 2, 4, 8, 15, 16, 23, 27, 29, и 30). Количество таких <math>a</math> по сравнению с <math>n</math> обычно гораздо меньше.

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

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

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

Существуют также пересечения между сильными псевдопростыми числами по разным основаниям. Например, 1373653 является наименьшим сильным псевдопростым по всем основаниям от 2 до 4 (и по всем [[Гладкое число|3-гладким]]), а 3215031751 — наименьшее сильное псевдопростое по всем основаниям от 2 до 10 (и всем [[Гладкое число|7-гладким]]). Арнольд<ref name="Arnault397Digit">{{статья
|заглавие=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases
|издание=[[Journal of Symbolic Computation]]
|том=20
|номер=2
|страницы=151—161
|ссылка=http://www.sciencedirect.com/science/article/pii/S0747717185710425
|doi=10.1006/jsco.1995.1042
|язык=en
|тип=journal
|автор=F. Arnault
|месяц=8
|год=1995
|archivedate=2018-12-01
|archiveurl=https://web.archive.org/web/20181201144945/https://www.sciencedirect.com/science/article/pii/S0747717185710425
}}</ref> предъявляет 397-значное составное число N, который является сильным псевдопростым по всем основаниям, меньшим 307. (и по всем [[Гладкое число|293-гладким]]). Поскольку N является [[Число Кармайкла|числом Кармайкла]], N также будет (не обязательно сильно) псевдопростым по всем основаним меньшим р, где р — наименьший 131-значный простой делитель N. В то же время, быстрый подсчет показывает, что N не является псевдопоростым числом Люка, если D, P, Q были выбраны методом, описанным выше, таким образом тест БПСВ определит, что это число составное.

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

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

Функции <code>IsPrime</code> в [[Maple]]<ref>[http://www.maplesoft.com/support/help/Maple/view.aspx?path=isprime isprime — Maple Help] {{Wayback|url=http://www.maplesoft.com/support/help/Maple/view.aspx?path=isprime |date=20120930082644 }}
документация по maplesoft.com.</ref>, <code>PrimeQ</code> в [[Mathematica]]<ref>[http://reference.wolfram.com/mathematica/tutorial/SomeNotesOnInternalImplementation.html#6849 Some Notes on Internal Implementation-Wolfram Mathematica 9 Documentation] {{Wayback|url=http://reference.wolfram.com/mathematica/tutorial/SomeNotesOnInternalImplementation.html#6849 |date=20140413201258 }}
документация по wolfram.com.</ref>, <code>is_pseudoprime</code> в [[Sage]]<ref>[http://www.sagemath.org/pdf/reference.pdf Sage Reference Manual Release 5.7] {{Wayback|url=http://www.sagemath.org/pdf/reference.pdf |date=20130118202129 }}
документация по Sage.</ref> и функции <code>isprime</code> и <code>ispseudoprime</code> в {{iw|PARI/GP}}<ref>[http://pari.math.u-bordeaux.fr/pub/pari/manuals/2.5.1/users.pdf User’s Guide to PARI/GP (version 2.5.1)] {{Wayback|url=http://pari.math.u-bordeaux.fr/pub/pari/manuals/2.5.1/users.pdf |date=20160304001044 }}
документация по PARI/GP.</ref> используют сочетание теста Миллера — Рабина (сильного теста Ферма) и теста Люка. Функция <code>Primep</code> в [[Maxima]] использует такой тест для чисел, превосходящих 341550071728321<ref>[http://maxima.sourceforge.net/docs/manual/en/maxima.pdf Maxima Manual Ver. 5.28.0] {{Wayback|url=http://maxima.sourceforge.net/docs/manual/en/maxima.pdf |date=20140709014216 }}
документация по Maxima.</ref>.

В библиотеке {{iw|FLINT}} содержатся функции <code>n_is_probabprime</code> и <code>n_is_probabprime_BPSW</code>, которые используют комбинированный тест, а также другие функции, которые используют испытания Ферма и Люка по отдельности<ref>[http://flintlib.org/ FLINT: Fast Library for Number Theory] {{Wayback|url=http://flintlib.org/ |date=20151208121111 }} документация по FLINT 2.3.0.</ref>.

Класс <code>BigInteger</code> в стандартных версиях [[Java (программная платформа)|Java]] и в версиях с открытым исходным кодом, таких как [[OpenJDK]], имеет метод <code>isProbablePrime</code>. Этот метод проводит один или несколько тестов Миллера — Рабина по случайными основаниям. Если проверяемое число содержит 100 и более битов, этот метод также проводит тест Люка, который проверяет, что <math>U_{n+1}=- \pmod  n</math><ref>[http://www.docjar.org/html/api/java/math/BigInteger.java.html BigInteger.java] {{Wayback|url=http://www.docjar.org/html/api/java/math/BigInteger.java.html |date=20151208133313 }} DocJar: Search Open Source Java API.</ref><ref>[http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/math/BigInteger.java BigInteger.java] {{Wayback|url=http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/00cd9dc3c2b5/src/share/classes/java/math/BigInteger.java |date=20151208062027 }} документация по OpenJDK.</ref>. Использование случайных оснований в тестах Миллера — Рабина имеет как преимущества, так и недостатки по сравнению с проверкой лишь по основанию 2, как в тесте БПСВ. Преимуществом использования случайных оснований является то, что можно получить вероятностную оценку того, что n является составным. Недостатком является то, что, в отличие от теста БПСВ, нельзя с уверенностью сказать, что если n меньше, чем некоторая фиксированная граница, например 2<sup>64</sup>, то n является простым.

В языке [[Perl]] модули <code>Math::Primality</code><ref>[http://metacpan.org/module/Math::Primality Math::Primality] модуль Perl с тестом БПСВ</ref> и <code>Math::Prime::Util</code><ref>[http://metacpan.org/module/Math::Prime::Util Math::Prime::Util] {{Wayback|url=http://metacpan.org/module/Math::Prime::Util |date=20130903054909 }} модуль Perl с тестами на простоту, в том числе БПСВ</ref><ref>[http://metacpan.org/module/Math::Prime::Util::GMP Math::Prime::Util::GMP] {{Wayback|url=http://metacpan.org/module/Math::Prime::Util::GMP |date=20130903200222 }} модуль Perl с тестами на простоту, в том числе БПСВ, использующий C+GMP</ref> содержат функции для выполнения сильного теста БПСВ, а также отдельные функции для сильного теста на псевдопростоту и сильного теста Люка. Библиотека NZMATH<ref>[http://tnt.math.se.tmu.ac.jp/nzmath/ NZMATH] {{webarchive|url=https://web.archive.org/web/20130117225129/http://tnt.math.se.tmu.ac.jp/nzmath/ |date=2013-01-17 }} система для работы с задачами, связанными с теорией числ в Python</ref> языка [[Python]] содержит сильный тест на псевдопростоту и сильный тест Люка, но не содержит их комбинации.

Функция <code>mpz_probab_prime_p</code> из [[GNU Multi-Precision Library|GNU Multiple Precision Arithmetic Library]] использует тест Миллера — Рабина, но не использует тест Люка<ref>[http://gmplib.org/manual/Prime-Testing-Algorithm.html Prime Testing Algorithm — GNU MP 5.1.1] {{Wayback|url=http://gmplib.org/manual/Prime-Testing-Algorithm.html |date=20151024010648 }}
документация по GMPLIB</ref>. Функции <code>IsProbablePrime</code> и <code>IsProbablyPrime</code> из Magma проводят 20 тестов Миллера — Рабина для чисел больших 34·10<sup>13</sup>, однако не используют их сочетание с тестом Люка<ref>[http://magma.maths.usyd.edu.au/magma/handbook/text/164 Magma Computational Algebra System — Primes and Primality Testing] {{Wayback|url=http://magma.maths.usyd.edu.au/magma/handbook/text/164 |date=20151003112350 }} документация по Magma.</ref>.

== Примечания ==
{{примечания}}

{{Теоретико-числовые алгоритмы}}

[[Категория:Тесты простоты]]