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

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

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

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

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

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

Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка. Существуют основания полагать, что в эти списки попадают, как правило, различные типы чисел. Например, псевдопростые по основанию 2, как правило, попадают в класс вычетов 1 по модулю m для многих малых m, в то время как псевдопростые числа Люка, как правило, попадают в класс вычетов −1 по модулю $m$. В результате число, которое проходит как сильный тест Ферма, так и сильное испытание Люка, с большой вероятностью будет простым.

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

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

Алгоритм

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

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

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

1. Первый этап лишь повышает эффективность. Тест БПСВ работает и без этого шага, однако, если $n$ имеет небольшие простые делители, то самый быстрый способ показать, что $n$ является составным — найти такой делитель серией проверок.
2. На втором этапе однократно применяется тест Миллера — Рабина на простоту. Выбор основания не влияет на эффективность конкретной проверки. Однако, многочисленные исследования показали, что сочетание сильного теста на простоту именно по основанию 2 и сильного теста Люка на простоту показывает хорошие результаты в проверке чисел на простоту.
3. Бейли и Уогстафф доказали, что среднее количество $D$, которое необходимо перебрать, примерно равно 3,147755149.
4. Если $n$ является полным квадратом, то на этапе 3 никогда не найдется $D$, такое что $(D/n)=-1$; однако, это не станет проблемой, поскольку полные квадраты легко обнаружить при помощью метода Ньютона для квадратных корней. Если на шаге 3 не удается найти $D$ за короткое время, следует проверить, является ли $n$ полным квадратом.
5. Для заданного $n$ существуют и другие методы подбора коэффициентов . Важно то, что символ Якоби $(D/n)$ должен быть равен −1. Брессон и Вэгон доказали, что для эффективности тестирования символ Якоби должен быть равен −1, а значение $Q\neq \pm 1$.

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

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

Если $n$ — псевдопростое по некоторому основанию $a$, то $n$, вероятно, является псевдопростым и по многим другим основаниям.

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

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

• 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⁶⁴, упомянутые выше, говорят о том, что тесты Ферма и Люка являются независимыми, таким образом, комбинация этих тестов является мощным тестом на простоту, особенно при использовании сильных форм этих тестов.

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

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

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

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

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

Класс BigInteger в стандартных версиях Java и в версиях с открытым исходным кодом, таких как OpenJDK, имеет метод isProbablePrime. Этот метод проводит один или несколько тестов Миллера — Рабина по случайными основаниям. Если проверяемое число содержит 100 и более битов, этот метод также проводит тест Люка, который проверяет, что $U_{n+1}=-{\pmod {n}}$. Использование случайных оснований в тестах Миллера — Рабина имеет как преимущества, так и недостатки по сравнению с проверкой лишь по основанию 2, как в тесте БПСВ. Преимуществом использования случайных оснований является то, что можно получить вероятностную оценку того, что n является составным. Недостатком является то, что, в отличие от теста БПСВ, нельзя с уверенностью сказать, что если n меньше, чем некоторая фиксированная граница, например 2⁶⁴, то n является простым.

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

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