Тест Фробениуса
Тест Фробениуса — вероятностный тест простоты для проверки того, является ли число вероятно простым. Он назван в честь Фердинанда Георга Фробениуса. Тест использует понятия квадратичных многочленов и эндоморфизм Фробениуса. Тест Фробениуса ограничивает полиномы, разрешённые на основе входных данных, а также имеет другие условия, которые должны быть выполнены. Составное число, прошедшее этот тест, называют псевдопростым числом Фробениуса, но обратное не обязательно верно.
Концепция
[править | править код]Грэнтэм поставил цель при разработке алгоритма обеспечить проверку, чтобы всегда проходили праймы и композиты (с вероятностью менее 1/7710)[1]:33.
Тест был позже расширен Франдсеном и Иваном Дамгардом (Ivan Bjerre Damgård) и назван расширенным квадратичным тестом Фробениуса (EQFT — extended quadratic Frobenius test)[2].
Алгоритм
[править | править код]Пусть n положительное целое число, такое, что n нечётно, (b2 + 4c | n) = −1 и (−c | n) = 1, где (x | n) обозначает символ Якоби. Положим B = 50000. Тогда тест на n с параметрами (b, c) работает следующим образом:
- Проверяем, является ли одно из простых чисел меньшим или равным наименьшему из двух значений и делим на n. Если да, то останавливаем когда n станет составным.
- Проверяем выполнимость . Останавливаем когда n является составным.
- Вычисляем . Если выполнено , то останавливаем, поскольку n является составным.
- Вычисляем . Если выполнено , то останавливаем, поскольку n является составным.
- Пусть , где s нечетно. Если выполнено , и для всех , то останавливаем, поскольку n является составным.
Если тест не останавливается в шагах (1)-(5), то n является вероятно простым числом.
См. также
[править | править код]Примечания
[править | править код]- ↑ Grantham, J. A Probable Prime Test With High Confidence (англ.) // Journal of Number Theory : journal. — Academic Press, 1998. — Vol. 72, no. 1. — P. 32—47. — doi:10.1006/jnth.1998.2247. Архивировано 29 сентября 2015 года.
- ↑ Damgård, Ivan Bjerre[англ.]; Frandsen, Gudmund Skovbjerg. An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates (англ.) // Lecture Notes in Computer Science : journal. — Springer Berlin Heidelberg, 2003. — Vol. Fundamentals of Computation Theory. — P. 118—131. — ISBN 978-3-540-45077-1. — ISSN 1611-3349. — doi:10.1007/978-3-540-45077-1_12. (недоступная ссылка)
На эту статью не ссылаются другие статьи Википедии. |