Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Теория чисел / Разложение на множители /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


P-1 метод Полларда - Программирование от RIN.RU
P-1 метод Полларда



Алгоритм p-1 со второй стадией.


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


  1. [Первая стадия]
    Используя В = В1, попытаться разложить N через алгоритм А2. Если удалось - выйти. В противоположном случае у нас будет число х и тогда пусть b := x, c := 0, P := 1, i := 0, j := i, y := x.

  2. [Предварительные вычисления]
    Для всех разностей d[i] (которые малы по размеру и по численности) вычислить и сохранить bd[i]. Пусть x := xp[k1].

  3. [Вперед!]
    Пусть i := i + 1, x : = x * bd[i] ( используя значения, вычесленные в шаге 2 ), P := P * ( x - 1 ), c := c + 1. Если i >= k2, идти на шаг 6. Иначе, если c < 20, идти на шаг 3.

  4. [Вычисляем НОД]
    Пусть g := НОД ( P , N ). Если g = 1, пусть c := 0, j := i, y := x и идти на шаг 3.


  5. [Обратный ход]
    Пусть i := j, x := y. Повторять x := x * bd[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 алгоритма гораздо более эффективна, чем одна первая стадия. Обычные значения для использования - это B1 = 2 * 106, B2 = 108.


Оптимально использовать этот алгоритм после простого деления, но перед применением более серьезных методов.










<<<  Назад
 1  2 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь