Метод простоты Фробениуса

Проверить информацию. Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье. На странице обсуждения должны быть пояснения.

Тест простоты Фробениуса — вероятностный тест простоты натурального числа 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}}$ элементов. Доказательство этого утверждения здесь рассматриваться не будет, поскольку это требует достаточно громоздких вычислений, целесообразнее смотреть их в оригинальной статье.^[1]
• Так же существует гипотеза Фробениуса, которая утверждает, что псевдопростых чисел по Фробениусу не существует. Другими словами, тест Фробениуса никогда не ошибается.

Квадратичные иррациональности[править | править код]

Для более четкого понимания алгоритма теста простоты Фробениуса рассмотрим такое понятие как квадратичные иррациональности и их свойства. Квадратичной иррациональностью будем называть число ${\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. A Simplified Quadratic Frobenius Primality Test // 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)