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

Сложность первого варианта зависит от истинности расширенной гипотезы Римана.

Второй вариант - SQUFOF, он использует группу классов бинарных квадратичных форм с положительным дискриминантом. Он также находит форму ambyg и разбивает дискриминант на факторы.

Сложность SQUFOF составляет арифметических операций; при этом алгоритм работает с целыми числами, не превосходящими . Среди алгоритмов факторизации с экспоненциальной сложностью SQUFOF считается одним из самых эффективных.

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

Более подробно алгоритм может быть записан в следующем виде:

Вход: Нечетное составное число n, которое требуется факторизовать. Если n mod 4=1 заменим n на 2n. Теперь n mod 4=2;3 . Последнее свойство нужно, чтобы определитель квадратичной формы был фундаментальным, что обеспечивает сходимость метода.

Выход: Нетривиальный делитель n.

1. Определим исходную квадратичную форму , с дискриминантом D=4n , где .

2. Выполним цикл редуцирований , пока форма не станет квадратной.

3. Вычислим квадратный корень из .

4. Выполним цикл редуцирований , пока значение второго коэффициента не стабилизируется . Число итераций этого цикла должно быть примерно равно половине от числа итераций первого цикла. Последнее значение даст делитель числа (возможно тривиальный).

Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число на множители за арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году. Этот алгоритм был первым детерминированным алгоритмом факторизации для целых чисел, имеющих более низкую оценку, чем . В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.

Алгоритм

Пусть n нечетно и n>8

Шаг 1. Для проверить условие a|n . Если на этом шаге мы не разложили на множители, то переходим к шагу 2.

Шаг 2. Если на шаге 1 делитель не найден и n — составное, то n = pq, где p, q — простые числа, и . Тогда для всех и всех проверить, является ли число квадратом натурального числа. Если является, то для и выполнено сравнение:

или (A-B)(A+B)=0 (mod n).

В этом случае для d*=( A-B, n ) проверяется неравенство 1< d*<n . Если оно выполнено, то n=d* . (n/d*) — разложение n на два множителя.

Если алгоритм не нашел разложение n на два множителя, то n — простое число.

Данный алгоритм в начале проверяет имеет ли простые делители не превосходящие , а после устраивает перебор значений k и d для проверки выполнимости указанной ниже Теоремы. В случае, если искомые значения x и , не найдены, то мы получаем что число простое. Таким образом мы можем рассматривать данный алгоритм как тест числа на простоту.

Трудоемкость

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

Трудоемкость второго шага оценивается в операциях тестирования числа , на то, является ли оно полным квадратом. В начале заметим, что для всех выполняется только две проверки: D=0 и D=1. Тогда, трудоемкость второго этапа оценивается сверху величиной
.

Таким образом трудоемкость всего есть величина .

Глава 2. Примеры реализации алгоритмов натуральных чисел и оценка их эффективности

2.1 Примеры разложения натуральных чисел

2.1.1 Метод факторизации Ферма

Пример с малым числом итераций

Возьмем число n=10873. Вычислим Для будем вычислять значения функции s+k . Для дальнейшей простоты построим таблицу, которая будет содержать значения y и на каждом шаге итерации. Получим:

Как видно из таблицы, уже на втором шаге итерации было получено целое значение .

Таким образом имеет место следующее выражение:. Отсюда следует, что

Пример с большим числом итераций

Пусть Тогда или

Данное разложение является не конечным, т.к., очевидно, что число 145 не является простым. Применив метод Ферма, получим145=29x5. В итоге, конечное разложение исходного числа n на произведение простых множителей 89755=5x29x619.

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

С помощью метода Крайчика-Ферма разложим число Число является первым, чей квадрат больше числа :

Вычислим значение функции для всех , получим

По методу Ферма, нужно было бы продолжать вычисления пока не был бы найден квадрат какого-либо числа. По методу Крайчика-Ферма далее нужно последовательно искать такие , для которых Тогда

Из алгоритма Крайчика-Ферма следует, что все полученные числа можно легко факторизовать.

Действительно:

Очевидно, что произведение полученный четырех чисел будет квадратом: Тогда теперь можно вычислить

Далее с помощью алгоритма Евклида находим .

Таким образом,

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

Пусть n=8051, , , .

Таким образом, 97 - нетривиальный делитель числа 8051. Используя другие варианты полинома F (x) , можно также получить делитель 83.

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

Применим данный метод для факторизации числа N=22117019

Теперь можно увидеть во втором цикле, что Следовательно число

2.1.5 Алгоритм Лемана

Разберем пример с n=1387 , тогда для , где , проверяем является ли число делителем числа . Не трудно убедится, что таких нет, тогда переходим к следующему пункту.

Для всех k=1,2,3,…, 11 и всех d = 0,1,…,4 проверяем, является ли число квадратом натурального числа. В нашем случае существуют такие k = 3 и d = 1 , что выражение является полным квадратом и равно . Следовательно, A = 130 и

B = 16. Тогда d* = ( A-B; n ) =19 , удовлетворяет неравенству 1<d*<n и является делителем числа n. В итоге, мы разложили число 1387 на два множителя: 73 и 19.

2.1.6 Алгоритм Диксона

Факторизуем число n = 89755

L (18638) = 194,174…

M = 13,934…

Все найденные числа b с соответствующими векторами записываем в таблицу.