Стадия 1 Определение     Пусть B - положительное целое число. Некоторое положительное целое N называется B-гладким, если все простые делители N меньше, либо равны B.
     N будет называться гладким степени B, если все степени простых чисел, делящие N меньше, либо равны B.


     Эти слова о гладкости весьма естественны в методах факторизации и, как мы увидим, будут весьма необходимы в самых современных из них.

     Пусть p - заранее не известный простой делитель N, которое мы хотим разложить. Пусть a > 1 - целое число (которое мы полагаем взаимно простым с N, проверяя это вычислением НОД. Если НОД ( a , N ) > 1, то N уже разложено). По теореме Ферма a^p-1 сравнимо с 1 (mod p). Теперь предположим, что p-1 - гладкое степени B, где B не слишком велико. Тогда по определению p-1 делит НОК чисел от 1 до B. Следовательно, a^{НОК(1..B)*k} сравнимо с 1 (mod p), следовательно a^НОК(1..B) сравнимо с 1 (mod p). А значит

     Если мы проверяем это для увеличивающихся значений B, то весьма маловероятно, что НОД будет равен N. Также можно использовать некоторые трюки, например не вычислять НОД каждый раз заново, а хранить результаты по модулю N и вычислять НОД только время от времени. Это приводит нас к алгоритму Полларда:

Первая стадия алгоритма p-1

     Пусть N - составное число, и В - заранее выбранная верхняя грань. Этот алгоритм будет пытаться найти нетривиальный делитель N, но это получится только если существует простой делитель N, такой что p-1 - гладкое степени B. Мы предполагаем, что уже есть таблица p[1], ..., p[k] всех простых до B.

1. [Инициализация]
        Пусть x := 2, y := x, P := 1, c := 0, i := 0, j := i.
   
   
2. [Следующее простое]
        Пусть i := i + 1. Если i > k, вычислим g = НОД ( P , N ). Если g = 1, выведем сообщение, что разложение не удалось и выйдем, иначе i := j, x := y и идти на шаг 5. Иначе ( т.е если i <= k ), q := p[i], q₁ := q, L := [ B / q ].
   
   
3. [Вычисляем степень]
        Пока q₁ <= L, пусть q₁ := q * q₁. Затем, пусть x := x^q₁ mod N, P := P * (x-1) mod N, c := c + 1, и , если c < 20, идти на шаг 2.
   
   
4. [Вычисляем НОД]
        Пусть g := НОД ( P , N ). Если g = 1, пусть c := 0, j := i, y := x и идти на шаг 2. Иначе пусть i := j, x := y.
   
   
5. [Обратный ход]
        Пусть i := i + 1, q := p[i] и q₁ := q.
   
   
6. [Конец?]
        Пусть x := x^q mod N, g := НОД ( x - 1 , N ). Если g = 1, пусть q₁ := q * q₁ и если q <= B, идти на шаг 6, иначе - на шаг 5. Иначе (т.е если g >= 1), если g < N, вывести g и выйти. Если g = N (редкий случай), вывести, что разложение не удалось и выйти.

     Заметим, что этот алгоритм может прекратить работу по двум различным причинам. Первая, самая часто встречающаяся, проявит себя в шаге 2. Это то, что N не имеет простых делителей p таких, что p-1 - гладкое степени B. При этом данный факт можно будет считать доказанным.
     Вторая причина ( в шаге 6 ) чрезвычайно редка. Это будет означать, что все простые делители N найдены одновременно. Если это так, то, очевидно, существует p - делитель N, которое является гладким степени B. Значит, стоит попробовать запустить алгоритм с другим начальным значением x, например, x := 3 вместо x :=2.

     Даже в такой простой форме поведение p-1 алгоритма довольно впечатляюще. Разумеется, он не претендует на получение полного разложения ( например, когда N = ( 2 * p + 1 ) * ( 2 * q + 1 ), где p, q, 2 * p + 1 и 2 * q + 1 простые, причем p и q примерно одного размера, время работы алгоритма будет O( N^1/2+e ), если мы хотим разложить N полностью, не лучше простого деления ). С другой стороны, его можно удачно использовать для нахождения даже очень больших делителей N, так как на время работы влияет не размер делителя p, а гладкость p-1.

