Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 30 стр.

                                                                              31

1.12. Полиномиальный критерий простоты AKS
         Одной       из   важных   проблем,   долгое    время   стоявших   перед
исследователями, была проблема построения детерминированного алгоритма
проверки    простоты       натуральных   чисел,     имеющего    полиномиальную
оценку времени работы. Алгоритм Миллера–Рабина, упомянутый в
предыдущем разделе, имеет полиномиальную оценку, но не является
детерминированным. Другие тесты, например тест Поклингтона (разд.1.6),
являются детерминированными, но не имеют полиномиальной оценки.
      В 2004 г. тремя молодыми индийскими математиками Агравелой,
Каялом     и     Саксеной      ([1])   был    разработан      детерминированный
полиномиальный безусловный тест AKS проверки простоты заданного
натурального числа. Тест AKS основывается на следующей теореме:

Теорема 1.7. (Agrawel,        Kayal,   Saxena     [2004].)   Пусть   n–нечетное
натуральное число, r –простое число и выполнены условия:

  1. Число n не делится ни на одно из чисел, меньших или равных r ,

  2. Порядок n в мультипликативной группе Z ∗p поля GFp не меньше
     (log2 (n))2 ,

  3. Для всех a, 0 ≤ a ≤ r , выполнена формула
                                                              Xr − 1
       (X + a)n ≡ X n + a в кольце многочленов Zn [X]/               .     (1.10)
                                                              X −1

Тогда число n является простым.


      В этой теореме используются вычисления в кольце многочленов Z n [X]
с коэффициентами, ограниченными сверху числом n, факторизованных по
модулю многочлена деления круга
               Xr − 1
   Φr (X) =           = X r−1 + X r−2 + ... + X + 1.
               X −1
      Конечно, если n–просто, то эквивалентность (X +a)n ≡ X n +a mod n
в силу малой теоремы Ферма выполняется и в кольце Z n [X], однако эти