Главная
В теории чисел псевдопростым числом Фробениуса называется псевдопростое число, прошедшее трехшаговый тест принадлежности к вероятно простым числам, разработанный Джоном Грантамом (Jon Grantham) в 1996 году.
Псевдопростые числа Фробениуса определяются по отношению к заданному многочлену. Для отдельных типов многочленов псевдопростые Фробениуса связаны с другими типами псевдопростых чисел.
Пример
Псевдопростые числа Фробениуса относительно полинома x 2 − x − 1 {displaystyle x^{2}-x-1} образуют последовательность:
4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, … (последовательность A212424 в OEIS).Свойства
Хотя единичный проход теста Фробениуса медленнее единичного прохода большинства других тестов псевдопростоты, он имеет меньшую наихудшую вероятность ошибки 1 7710 {displaystyle { frac {1}{7710}}} ,, которую можно получить только семью проходами теста простоты Миллера-Рабина.
Сильные псевдопростые Фробениуса
Псевдопростое число называется сильным псевдопростым Фробениуса, если оно удовлетворяет дополнительным ограничениям.