Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Ρ-алгоритм Полларда).pdf

Обратно, если дано, что , то правую часть можно разложить на множители: .

Описание алгоритма

Для разложения на множители нечётного числа ищется пара чисел таких, что , или . При этом числа и являются множителями , возможно, тривиальными (то есть одно из них равно 1, а другое — .)

Равенство равносильно , то есть тому, что является квадратом.

Начинается поиск такого квадрата с — наименьшего числа, при котором разность неотрицательна. Для каждого значения k€N начиная с k=1, вычисляют и проверьте, является ли это число точным квадратом. Если это не так, то k увеличивается на единицу и переходит к следующей итерации.

Если является точным квадратом, т.е. то получено разложение:

в котором

Если оно является тривиальным и единственным, то n — простое.

На практике значение выражения на -ом шаге вычисляется с учетом значения на k-ом шаге:

где

Таким образом, как и метод пробного деления, алгоритм Ферма имеет экспоненциальную оценку и не эффективен для разложения длинных чисел. Вы можете улучшить метод Ферма, сначала выполнив предварительное деление числа n на числа от 2 до некоторой константы B, тем самым исключив небольшие делители n на B включительно, а затем ищите Ферма.

1.4 Метод Крайчика-Ферма

Обобщение метода Ферма было предложено Морисом Крайчиком (1882-1957). Он предложил рассматривать вместо пар чисел которые удовлетворяют соотношению искать пары чисел, удовлетворяющих более общему уравнению Крайчик заметил, что многие из чисел, получаемых по формуле раскладываются на простые множители, т.е. числа являются гладкими.

Последовательность действий по Крайчику

1. Найти множество пар которые удовлетворяют соотношению

2. Определить полное или частное разложение чисел x и y на множители для каждой пары (x,y).

3. Выбрать пары ( x,y ), произведение которых удовлетворит соотношению

4. Разложить число n на множители.

1.5 Ρ-алгоритм Полларда

Числовая последовательность зацикливается, начиная с некоторого n. Числовая последовательность зацикливается, начиная с некоторого n. Цикл можно представить в виде греческой буквы ρ.

Ρ-алгоритм Джона Полларда, предложенный им в 1975 году, используется для факторизации целых чисел. Он основан на алгоритме Флойда для определения длины цикла в последовательности и некоторых следствий из парадокса дней рождения. Алгоритм наиболее эффективен при расчете составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается, как .

Во всех ρ-методах Полларда строится числовая последовательность, элементы которой образуют цикл, начиная с определенного числа n, что можно проиллюстрировать расположением чисел в виде греческой буквы ρ. Это было название семейства методов.

Описание алгоритма

Оригинальная версия

Рассмотрим последовательность целых чисел , такую что и , где - число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом.

1. Будем вычислять тройки чисел

, где .

Причем каждая такая тройка получается из предыдущей.

2. Каждый раз, когда число кратно числу (скажем, ), будем вычислять наибольший общий делитель любым известным методом.

3. Если , то найдено частичное разложения числа , причем .

Найденный делитель может быть составным, поэтому его также необходимо факторизовать. Если число составное, то продолжаем алгоритм с модулем .

4. Вычисления повторяются S раз. Например, можно прекратить алгоритм при . Если при этом число не было до конца факторизовано, можно выбрать, например, другое начальное число .

Современная версия

1. Пусть n будет составным положительным целым числом, в которое вы хотите вложить. Алгоритм выглядит следующим образом:
2. Выбираем небольшое число и строим последовательность , определяя каждое следующее как .
3. Одновременно на каждом i-ом шаге вычисляем для каких-либо i, j таких, что j<i, например, i=2j.
4. Если обнаружили, что d>1, , то вычисление заканчивается, и найденное на предыдущем шаге число d является делителем n. Если n/d не является простым числом, то процедуру поиска делителей можно продолжить, взяв в качестве n число n`=n/d.

Как на практике выбирать функцию F(x)? Функция должна быть не слишком сложной для вычисления, но в то же время не должна быть линейным многочленом, а также не должна порождать взаимно однозначное отображение. Обычно в качестве F(x) берут функцию или . Однако не следует использовать функции и .

Если известно, что для делителя p числа n справедливо p=1(mod k) при некотором k>2 , то имеет смысл использовать .

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений .

Улучшения алгоритма

Изначальная версия алгоритма обладает рядом недостатков. В настоящий момент существует несколько подходов к улучшению оригинального метода.

Пусть . Заметим, что если , то , поэтому, если пара дает нам решение, то решение даст любая пара .

Поэтому, нет необходимости проверять все пары , а можно ограничиться парами вида , где , и k пробегает набор последовательны значений 1, 2, 3, ..., а принимает значения из интервала . Например, k = 3, , а .

Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25%.

Еще одна вариация P-метода Полларда была разработана Флойдом. Согласно Флойду, значение обновляется на каждом шаге по формуле , поэтому на шаге i будут получены значения , , и НОД на этом шаге вычисляется для и .

1.6 Метод квадратичных форм Шенкса

Это метод факторизации целых чисел, основанный на использовании квадратичных форм, разработанный Дэниелом Шенксом в 1975 году в качестве развития метода факторизации Ферма.

Для 32-разрядных компьютеров алгоритмы, основанные на этом методе, являются бесспорными лидерами алгоритмов факторизации для чисел между ними и, вероятно, останутся. Этот алгоритм может разбить почти любое составное 18-значное число менее чем за миллисекунду. Алгоритм чрезвычайно прост, красив и эффективен. Кроме того, методы, основанные на этом алгоритме, используются в качестве вспомогательных при разложении делителей больших чисел, таких как числа Ферма.

Вспомогательные определения

Чтобы понять, как реализован этот алгоритм, необходимо найти минимальную информацию о математических объектах, используемых в этом методе, а именно о квадратичных формах. Бинарная квадратичная форма является полиномом от двух переменных x и y:

В методе Шенкса используются только неопределенные формы. Под будем понимать дискриминант квадратичной формы. Будем говорить, что квадратичная форма представляет целое число , если существуют такие целые числа , что выполнено равенство: . В случае если выполнено равенство , то представление называется примитивным.

Для любой неопределенной квадратичной формы можно определить оператор редукции как:

,

Где r(-b,c) - определено, как целое число , однозначно определяемое условиями:

r+b=0 mod (2c)

Результат применения оператора к форме раз записывается в виде . Также определен оператор как:

,

где r(-b,c) определен так же, как и в прошлом случае. Заметим, что в результате применения операторов и к квадратичной форме с дискриминантом , полученные квадратичные формы так же будут иметь дискриминант .

Метод получения редуцированной формы, эквивалентной данной, был найден еще Карлом Гауссом и состоит в последовательном применении оператора редукции g=p(f) , пока f не станет редуцированной.

Теорема.

Каждая форма f эквивалентна некоторой редуцированной форме, и любая редуцированная форма для f равна для некоторого положительного k. Если f - редуцирована, то также редуцирована.

Также для ясности понимания всех операций с квадратичными формами нам нужны понятия квадратной, смежной и неоднозначной квадратичной формы.

Варианты

Идея метода Шенкса состоит в сопоставлении числу , которое надо разложить квадратичной бинарной формы с дискриминантом D = 4n, с которой потом выполняется серия эквивалентных преобразований и переход от формы к неоднозначной форме . Тогда, будет являться делителем n.

Первая версия работает с положительно определенными двоичными квадратичными формами заданного отрицательного дискриминанта, а в группе форм классов находит форму Ambigue, которая дает разложение дискриминанта на факторы.