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

                                                                             40

Теорема 2.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) ≡ X + a в кольце многочленов Zn [X]/
                n      n
                                                           .              (2.13)
                                                    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], однако эти
вычисления слишком громоздки, чтобы их можно было реально выполнить.
Суть замечательной идеи Агравелы, Каялы и Саксены состояла в том, чтобы
заменить кольцо Z n [X] на гораздо меньшее кольцо Z n [X]/Φr (X).
      На этой теореме основан следующий тест проверки простоты числа n:

  1. Проверим, что n не является полным квадратом,

  2. Используя числа r = 2, 3, 5, ..., найдем наименьшее простое число r
     такое, что r не является делителем n, и не является делителем ni − 1
     для всех i ∈ {0, 1, 2, ... , (log2 n)2 )}.

  3. Проверим, что выполнены условия пункта 3 теоремы.

Если эти условия выполнены, то n–простое, иначе n–составное.