Участник:Pyatakovns/Ро-алгоритм Полларда: различия между версиями

Текущая версия на 14:49, 15 октября 2020

Автор: Пятаков Н.С. 419 группа

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритмов

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

Ро-алгоритм Полларда^[1] предназначен для решения задачи факторизации целых чисел. Этот метод был разработан Джоном Поллардом в 1975 г. Данный алгоритм основывается на следствиях из парадокса дней рождения и алгоритме Флойда поиска длины цикла в последовательности. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается как [math]O(N^{1/4})[/math].

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

1.2 Математическое описание алгоритма

Пусть n – число, которое следует разложить. ρ-метод Полларда работает следующим образом: ^[2]^[3]

1. Выбираем произвольное небольшое число [math]x_0[/math] и строим последовательность чисел [math]{x_n}, n = 0, 1, 2, ...,[/math] определяя каждое следующее [math]x_{n+1}[/math] по формуле [math]x_{n+1} =(x_{n}^2 −1)(modn)[/math].

2. Одновременно на каждом шаге [math]i[/math] вычисляем [math]Н.О.Д.[/math] [math]d[/math] числа [math]n[/math] и всевозможных разностей [math]|x_i − x_j|[/math], где [math]j \lt i[/math].

3. Когда будет найден [math]d[/math] [math]=[/math] [math]Н.О.Д.(n, |x_i−x_j|)[/math], отличный от [math]1[/math], вычисление заканчивается. Найденное [math]d[/math] является делителем [math]n[/math]. Если [math]n/d[/math] не является простым числом, то процедуру можно продолжить, взяв вместо [math]n[/math] число [math]n/d[/math].

Вместо функции [math]F (x) = (x^2 − 1) (mod n)[/math] в вычислении [math]x_n+1[/math] можно взять другой многочлен, например, [math]x^2 + 1[/math] или произвольный многочлен степени большей или равной двум.

Недостатком данного варианта метода является необходимость хранить большое число предыдущих значений [math]x_j[/math] . Если [math](x_j −x_i)≡0(modp)[/math], то[math](f(x_j)−f(x_i))≡0(modp)[/math], поэтому, если пара [math](x_i, x_j)[/math] дает нам решение, то решение даст любая пара [math](x_{i+k}, x_{j+k})[/math].

Поэтому, нет необходимости проверять все пары [math](x_i, x_j)[/math], а можно ограничиться парами виды [math](x_i, x_j)[/math], где [math]j = 2k[/math] , и [math]k[/math] пробегает набор последовательных значений [math]1, 2, 3,...,[/math] а [math]i[/math] принимает значения из интервала [math][2^k + 1; 2^{k+1}][/math].

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

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

↑ Pollard J. M. A Monte Carlo method for factorization // BIT. 1975. V. 15. P. 331—334.
↑ Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие / Захаров В.М.. — Казань: Казанский Университет, 2011. — С. 61—64. — 190 с
↑ Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.

[1] Pollard J. M. A Monte Carlo method for factorization // BIT. 1975. V. 15. P. 331—334.

[2] Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие / Захаров В.М.. — Казань: Казанский Университет, 2011. — С. 61—64. — 190 с

[3] Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.

[1]

[2]

[3]

@@ Строка 4: / Строка 4: @@
 == Свойства и структура алгоритмов ==
 === Общее описание алгоритма ===
-'''Ро-алгоритм Полларда'''<ref>Pollard J. M. A Monte Carlo method for factorization // BIT. 1975. V. 15. P. 331—334.</ref> предназначен для решения задачи факторизации целых чисел. Этот метод был разработан Джоном Поллардом в 1975 г. Данный алгоритм основывается на следствиях из парадокса дней рождения и алгоритме Флойда поиска длины цикла в последовательности.
+'''Ро-алгоритм Полларда'''<ref>Pollard J. M. A Monte Carlo method for factorization // BIT. 1975. V. 15. P. 331—334.</ref> предназначен для решения задачи факторизации целых чисел. Этот метод был разработан Джоном Поллардом в 1975 г. Данный алгоритм основывается на следствиях из парадокса дней рождения и алгоритме Флойда поиска длины цикла в последовательности. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается как <math>O(N^{1/4})</math>.
+Ро-алгоритм Полларда строит числовую последовательность, элементы которой образуют цикл, начиная с некоторого номера n, что может быть проиллюстрировано, расположением чисел в виде греческой буквы <math>ρ</math>, что послужило названием семейству алгоритмов.
 === Математическое описание алгоритма ===
-Пусть n – число, которое следует разложить. ρ-метод Полларда работает следующим образом:
+Пусть n – число, которое следует разложить. ρ-метод Полларда работает следующим образом: <ref>Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие / Захаров В.М.. — Казань: Казанский Университет, 2011. — С. 61—64. — 190 с</ref><ref>Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.</ref>
-. Выбираем небольшое число <math>x_0</math> и строим последовательность чисел <math>{x_n}, n = 0, 1, 2, ...,</math> определяя каждое следующее <math>x_{n+1}</math> по формуле <math>x_{n+1} =(x_{2n} −1)(modn)</math>.
+. Выбираем произвольное небольшое число <math>x_0</math> и строим последовательность чисел <math>{x_n}, n = 0, 1, 2, ...,</math> определяя каждое следующее <math>x_{n+1}</math> по формуле <math>x_{n+1} =(x_{n}^2 −1)(modn)</math>.
+. Одновременно на каждом шаге <math>i</math> вычисляем <math>Н.О.Д.</math> <math>d</math> числа <math>n</math> и всевозможных разностей <math>|x_i − x_j|</math>, где <math>j < i</math>.
+. Когда будет найден <math>d</math> <math>=</math> <math>Н.О.Д.(n, |x_i−x_j|)</math>, отличный от <math>1</math>, вычисление заканчивается. Найденное <math>d</math> является делителем <math>n</math>. Если <math>n/d</math> не является простым числом, то процедуру можно продолжить, взяв вместо <math>n</math> число <math>n/d</math>.
+Вместо функции <math>F (x) = (x^2 − 1) (mod n)</math> в вычислении <math>x_n+1</math> можно взять другой многочлен, например, <math>x^2 + 1</math> или произвольный многочлен степени большей или равной двум.
+Недостатком данного варианта метода является необходимость хранить большое число предыдущих значений <math>x_j</math> . Если <math>(x_j −x_i)≡0(modp)</math>, то<math>(f(x_j)−f(x_i))≡0(modp)</math>, поэтому, если пара <math>(x_i, x_j)</math> дает нам решение, то решение даст любая пара <math>(x_{i+k}, x_{j+k})</math>.
+Поэтому, нет необходимости проверять все пары <math>(x_i, x_j)</math>, а можно ограничиться парами виды <math>(x_i, x_j)</math>, где <math>j = 2k</math> , и <math>k</math> пробегает набор последовательных значений <math>1, 2, 3,...,</math> а <math>i</math> принимает значения из интервала <math>[2^k + 1; 2^{k+1}]</math>.
 === Вычислительное ядро алгоритма ===