Просмотр кода страницы Метод простоты Фробениуса

{{Проверить факты|дата=2017-04-11}}
'''Тест простоты Фробениуса''' — вероятностный [[тест простоты]] натурального числа '''n'''. Тест простоты [[Фердинанд Георг Фробениус|Фробениуса]] позволяет с наибольшей вероятностью определить простоту числа. Доказано, что для чисел меньших <math>2^{60}</math> тест простоты Фробениуса выполняется всегда.

== История ==
Тест простоты Фробениуса был разработан Джоном Грантамом в 1996 году. Он основывается на одноименной теореме.
* '''Теорема Фробениуса:''' Пусть <math>n</math> — [[простое число]], [[символ Якоби]] <math>\left(\frac{a}{n}\right)=-1</math> и <math>z</math> принадлежит <math>Z_n(\sqrt{c})</math>, тогда выполняется равенство <math> z^n \ mod \ n =  \bar{z}</math>, где <math>Z_n(\sqrt{c})</math> — это [[Конечное поле|поле Галуа]] из <math>n^2</math> элементов. Доказательство этого утверждения здесь рассматриваться не будет, поскольку это требует достаточно громоздких вычислений, целесообразнее смотреть их в оригинальной статье.{{sfn|Seysen|2005|pp = 11—12}}
* Так же существует [[гипотеза]] Фробениуса, которая утверждает, что [[Псевдопростое число|псевдопростых чисел]] по Фробениусу не существует. Другими словами, тест Фробениуса никогда не ошибается.

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

=== Свойства ===
# Сопряжение мультипликативно: <math>\overline{z_1 z_2} = \overline{z_1}  \overline{z_2}</math>
# Норма [[Мультипликативная функция|мультипликативна]]: <math>N(z_1 z_2)=N(z_1) N(z_2)</math>
# <math>N(z\bmod n)=N(z)\bmod n</math>

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

== Алгоритм Фробениуса ==
В общем смысле вероятностный тест простоты Фробениуса нечетного натурального числа '''n''' заключается в подборе таких квадратичных иррациональностей вида <math>z=a+b*\sqrt{c}</math>, что '''a''', '''b''', '''c''' [[Взаимно простые числа|взаимно просты]] с '''n''' и выполняются условия:
* <math>a^2-b^2*c \neq (0,1) \mod n</math>
* Символ Якоби <math>jacobi(c/n)=-1</math>.
Тогда если <math> z^n \equiv \bar{z}\mod n</math>, то число '''n''' скорее всего простое.
Как и в других вероятностных тестах для повышения надежности можно было бы потребовать выполнить этот тест для нескольких пар чисел '''a''' и '''b''',
но это излишне. Поэтому в дальнейшем будем рассматривать упрощенный принцип работы алгоритма теста простоты Фробениуса.
{{Hider|
  title = Упрощенный принцип работы алгоритма|
  hidden = 0 |
  title-style = text-align: left; height: auto; |
  content-style = text-align: left; |
  content =
* Пусть '''n''' – нечетное натуральное число, свободное от квадратов.
* Обозначим через '''c''' наименьшее среди чисел [-1,2,3,5,7,11,...] такое, что [[символ Якоби]] <math>jacobi(c/n) =-1</math>.
* Если <math> c \le 2 </math>, то положим <math>z=2+\sqrt{c}</math>, иначе <math>z=1+\sqrt{c}</math>.
* Определение: назовем число '''n''' простым по Фробениусу, если <math> z^n \equiv \bar{z}\mod n</math>.
* Назовем число [[Псевдопростое число Фробениуса|псевдопростым по Фробениусу]], если оно составное, но просто по Фробениусу.
}}

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

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

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

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

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

== Примечания ==
{{примечания}}

== Литература ==
* {{статья
  |автор          = M. Seysen
  |заглавие       = A Simplified Quadratic Frobenius Primality Test
  |ссылка         = https://eprint.iacr.org/2005/462.pdf
  |издание        = Cryptology ePrint Archive
  |год            = 2005
  |pages          = 4—13
  |ref            = Seysen
}}
* 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}}

[[Категория:Тесты простоты]]