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

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

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

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

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

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

Если ${\displaystyle n}$ — псевдопростое по некоторому основанию ${\displaystyle a}$, то ${\displaystyle n}$, вероятно, является псевдопростым и по многим другим основаниям[11].

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

Поэтому, если ${\displaystyle n}$ — псевдопросто по основанию ${\displaystyle a}$, высока вероятность того, что ${\displaystyle 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-гладким). Арнольд[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 и более битов, этот метод также проводит тест Люка, который проверяет, что ${\displaystyle U_{n+1}=-{\pmod {n}}}$[19][20]. Использование случайных оснований в тестах Миллера — Рабина имеет как преимущества, так и недостатки по сравнению с проверкой лишь по основанию 2, как в тесте БПСВ. Преимуществом использования случайных оснований является то, что можно получить вероятностную оценку того, что n является составным. Недостатком является то, что, в отличие от теста БПСВ, нельзя с уверенностью сказать, что если n меньше, чем некоторая фиксированная граница, например 2⁶⁴, то 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·10¹³, однако не используют их сочетание с тестом Люка[26].