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

В теории чисел псевдопростое число Фробениуса — это псевдопростое число , определение которого было вдохновлено квадратичным тестом Фробениуса, описанным Джоном Грэнтемом в препринте 1998 года и опубликованным в 2000 году. ^{[1] [2]} Псевдопростые числа Фробениуса можно определить относительно многочленов степени не ниже 2, но наиболее подробно они изучались в случае квадратичных многочленов . ^{[3] [4]}

Псевдопростые числа Фробениуса относительно квадратичных многочленов

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

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

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

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

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

где находится символ Якоби . ${\displaystyle \delta =\left({\tfrac {D}{n}}\right)}$

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

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

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

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

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

Каждое псевдопростое число Фробениуса также ${\displaystyle (P,Q)}$

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

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

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

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

Примеры

Псевдопростые числа Фробениуса относительно полинома Фибоначчи определяются через числа Фибоначчи и числа Люка . Такие псевдопростые числа Фробениуса образуют последовательность: ${\displaystyle x^{2}-x-1}$ ${\displaystyle F_{n}=U_{n}(1,-1)}$ ${\displaystyle 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, 489601, ... (последовательность A212424 в OEIS ).

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

В другом случае псевдопростые числа Фробениуса относительно квадратичного многочлена можно определить с помощью последовательности Люка: ${\displaystyle x^{2}-3x-1}$ ${\displaystyle (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, 350173, 363091, 371399, 397927, 423721, 440833, 459191, 473801, 479119, 493697, ... (последовательность A327655 в OEIS )

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

Квадратичный многочлен , то есть , имеет более редкие псевдопростые числа по сравнению со многими другими простыми квадратичными числами. Используя тот же процесс, что и выше, мы получаем последовательность: ${\displaystyle x^{2}-3x-5}$ ${\displaystyle (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.)

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

Также определены сильные псевдопростые числа Фробениуса. ^[2] Подробности реализации для квадратичных многочленов можно найти в Crandall and Pomerance. ^[3]

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

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

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

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

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

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

В то время как все простые n проходят этот тест, составное n проходит его тогда и только тогда, когда n является псевдопростым числом Фробениуса для . Подобно приведенному выше примеру, Хашин отмечает, что для его теста не было найдено ни одного псевдопростого числа. Он также показывает, что любое число, которое существует под 2 ^60, должно иметь множитель меньше 19 или иметь c > 128. ${\displaystyle (P,Q)=(2,1-c)}$

Характеристики

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

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

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

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

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

Смотрите также

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

Ссылки

1. Грэнтем, Джон (1998). Псевдопростые числа Фробениуса (Отчет). Препринт.
2. Grantham, Jon (2001). "Псевдопростые числа Фробениуса". Mathematics of Computation . 70 (234): 873–891. arXiv : 1903.06820 . Bibcode :2001MaCom..70..873G. doi : 10.1090/S0025-5718-00-01197-2 .
3. Crandall, Richard ; Pomerance, Carl (2005). Простые числа: вычислительная перспектива (2-е изд.). Springer-Verlag . ISBN 978-0-387-25282-7.
4. Loebenberger, Daniel (2008). "Простой вывод для теста Фробениуса на псевдопростые числа" (PDF) . Архив IACR Cryptology ePrint . 2008 .
5. Роткевич, Анджей (2003). «Псевдопростые числа Лукаса и Фробениуса» (PDF) . Annales Mathematicae Silesianae . 17 . Wydawnictwo Uniwersytetu Śląskiego: 17–39.
6. Роберт Бейли; Эндрю Фиори; Сэмюэл С. Вагстафф-младший (июль 2021 г.). «Усиление теста простоты Бейли-ПСВ». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . doi : 10.1090/mcom/3616. ISSN  0025-5718. S2CID  220055722.
7. Бейли, Роберт; Вагстафф, Сэмюэл С. младший (октябрь 1980 г.). «Псевдопростые числа Лукаса» (PDF) . Математика вычислений . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR  0583518.
8. Grantham, Jon (1998). «Вероятный простой тест с высокой степенью уверенности». Журнал теории чисел . 72 (1): 32–47. arXiv : 1903.06823 . CiteSeerX 10.1.1.56.8827 . doi : 10.1006/jnth.1998.2247. S2CID  119640473. 
9. Хашин, Сергей (июль 2013 г.). «Контрпримеры для теста Фробениуса на простоту». arXiv : 1307.7920 [math.NT].
10. Мюллер, Сигуна (2001). «Вероятный простой тест с очень высокой степенью уверенности для N Equiv 1 Mod 4». Труды 7-й Международной конференции по теории и применению криптологии и информационной безопасности: достижения в криптологии . ASIACRYPT. стр. 87–106. doi : 10.1007/3-540-45682-1_6 . ISBN 3-540-42987-5.
11. Дамгорд, Иван Бьерре ; Франдсен, Гудмунд Сковбьерг (октябрь 2006 г.). «Расширенный квадратичный тест на простоту Фробениуса с оценкой ошибки в среднем и наихудшем случае» (PDF) . Журнал криптологии . 19 (4): 489–520. doi : 10.1007/s00145-006-0332-x. S2CID  34417193.
12. Сейсен, Мартин. Упрощенный квадратичный тест Фробениуса на простоту, 2005.

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

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