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

                                                                         32

вычисления слишком громоздки, чтобы их можно было реально выполнить.
Суть замечательной идеи Агравелы, Каялы и Саксены состояла в том, чтобы
заменить кольцо 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–составное.
      Замечание. Несмотря на то, что тест AKS явился решением крупной
и долгостоявшей научной проблемы, он является не слишком удобным с
практической точки зрения. Проверка условий пункта 3 является настолько
громоздкой, что общая оценка времени работы алгоритма достигает
O(log18 n) (см. Д. Вентури. Лекции по алгоритмической теории чисел [53]).
Поэтому этот тест следует применять лишь в тех случаях, когда надо
получить гарантированное доказательство того, что число n является
простым.


1.13. Распределение простых чисел
       Известно, что простых чисел бесконечно много. Действительно,
согласно известной теореме Евклида, если {2, 3, 5, ..., pm ≤ B } – множество
всех простых чисел, меньших некоторой границы B , то число M
                      m
                      Y
                M=           pi + 1
                       i=1

снова является простым. Этим методом можно порождать сколь угодно
большие числа. Недостатком такого метода будет только то, что члены
последовательности будут расположены слишком редко.