Тест простоты Фробениуса — это вероятностный тест простоты натурального числа n . Тест простоты Фробениуса позволяет с наибольшей вероятностью определить простоту числа. Доказано, что для чисел меньших ${\displaystyle 2^{60}}$ тест простоты Фробениуса выполняется всегда.

История

Тест простоты Фробениуса был разработан Джоном Грантамом в 1996 году. Он основывается на одноименной теореме.

• Теорема Фробениуса: Пусть ${\displaystyle n}$ — простое число , символ Якоби ${\displaystyle \left({\frac {a}{n}}\right)=-1}$ и ${\displaystyle z}$ принадлежит ${\displaystyle Z_{n}({\sqrt {c}})}$ , тогда выполняется равенство ${\displaystyle z^{n}\ mod\ n={\bar {z}}}$ , где ${\displaystyle Z_{n}({\sqrt {c}})}$ — это поле Галуа из ${\displaystyle n^{2}}$ элементов. Доказательство этого утверждения здесь рассматриваться не будет, поскольку это требует достаточно громоздких вычислений, целесообразнее смотреть их в оригинальной статье.
• Так же существует гипотеза Фробениуса, которая утверждает, что псевдопростых чисел по Фробениусу не существует. Другими словами, тест Фробениуса никогда не ошибается.

Квадратичные иррациональности

Для более четкого понимания алгоритма теста простоты Фробениуса рассмотрим такое понятие как квадратичные иррациональности и их свойства. Квадратичной иррациональностью будем называть число ${\displaystyle z=a+b{\sqrt {c}}}$ , где ${\displaystyle a,b,c}$ — целые числа, причем ${\displaystyle c}$ свободно от квадратов . Сопряженным числом будет являться число вида ${\displaystyle {\bar {z}}=a-b{\sqrt {c}}}$ . Так же делением по модулю ${\displaystyle n}$ определим операцию ${\displaystyle z{\bmod {n}}=(a{\bmod {n}})+(b{\bmod {n}}){\sqrt {c}}}$ . Норму квадратичной иррациональности определим как целое число ${\displaystyle N(z)=z{\overline {z}}=a^{2}-b^{2}c}$ .

Свойства

1. Сопряжение мультипликативно: ${\displaystyle {\overline {z_{1}z_{2}}}={\overline {z_{1}}}{\overline {z_{2}}}}$
2. Норма мультипликативна : ${\displaystyle N(z_{1}z_{2})=N(z_{1})N(z_{2})}$
3. ${\displaystyle N(z{\bmod {n}})=N(z){\bmod {n}}}$

Пример

• Пусть ${\displaystyle z=1+{\sqrt {3}}}$ , тогда ${\displaystyle {\overline {z}}=1-{\sqrt {3}}}$ .
• Норма ${\displaystyle N(z)=N({\overline {z}})=-2}$ .
• Вычислим, например, ${\displaystyle z^{11}=31648+18272{\sqrt {3}}}$ .
• Норма будет равна ${\displaystyle N(z^{11})=-2048=(-2)^{11}}$ . Видим, что данное равенство удовлетворяет свойству мультипликативности нормы.
• Также вычислим ${\displaystyle z^{11}{\bmod {\ }}15}$ . Легко проверить, что это будет равно ${\displaystyle 13+2{\sqrt {3}}}$ .

Алгоритм Фробениуса

В общем смысле вероятностный тест простоты Фробениуса нечетного натурального числа n заключается в подборе таких квадратичных иррациональностей вида ${\displaystyle z=a+b*{\sqrt {c}}}$ , что a , b , c взаимно просты с n и выполняются условия:

• ${\displaystyle a^{2}-b^{2}*c\neq (0,1)\mod n}$
• Символ Якоби ${\displaystyle jacobi(c/n)=-1}$ .

Тогда если ${\displaystyle z^{n}\equiv {\bar {z}}\mod n}$ , то число n скорее всего простое. Как и в других вероятностных тестах для повышения надежности можно было бы потребовать выполнить этот тест для нескольких пар чисел a и b , но это излишне. Поэтому в дальнейшем будем рассматривать упрощенный принцип работы алгоритма теста простоты Фробениуса.

На данный момент неизвестно ни одного числа, псевдопростого по Фробениусу, причем доказано, что таких чисел нет среди меньших ${\displaystyle 2^{60}}$ .

Примеры

Пример 1:

• Первый шаг: Пусть ${\displaystyle n=19}$ . Тогда ${\displaystyle c=-1}$ , следовательно ${\displaystyle z=2+i}$ и ${\displaystyle {\bar {z}}=2-i}$ .
• Второй шаг: ${\displaystyle z^{n}\equiv (2+i)^{19}\equiv -3565918+2521451*i}$ .
• Третий шаг: ${\displaystyle z^{n}\ mod\ n\equiv (2-i)\mod n\equiv {\bar {z}}}$ .
• Вывод: ${\displaystyle n=19}$ — простое число.

Пример 2:

• Первый шаг: Пусть ${\displaystyle n=33}$ . Тогда ${\displaystyle c=-1}$ , следовательно ${\displaystyle z=2+i}$ и ${\displaystyle {\bar {z}}=2-i}$ .
• Второй шаг: ${\displaystyle z^{n}\equiv (2+i)^{33}\equiv -313245345598+135250416961*i}$ .
• Третий шаг: ${\displaystyle z^{n}\ mod\ n\equiv (2+22*i)\mod n\neq {\bar {z}}}$ .
• Вывод: ${\displaystyle n=33}$ — составное число .

Пример 3:

• Первый шаг: Пусть ${\displaystyle n=17}$ . Тогда ${\displaystyle c=3}$ , следовательно ${\displaystyle z=1+{\sqrt {3}}}$ и ${\displaystyle {\bar {z}}=1-{\sqrt {3}}}$ .
• Второй шаг: ${\displaystyle z^{n}\equiv (1+{\sqrt {3}})^{17}\equiv 13160704+7598336*{\sqrt {3}}}$ .
• Третий шаг: ${\displaystyle z^{n}\ mod\ n\equiv (1-{\sqrt {3}})\mod n\equiv {\bar {z}}}$ .
• Вывод: ${\displaystyle n=17}$ — простое число.

Применение в криптографии

Многие криптосистемы требуют построения сильных простых чисел. Так как вероятность ошибки теста простоты Фробениуса составляет ${\displaystyle 7710^{-1}}$ , причем при выборе случайных a и b в квадратичных иррациональностях k раз вероятность ошибки уменьшается до ${\displaystyle 7710^{-k}}$ . Доказано, что для чисел вида ${\displaystyle n\equiv 1\mod 4}$ вероятность ошибки составляет ${\displaystyle 2^{-17}}$ . Это позволяет использовать тест простоты Фробениуса в качестве одного из базовых тестов для построения достоверно простых чисел, использующихся в криптографических приложениях и требующих повышенной стойкости.

Примечания

Литература

• M. Seysen. // Cryptology ePrint Archive. — 2005. — P. 4—13.
• Jon Grantham (2001). «Frobenius pseudoprimes». Mathematics of Computation 70 (234): 873—891. doi:10.1090/S0025-5718-00-01197-2.
• S.Khashin. Counterexamples for Frobenius primality test.
• И.Горбенко. Тестирование чисел на простоту: теория и практика. УДК 681.3.06:519.248.681

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 18 апреля 2018 )