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

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


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

 .
 Мощность теста состоит в том, что не существует известных пересеченийсписков псевдопростых чисел Ферма и псевдопростых чисел Люка. Существуютоснования полагать, что в эти списки попадают, как правило, различныетипы чисел. Например, псевдопростые по основанию 2, как правило,попадают в класс вычетов 1 по модулю m для многих малых m, в то времякак псевдопростые числа Люка, как правило, попадают в класс вычетов −1по модулю m. В результате число, которое проходит как сильный тестФерма, так и сильное испытание Люка, с большой вероятностью будетпростым.
 Ни одно составное число, меньшее 264 (что примерноравно 1,845 · 1019), не проходит тест БПСВ. Такимобразом, этот тест можно считать детерминированным тестом простоты длячисел, меньших указанной границы. Также пока не известно ни односоставное число, большее границы, которое проходит тест.
 В 1980 году Померанц, Селфридж и Вагстафф предложили вознаграждение вразмере \$30 тому, кто отыщет контрпример, то есть найдет составноечисло, которое проходит этот тест. Ричард Гай ошибочно полагал, чторазмер вознаграждения составляет \$620, но он перепуталпоследовательности Люка и Фибоначчи, и его замечания оказались применимылишь к одной гипотезе Селфриджа. По состоянию на июнь 2014 года приз таки не был востребован. Тем не менее, эвристический аргумент Померанцауказывает на то, что таких контрпримеров существует бесконечно много.Кроме того, Чен и Грин
 \textttпостроили множество S, состоящее из 1248 таких простых чисел, что среди 2\texttt1248\texttt произведений различных простых чисел из S может быть около 740 контрпримеров. Однако, они рассматривали более слабый БПСВ-тест, который вместо теста Люка использует тест Фибоначчи.

Алгоритм


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

  1. По желанию провести перебор простых делителей, меньших заданной верхней границы.
  2. Произвести сильную проверку на простоту по основанию 2. Если n не является сильно вероятно простым по основанию 2, то n является составным; на этом проверка завершается.
  3. Найти первое D в последовательности 5, −7, 9, −11, 13, −15, \ldots, для которого символ Якоби (D/n) равен −1. Положим P=1 и Q=(1D)/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±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·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-гладким). Арнольд предъявляет 397-значное составноечисло N, который является сильным псевдопростым по всем основаниям,меньшим 307. (и по всем 293-гладким). Поскольку N является числомКармайкла, N также будет (не обязательно сильно) псевдопростым по всемоснованим меньшим р, где р — наименьший 131-значный простой делительN. В то же время, быстрый подсчет показывает, что N не являетсяпсевдопоростым числом Люка, если D, P, Q были выбраны методом, описаннымвыше, таким образом тест БПСВ определит, что это число составное.

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


 Нижеперечисленные компьютерные системы и программные пакеты используютразличные версии теста БПСВ.
 Функции \textttIsPrime в Maple, \textttPrimeQ в Mathematica,\textttis\_pseudoprime в Sage и функции \textttisprime и\textttispseudoprime в используют сочетание теста Миллера — Рабина(сильного теста Ферма) и теста Люка. Функция \textttPrimep в Maximaиспользует такой тест для чисел, превосходящих 341550071728321.
 В библиотеке содержатся функции \textttn\_is\_probabprime и\textttn\_is\_probabprime\_BPSW, которые используют комбинированныйтест, а также другие функции, которые используют испытания Ферма и Люкапо отдельности.
 Класс \textttBigInteger в стандартных версиях Java и в версиях соткрытым исходным кодом, таких как OpenJDK, имеет метод\textttisProbablePrime. Этот метод проводит один или несколько тестовМиллера — Рабина по случайными основаниям. Если проверяемое числосодержит 100 и более битов, этот метод также проводит тест Люка, которыйпроверяет, что Un+1=(modn). Использование случайных оснований втестах Миллера — Рабина имеет как преимущества, так и недостатки посравнению с проверкой лишь по основанию 2, как в тесте БПСВ.Преимуществом использования случайных оснований является то, что можнополучить вероятностную оценку того, что n является составным.Недостатком является то, что, в отличие от теста БПСВ, нельзя суверенностью сказать, что если n меньше, чем некоторая фиксированнаяграница, например 264, то n является простым.
 В языке Perl модули \textttMath::Primality и\textttMath::Prime::Util содержат функции для выполнения сильноготеста БПСВ, а также отдельные функции для сильного теста напсевдопростоту и сильного теста Люка. Библиотека NZMATH языка Pythonсодержит сильный тест на псевдопростоту и сильный тест Люка, но несодержит их комбинации.
 Функция \textttmpz\_probab\_prime\_p из GNU Multiple PrecisionArithmetic Library использует тест Миллера — Рабина, но не используеттест Люка. Функции \textttIsProbablePrime и \textttIsProbablyPrimeиз Magma проводят 20 тестов Миллера — Рабина для чисел больших34·1013, однако не используют их сочетание с тестомЛюка.