Псевдопростое число Фробениуса

В теории чисел псевдопростым числом Фробениуса называется псевдопростое число, прошедшее трехшаговый тест принадлежности к вероятно простым числам, разработанный Джоном Грантамом (Jon Grantham) в 1996 году.

Псевдопростые числа Фробениуса определяются по отношению к заданному многочлену. Для отдельных типов многочленов псевдопростые Фробениуса связаны с другими типами псевдопростых чисел.

Пример

Псевдопростые числа Фробениуса относительно полинома $x^2-x-1$ образуют последовательность:

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, … (Шаблон:OEIS).

Свойства

Хотя единичный проход теста Фробениуса медленнее единичного прохода большинства других тестов псевдопростоты, он имеет меньшую наихудшую вероятность ошибки $\frac{1}{7710}$,, которую можно получить только семью проходами теста простоты Миллера-Рабина.

Сильные псевдопростые Фробениуса

Псевдопростое число называется сильным псевдопростым Фробениуса, если оно удовлетворяет дополнительным ограничениям.

См. также

• Псевдопростое число
• Фердинанд Георг Фробениус

Ссылки

• Шаблон:Книга

Внешние ссылки

• Symmetric Pseudoprimes, MathPages.