Псевдопростое число Фробениуса (Hvyf;khjkvmky cnvlk SjkQyunrvg)
В теории чисел псевдопростым числом Фробениуса называется псевдопростое число, прошедшее трехшаговый тест принадлежности к вероятно простым числам, разработанный Джоном Грантамом (Jon Grantham) в 1996 году.[1][2]
Псевдопростые числа Фробениуса определяются по отношению к заданному многочлену. Для отдельных типов многочленов псевдопростые Фробениуса связаны с другими типами псевдопростых чисел.
Пример
[править | править код]Псевдопростые числа Фробениуса относительно полинома образуют последовательность:
Свойства
[править | править код]Хотя единичный проход теста Фробениуса медленнее единичного прохода большинства других тестов псевдопростоты, он имеет меньшую наихудшую вероятность ошибки ,[1], которую можно получить только семью проходами теста простоты Миллера-Рабина.
Сильные псевдопростые Фробениуса
[править | править код]Псевдопростое число называется сильным псевдопростым Фробениуса, если оно удовлетворяет дополнительным ограничениям.[3]
См. также
[править | править код]Ссылки
[править | править код]- ↑ 1 2 Weisstein, Eric W. Frobenius pseudoprime (англ.) на сайте Wolfram MathWorld.
- ↑ Jon Grantham. Frobenius pseudoprimes (англ.) // Mathematics of Computation[англ.] : journal. — 2001. — Vol. 70, no. 234. — P. 873—891. — doi:10.1090/S0025-5718-00-01197-2.
- ↑ Weisstein, Eric W. Strong Frobenius pseudoprime (англ.) на сайте Wolfram MathWorld.
- R. Crandall, C. B. Pomerance. Prime Numbers: A Computational Perspective (англ.). — 2nd ed.. — Springer, 2005. — P. 613. — ISBN 9780387252827.
Внешние ссылки
[править | править код]- Symmetric Pseudoprimes, MathPages.
![]() | В другом языковом разделе есть более полная статья Frobenius pseudoprime (англ.). |
Для улучшения этой статьи желательно:
|