Тест Фробениуса

Тест Фробениуса — вероятностный тест простоты для проверки того, является ли число вероятно простым. Он назван в честь Фердинанда Георга Фробениуса. Тест использует понятия квадратичных многочленов и эндоморфизм Фробениуса. Тест Фробениуса ограничивает полиномы, разрешённые на основе входных данных, а также имеет другие условия, которые должны быть выполнены. Составное число, прошедшее этот тест, называют псевдопростым числом Фробениуса, но обратное не обязательно верно.

Концепция править

Грэнтэм поставил цель при разработке алгоритма обеспечить проверку, чтобы всегда проходили праймы и композиты (с вероятностью менее 1/7710)^[1]^:33.

Тест был позже расширен Франдсеном и Иваном Дамгардом (Ivan Bjerre Damgård) и назван расширенным квадратичным тестом Фробениуса (EQFT — extended quadratic Frobenius test)^[2].

Алгоритм править

Пусть n положительное целое число, такое, что n нечётно, (b² + 4c | n) = −1 и (−c | n) = 1, где (x | n) обозначает символ Якоби. Положим B = 50000. Тогда тест на n с параметрами (b, c) работает следующим образом:

Проверяем, является ли одно из простых чисел меньшим или равным наименьшему из двух значений $B$ и ${\sqrt {n}}$ делим на n. Если да, то останавливаем когда n станет составным.
Проверяем выполнимость ${\sqrt {n}}\in \mathbb {Z}$ . Останавливаем когда n является составным.
Вычисляем $x^{n+1 \over 2}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)$ . Если выполнено $x^{n+1 \over 2}\notin \mathbb {Z} {\big /}n\mathbb {Z}$ , то останавливаем, поскольку n является составным.
Вычисляем $x^{n+1}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)$ . Если выполнено $x^{n+1}\not \equiv -c$ , то останавливаем, поскольку n является составным.
Пусть $n^{2}-1=2^{r}s$ , где s нечетно. Если выполнено $x^{s}\not \equiv 1{\bmod {\,}}{\big (}n,x^{2}-bx-c)$ , и $x^{2^{j}s}\not \equiv -1{\bmod {\,}}{\big (}n,x^{2}-bx-c)$ для всех $0\leq j\leq r-2$ , то останавливаем, поскольку n является составным.