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

Тест простоты Фробениуса — это вероятностный тест простотынатурального числа 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. Это позволяет использовать тестпростоты Фробениуса в качестве одного из базовых тестов для построениядостоверно простых чисел, использующихся в криптографических приложенияхи требующих повышенной стойкости.