Русская Википедия:Тест Фробениуса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Концепция

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

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

Алгоритм

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

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

Если тест не останавливается в шагах (1)-(5), то n является вероятно простым числом.

См. также

• Сравнение по модулю
• Мультипликативная группа кольца вычетов