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

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

История


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

  • Теорема Фробениуса: Пусть n — простое число, символ Якоби (an)=1 и z принадлежит Zn(c), тогда выполняется равенство zn mod n=z¯, где Zn(c) — это поле Галуа из n2 элементов. Доказательство этого утверждения здесь рассматриваться не будет, поскольку это требует достаточно громоздких вычислений, целесообразнее смотреть их в оригинальной статье.
  • Так же существует гипотеза Фробениуса, которая утверждает, что псевдопростых чисел по Фробениусу не существует. Другими словами, тест Фробениуса никогда не ошибается.

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


 Для более четкого понимания алгоритма теста простоты Фробениуса рассмотрим такое понятие как квадратичные иррациональности и их свойства. Квадратичной иррациональностью будем называть число z=a+bc, где a,b,c - целые числа, причем c свободно от квадратов. Сопряженным числом будет являться число вида z¯=abc. Так же делением по модулю n определим операцию zmodn=(amodn)+(bmodn)c. Норму квадратичной иррациональности определим как целое число N(z)=zz¯=a2b2c.

Свойства



  1. Сопряжение мультипликативно: z1z2¯=z1¯z2¯
  2. Норма мультипликативна: N(z1z2)=N(z1)N(z2)
  3. N(zmodn)=N(z)modn

Пример



  • Пусть z=1+3, тогда z¯=13.
  • Норма N(z)=N(z¯)=2.
  • Вычислим, например, z11=31648+182723.
  • Норма будет равна N(z11)=2048=(2)11. Видим, что данное равенство удовлетворяет свойству мультипликативности нормы.
  • Также вычислим z11mod 15. Легко проверить, что это будет равно 13+23.

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


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

  • a2b2c(0,1)modn
  • Символ Якоби jacobi(c/n)=1.

 Тогда если znz¯modn, то число n скорее всего простое. Как и в других вероятностных тестах для повышения надежности можно было бы потребовать выполнить этот тест для нескольких пар чисел a и b, но это излишне. Поэтому в дальнейшем будем рассматривать упрощенный принцип работы алгоритма теста простоты Фробениуса.
 На данный момент неизвестно ни одного числа, псевдопростого по Фробениусу, причем доказано, что таких чисел нет среди меньших 260.

Примеры


Пример 1:

  • Первый шаг: Пусть n=19. Тогда c=1, следовательно z=2+i и z¯=2i.
  • Второй шаг: zn(2+i)193565918+2521451i.
  • Третий шаг: zn mod n(2i)modnz¯.
  • Вывод: n=19 - простое число.

Пример 2:

  • Первый шаг: Пусть n=33. Тогда c=1, следовательно z=2+i и z¯=2i.
  • Второй шаг: zn(2+i)33313245345598+135250416961i.
  • Третий шаг: zn mod n(2+22i)modnz¯.
  • Вывод: n=33 - составное число.

Пример 3:

  • Первый шаг: Пусть n=17. Тогда c=3, следовательно z=1+3 и z¯=13.
  • Второй шаг: zn(1+3)1713160704+75983363.
  • Третий шаг: zn mod n(13)modnz¯.
  • Вывод: n=17 - простое число.

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


 Многие криптосистемы требуют построения сильных простых чисел. Так как вероятность ошибки теста простоты Фробениуса составляет 77101, причем при выборе случайных a и b в квадратичных иррациональностях k раз вероятность ошибки уменьшается до 7710k. Доказано, что для чисел вида n1mod4 вероятность ошибки составляет 217. Это позволяет использовать тест простоты Фробениуса в качестве одного из базовых тестов для построения достоверно простых чисел, использующихся в криптографических приложениях и требующих повышенной стойкости.