Тест Фробениуса — вероятностный тест простоты для проверки того, является ли число вероятно простым. Он назван в честь Фердинанда Георга Фробениуса. Тест использует понятия квадратичных многочленов и эндоморфизм Фробениуса. Тест Фробениуса ограничивает полиномы, разрешенные на основе входных данных, а также имеет другие условия, которые должны быть выполнены. Составное число, прошедшее этот тест называют псевдопростым числом Фробениуса, но обратное не обязательно верно.
Концепция
Грэнтэм поставил цель при разработке алгоритма обеспечить проверку, чтобы всегда проходили праймы и композиты (с вероятностью менее 1/7710).
Тест был позже расширен Франдсеном и Иваном Дамгардом (Ivan Bjerre Damgård) и назван расширенным квадратичным тестом Фробениуса (EQFT — extended quadratic Frobenius test).
Алгоритм
Пусть n положительное целое число, такое, что n нечетно, (b2 + 4c | n) = −1 и (−c | n) = 1, где (x | n) обозначает символ Якоби. Положим B = 50000. Тогда тест на n с параметрами (b, c) работает следующим образом:
Проверяем, является ли одно из простых чисел меньшим или равным наименьшему из двух значений B {displaystyle B} и n {displaystyle {sqrt {n}}} делим на n. Если да, то станавливаем когда n станет составным. Проверяем выполнимость n ∈ Z {displaystyle {sqrt {n}}in mathbb {Z} } . Останавливаем когда n является составным. Вычисляем x n + 1 2 mod ( n , x 2 − b x − c ) {displaystyle x^{n+1 over 2},{mod {,}}{ig (}n,x^{2}-bx-c)} . Если выполнено x n + 1 2 ∉ Z / n Z {displaystyle x^{n+1 over 2}
otin mathbb {Z} {ig /}nmathbb {Z} } , то останавливаем, поскольку n является составным. Вычисляем x n + 1 mod ( n , x 2 − b x − c ) {displaystyle x^{n+1},{mod {,}}{ig (}n,x^{2}-bx-c)} . Если выполнено x n + 1 ≢ − c {displaystyle x^{n+1}
ot equiv -c} , то останавливаем, поскольку n является составным. Пусть n 2 − 1 = 2 r s {displaystyle n^{2}-1=2^{r}s} , где s нечетно. Если выполнено x s ≢ 1 mod ( n , x 2 − b x − c ) {displaystyle x^{s}
ot equiv 1{mod {,}}{ig (}n,x^{2}-bx-c)} , и x 2 j s ≢ − 1 mod ( n , x 2 − b x − c ) {displaystyle x^{2^{j}s}
ot equiv -1{mod {,}}{ig (}n,x^{2}-bx-c)} для всех 0 ≤ j ≤ r − 2 {displaystyle 0leq jleq r-2} , то останавливаем, поскольку n является составным. Если тест не останавливается в шагах (1)-(5), то n является вероятно простым числом.
Главная