Введение

В теории чисел псевдопервичное число Фробена — это псевдопервичное число, определение которого вдохновлено квадратичным тестом Фробена, описанным Джоном Грантемом в препринте 1998 года и опубликованном в 2000 году. Псевдопервичные числа Фробена могут быть определены относительно многочленов степени не менее 2, но наиболее полно они исследованы в случае квадратичных многочленов.

Испытания псевдопримальности

Условия, определяющие псевдопростые числа Фробениуса, могут быть использованы для проверки вероятной простоты данного числа n. Часто такие тесты не опираются на фиксированные параметры, а скорее выбирают их определенным образом в зависимости от входного числа n, чтобы уменьшить долю ложноположительных результатов, то есть составных чисел, проходящих тест. Иногда такие составные числа обычно называют псевдопростыми числами Фробениуса, хотя они могут соответствовать различным параметрам. Используя идеи выбора параметров, впервые представленные в Baillie и Wagstaff (1980) как часть теста простоты Baillie–PSW и использованные Grantham в его квадратичном тесте Фробениуса, можно создать еще более эффективные квадратичные тесты. В частности, было показано, что выбор параметров из квадратичных невычетов по модулю n (на основе символа Якоби) создает значительно более надежные тесты, и является одной из причин успеха теста простоты Baillie–PSW. Например, для параметров (P, 2), где P – первое нечетное целое число, удовлетворяющее , псевдопростых чисел ниже 264 не существует. Khashin предлагает еще один тест. Для данного числа n, не являющегося полным квадратом, он сначала вычисляет параметр c как наименьшее нечетное простое число, имеющее символ Якоби , а затем проверяет следующее сравнение: в то время как все простые числа n проходят этот тест, составное число n проходит его тогда и только тогда, когда n является псевдопростым числом Фробениуса для . Аналогично приведенному выше примеру, Khashin отмечает, что для его теста не было найдено ни одного псевдопростого числа. Он также показывает, что любое такое число, меньшее 260, должно иметь делитель меньше 19 или c > 128.

Свойства

Расчетная стоимость теста псевдопервенства Фробениуса по отношению к квадратным многочленам примерно в три раза превышает стоимость сильного теста псевдопервенства (т. е. одного раунда теста первенства Миллера — Рэбина), в 1,5 раза превышает стоимость теста псевдопервенства Лукаса и незначительно больше, чем тест первенства Бейли — ПСВ. Следует отметить, что квадратный тест Фробениуса сильнее, чем тест Лукаса. Например, 1763 является псевдопервичным числом Лукаса для (P, Q) = (3, –1), поскольку U1764(3, –1) ≡ 0 (mod 1763) (U(3, –1) приведено в ), и оно также проходит шаг Якоби, но не проходит тест Фробениуса для x² – 3x – 1. Это свойство становится очевидным, когда алгоритм представлен в форме, описанной в алгоритме 3.6.9 Крандэлла и Померанса. Дамгард и Франдсен в 2003 году предложили EQFT с границей, по существу равной , а Сейзен в 2005 году предложил тест SQFT с границей и тест SQFT3 с границей. При одинаковых вычислительных затратах эти тесты обеспечивают лучшие границы в худшем случае, чем обычно используемый тест первенства Миллера — Рэбина.