Фробениус псевдопростой

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

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

Определение псевдопростых чисел Фробениуса относительно монического квадратичного многочлена. $x^{2}-Px+Q$, где дискриминант $D=P^{2}-4Q$ не является квадратом, может быть выражено через последовательность Люка $U_{n}(P,Q)$ и $V_{n}(P,Q)$ следующее.

n Составное число является числом Фробениуса. $(P,Q)$ псевдопростое тогда и только тогда, когда

$(1)\qquad \gcd(n,2QD)=1,$

$(2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},$ и

$(3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},$

где $\delta =\left({\tfrac {D}{n}}\right)$ — символ Якоби .

При выполнении условия (2) условие (3) становится эквивалентным

$(3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.$

Следовательно, Фробениус $(P,Q)$ псевдопростое n может быть эквивалентно определено условиями (1–2) и (3) или условиями (1–2) и (3′).

Поскольку условия (2) и (3) выполняются для всех простых чисел, удовлетворяющих простому условию (1), их можно использовать в качестве вероятного теста на простоту. (Если условие (1) не выполняется, то либо наибольший общий делитель меньше n , и в этом случае он является нетривиальным множителем, а n составным, либо НОД равен n , и в этом случае следует попробовать разные параметры P и Q, которые не кратны n .)

Отношения с другими псевдопростыми числами

Каждый Фробениус $(P,Q)$ псевдопростое тоже

• псевдопростое число Лукаса с параметрами $(P,Q)$, поскольку он определяется условиями (1) и (2);
• псевдопростое число Диксона с параметрами $(P,Q)$, поскольку он определяется условиями (1) и (3');
• псевдопростое Ферма основание $|Q|$ когда $|Q|>1$.

Обратное ни одно из этих утверждений не верно, поэтому Фробениус $(P,Q)$ псевдопростые числа - правильное подмножество каждого из наборов псевдопростых чисел Люка и псевдопростых чисел Диксона с параметрами $(P,Q)$и псевдопростые числа Ферма по основанию $|Q|$ когда $|Q|>1$. Далее следует, что для тех же параметров $(P,Q)$составное число является псевдопростым числом Фробениуса тогда и только тогда, когда оно одновременно является псевдопростым числом Люкаса и Диксона. Другими словами, для каждой фиксированной пары параметров $(P,Q)$, множество псевдопростых чисел Фробениуса равно пересечению множеств псевдопростых чисел Люка и Диксона.

Хотя каждый Фробениус $(P,Q)$ псевдопростое число — это псевдопростое число Люка, оно не обязательно является сильным псевдопростым числом Люка . Например, 6721 — первое псевдопростое число Фробениуса для $(P,Q)=(1,-1)$, что не является сильным псевдопростым числом Лукаса.

Каждое псевдопростое число Фробениуса $x^{3}-x-1$ также является ограниченным псевдопростым числом Перрена . Аналогичные утверждения справедливы и для других кубических многочленов вида $x^{3}-rx^{2}+sx-1$.

Примеры

Псевдопростые числа Фробениуса относительно многочлена Фибоначчи $x^{2}-x-1$ определяются через числа Фибоначчи $F_{n}=U_{n}(1,-1)$ и числа Лукаса $L_{n}=V_{n}(1,-1)$. Такие псевдопростые числа Фробениуса образуют последовательность:

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 75077, 90061, 96049, 97921, 100127, 11357 3, 118441, 146611, 161027, 162133, 163081, 186961, 197209, 219781,231703,252601,254321,257761,268801,272611,283361,302101,303101,330929,399001,430127,433621,438751, 48 9601, ... (последовательность A212424 в OEIS ).

В то время как 323 является первым псевдопростым числом Люка относительно многочлена Фибоначчи. $x^{2}-x-1$, первое псевдопростое число Фробениуса относительно того же многочлена равно 4181 (Грэнтэм заявил его как 5777 но многие авторы отметили, что это неверно и вместо этого является первым псевдопростым числом с $\left({\tfrac {5}{n}}\right)=-1$ для этого многочлена ).

Другой случай: псевдопростые числа Фробениуса относительно квадратичного многочлена. $x^{2}-3x-1$ можно определить с помощью Лукаса $(3,-1)$ последовательность и являются:

119, 649, 1189, 4187, 12871, 14041, 16109, 23479, 24769, 28421, 31631, 34997, 38503, 41441, 48577, 50545, 56279, 58081, 59 081, 61447, 75077, 91187, 95761, 96139, 116821, 127937,146329,148943,150281,157693,170039,180517,188501,207761,208349,244649,281017,311579,316409,349441,35 0173, 363091, 371399, 397927, 423721, 440833, 459191, 473801, 479119, 493697, ... (последовательность A327655 в OEIS )

В этом случае первое псевдопростое число Фробениуса относительно квадратичного многочлена $x^{2}-3x-1$ равно 119, что также является первым псевдопростым числом Люка относительно того же многочлена. Кроме, $\left({\tfrac {13}{119}}\right)=-1$.

Квадратичный полином $x^{2}-3x-5$, то есть $(P,Q)=(3,-5)$, имеет более редкие псевдопростые числа по сравнению со многими другими простыми квадратичными числами. Используя тот же процесс, что и выше, мы получаем последовательность:

13333, 44801, 486157, 1615681, 3125281, 4219129, 9006401, 12589081, 13404751, 15576571, 16719781, ….

Обратите внимание, что существует только 3 таких псевдопростых числа ниже 500 000, в то время как существует множество псевдопростых чисел Фробениуса (1, -1) и (3, -1) ниже 500 000.

Каждая запись в этой последовательности является псевдопростым числом Ферма по основанию 5, а также псевдопростым числом Люка (3, -5), но обратное неверно: 642 001 является одновременно псевдопростым числом psp-5 и псевдопростым числом Люка (3, -5), но не является псевдопростым числом Фробениуса (3, −5). (Обратите внимание, что псевдопростое число Люка для пары ( P , Q ) не обязательно должно быть псевдопростым числом Ферма по основанию | Q |, например, 14209 является псевдопростым числом Люка (1, −3), но не псевдопростым числом Ферма по основанию 3.)

Сильные

Также определены сильные псевдопростые числа Фробениуса. Подробности о реализации квадратичных полиномов можно найти у Крэндалла и Померанса.

Вводя ограничения, которые $\delta =-1$ и $Q\neq \pm 1$, авторы покажи как выбрать $P$ и $Q$ такое, что существует только пять нечетных составных чисел меньше $10^{15}$ для которого выполнено (3), т.е. для которого $V_{n+1}\equiv 2Q{\pmod {n}}$.

Тесты на псевдопростость

Условия, определяющие псевдопростое число Фробениуса, можно использовать для проверки данного числа n на вероятную простоту . Часто такие тесты не полагаются на фиксированные параметры. $(P,Q)$, а выбирать их определенным образом в зависимости от входного числа n, чтобы уменьшить долю ложных срабатываний , т. е. составных чисел, прошедших проверку. Иногда такие составные числа принято называть псевдопростыми числами Фробениуса, хотя они могут соответствовать разным параметрам.

Использование идей выбора параметров, впервые изложенных Бэйли и Вагстаффом (1980). как часть теста на простоту Бэйли-ПСВ и используемый Грэнтэмом в его квадратичном тесте Фробениуса , можно создать еще лучшие квадратичные тесты. В частности, было показано, что выбор параметров из квадратичных невычетов по модулю n (на основе символа Якоби ) обеспечивает гораздо более сильные тесты и является одной из причин успеха теста простоты Бэйли – PSW . Например, для параметров ( P ,2), где P — первое нечетное целое число, удовлетворяющее условию $\left({\tfrac {D}{n}}\right)=-1$, нет псевдопростых чисел ниже 2 ⁶⁴ .

Еще один тест предлагает Хашин. Для данного неквадратного числа n он сначала вычисляет параметр c как наименьшее нечетное простое число, имеющее символ Якоби. $\left({\tfrac {c}{n}}\right)=-1$, а затем проверяет соответствие:

$(1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}$.

Хотя все простые n проходят этот тест, составное n проходит его тогда и только тогда, когда n является псевдопростым числом Фробениуса для $(P,Q)=(2,1-c)$. Как и в приведенном выше примере, Хашин отмечает, что для его теста не обнаружено псевдопростых чисел. Далее он показывает, что все, что существует меньше 2 ⁶⁰ должен иметь коэффициент меньше 19 или иметь c > 128.

Свойства

Вычислительные затраты на тест псевдопростоты Фробениуса по отношению к квадратичным полиномам примерно в три раза превышают стоимость сильного теста на простоту псевдопростоты (т. е. одного раунда теста на простоту Миллера-Рабина ), в 1,5 раза больше, чем у теста псевдопростости Люка , и немного больше. чем тест на простоту Бэйли-ПСВ .

Обратите внимание, что квадратичный критерий Фробениуса сильнее критерия Люка. Например, 1763 является псевдопростым числом Люка для ( P , Q ) = (3, –1), поскольку U ₁₇₆₄ (3,–1) ≡ 0 (по модулю 1763) ( U (3,–1) задано в OEIS : A006190 ), а также проходит шаг Якоби, поскольку $\left({\tfrac {13}{1763}}\right)=-1$, но не проходит тест Фробениуса для x ² – 3 x – 1. Это свойство можно ясно увидеть, если алгоритм сформулировать, как показано в алгоритме Крэндалла и Померанса 3.6.9. или, как показал Лебенбергер, поскольку алгоритм выполняет тест Люка с последующей дополнительной проверкой условия Фробениуса.

Хотя квадратичный тест Фробениуса не имеет формальных границ ошибок, кроме теста Люка, его можно использовать в качестве основы для методов с гораздо меньшими границами ошибок. Обратите внимание, что здесь требуется больше шагов, дополнительных требований и немаловажных дополнительных вычислений, помимо описанных на этой странице. Важно отметить, что границы ошибок для этих методов не применимы к стандартным или сильным тестам Фробениуса с фиксированными значениями (P,Q), описанным на этой странице.

На основе этой идеи псевдопростых чисел можно построить алгоритмы с сильными границами ошибок в худшем случае. Квадратичный тест Фробениуса . используя квадратичный критерий Фробениуса плюс другие условия, имеет границу ${\tfrac {1}{7710}}$. Мюллер в 2001 году предложил тест MQFT с границами, по существу, ${\tfrac {1}{131040^{t}}}$. Дамгорд и Франдсен в 2003 году предложили EQFT с привязкой, по существу, к ${\tfrac {256}{{331776}^{t}}}$. Сейсен в 2005 году предложил тест SQFT с границей ${\tfrac {1}{{4096}^{t}}}$ и тест SQFT3 с границей ${\tfrac {16}{336442^{t}}}$.

При тех же вычислительных затратах они обеспечивают лучшие оценки для наихудшего случая, чем обычно используемый тест простоты Миллера-Рабина .

См. также

• Псевдопростой
• Лукас псевдопростой
• Фердинанд Георг Фробениус
• Квадратичный критерий Фробениуса

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

• Вайсштейн, Эрик В. «Фробениус Псевдопростой» . Математический мир .
• Вайсштейн, Эрик В. «Сильный Фробениус Псевдопростой» . Математический мир .
• Якобсен, Дана Статистика, таблицы и данные псевдопростых чисел (данные для псевдопростых чисел Фробениуса (1,-1) и (3,-5))