Размер B зависит, в основном, от времени, которое мы можем потратить. Кроме того, на него влияет существование второй стадии алгоритма. Обычные значения B - где-то от 10⁵ до 10⁶.
p-1 метод, стадия 2.      А теперь - существенное улучшения P-1 алгоритма. Требование существования простого делителя N, такого что p - 1 - гладкое степени B, - слишком строгое. Более рационально положить условие полной разложимости p - 1 при простом делении до B. То есть сделаем возможным существование одного простого делителя, большего B. Но это значит, что p - 1 = f * q, где f - B-гладкое, а q - простое число, возможно, гораздо большее B ( но не B² ). Для наших целей мы несколько усилим условие и предположим, что у N есть простой делитель р, такой что p - 1 \ f * q, где f - гладкое степени B₁ , и q - такое простое, что B₁ < q <= B₂, где B₁ - cтарое B и B₂ - гораздо большая константа.

     Покажем, как мы будем искать такое p. Очевидно, p - 1 - гладкое степени B₂, таким образом мы могли бы использовать стадию 1 с B₁ замененным на В₂, однако, это нереально, так как B₂ - гораздо большая константа, чем В₁.

     Тем же путем получаем


и поступаем так: в конце первой стадии у нас будет вычислено b := a^{НОК(1..В)} mod N. Мы храним таблицу разностей простых от B₁ до B₂. Теперь эти разности малы и у нас их немного. Таким образом мы можем легко вычислить b^d для всех возможных разностий d и получить все b^d, умножая начальную степень b на эти заранее вычисленные b^d. Следовательно, для каждого простого, мы заменяем возведение в степень простым умножением, которое гораздо быстрее, и поэтому мы можем пойти много дальше. Это приводит нас к следующему алгоритму.


Алгоритм p-1 со второй стадией.
     Пусть N - составное число и В₁ и В₂ - заранее выбранные границы. Этот аглоритм будет искать нетривиальные делители N и может сделать это только в том случае, если существует простой делитель p такой, что p - 1 равно некоторому числу гладкости В₁, умноженному на простое, меньшее либо равное В₂. Мы предполагаем, что уже есть таблица p[1], ... , p[k₁] всех простых до В1 и таблица d[1], ... , d[k₂] разностей между простыми от В₁ до В₂, где d[k] = p[k₁ + 1] - p[k₁], и т.д...

1. [Первая стадия]
        Используя В = В₁, попытаться разложить N через алгоритм А2. Если удалось - выйти. В противоположном случае у нас будет число х и тогда пусть b := x, c := 0, P := 1, i := 0, j := i, y := x.
   
   
2. [Предварительные вычисления]
        Для всех разностей d[i] (которые малы по размеру и по численности) вычислить и сохранить b^d[i]. Пусть x := x^p[k1].
   
   
3. [Вперед!]
        Пусть i := i + 1, x : = x * b^d[i] ( используя значения, вычесленные в шаге 2 ), P := P * ( x - 1 ), c := c + 1. Если i >= k₂, идти на шаг 6. Иначе, если c < 20, идти на шаг 3.
   
   
4. [Вычисляем НОД]
        Пусть g := НОД ( P , N ). Если g = 1, пусть c := 0, j := i, y := x и идти на шаг 3.
   
   
5. [Обратный ход]
        Пусть i := j, x := y. Повторять x := x * b^d[i], i := i + 1, g := НОД ( x - 1 , N ) до того, g не примет значение g > 1 ( это должно произойти ). Если g < N вывести g и выйти. Иначе (т.е если g = N, редчайший случай), вывести, что разложение не удалось ( или попробовать опять, используя x := 3 вместо x := 2 в 1 шаге алгоритма А2), и выйти.
   
   
6. [Не удалось?]
        Пусть g := НОД ( P , N ). Если g = 1, вывести, что разложение не удалось, и выйти. Иначе идти на шаг 5.

     Эта форма р-1 алгоритма гораздо более эффективна, чем одна первая стадия. Обычные значения для использования - это B₁ = 2 * 10⁶, B₂ = 10⁸.

Назад

снежок-силикагель - наполнители для туалетов домашних животных поглощают запахи и влагу