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

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

История

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

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

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

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

Свойства

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

Пример

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

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

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

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

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

Упрощенный принцип работы алгоритма

Пусть n – нечетное натуральное число, свободное от квадратов.
Обозначим через c наименьшее среди чисел [-1,2,3,5,7,11,...] такое, что символ Якоби $jacobi(c/n)=-1$ .
Если $c\leq 2$ , то положим $z=2+{\sqrt {c}}$ , иначе $z=1+{\sqrt {c}}$ .
Определение: назовем число n простым по Фробениусу, если $z^{n}\equiv {\bar {z}}\mod n$ .
Назовем число псевдопростым по Фробениусу, если оно составное, но просто по Фробениусу.

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

Примеры

Пример 1:

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

Пример 2:

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

Пример 3:

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

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

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

Примечания

Seysen, 2005, pp. 11—12.

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_cb97c43c7cb022a6-1] Seysen, 2005, pp. 11—12.

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина