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

                                                                            19

Оценка сложности решета Аткина

      По оценке авторов алгоритм имеет асимптотическую сложность
                       n 
                    O
                        ln ln n
и требует O(n1/2+o(1) ) бит памяти. Ранее были известны столь же
асимптотически быстрые алгоритмы, но они требовали существенно
больше памяти.


1.6. Тест Поклингтона
      Если у числа n − 1 найдено один или несколько простых делителей, то
это позволяет ограничить область значений простых делителей числа n или
даже показать, что n является простым. Следующая теорема подтверждает
это наблюдение:

Теорема 1.4. (H.C. Pocklington). Пусть n − 1             =   F · R , и полное
разложение множителя F на простые множители известно. Тогда, если
для некоторого a < n выполняются условия:

  1. an−1 ≡ 1 (mod n),

  2. Н.О.Д.(a(n−1)/q , n) 6= 1 для любого q|F ,

тогда любой делитель числа n сравним с 1 по модулю F.


      Доказательство.         Пусть    p–простой   делитель    числа   n.   Из
п.1 предположений теоремы следует, что порядок k элемента aR в
мультипликативной группе поля GFp является делителем (n − 1)/F = R . Из
второго пункта предположений следует, что k не может быть собственным
делителем, т.е. k = F . Отсюда F |(p − 1), т.е. p = 1 + m · F для некоторого
целого m.
                         √
Следствие. Если F >          n, тогда число n–простое.