Факторизация целых чисел с экспоненциальной сложностью

Министерство транспорта Российской Федерации

ГОУ ВПО «Дальневосточный государственный университет путей  сообщения» 
 
 
 
 

Кафедра: «Прикладная  математика» 
 
 
 

РЕФЕРАТ

 по дисциплине  «Основы криптографии» 

на тему:

«Факторизация целых чисел с  экспоненциальной сложностью» 
 
 
 
 
 
 

                                Выполнила: ст-ка 942 гр.,    

                                                       Левина А.Е.

                                                     Проверил: Ершов Н.Е. 
 
 

Хабаровск

2011г. 

Содержание.

Введение………………………………………………………………………………………………………3

Метод Ферма………………………………………………………………………………………………...4

(P− 1)-метод Полларда………………………………………………………………………………...7

p-метод Полларда……………………………………………………………………………………….11

Метод Шермана—Лемана…………………………………………………………………………..14

Алгоритм  Ленстры…………………………………………………………………………………….18

Алгоритм  Полларда—Штрассена……………………………………………………………….26

(P+ 1)-метод Уильямса и его обобщения……………………………………………………28

Методы  Шэнкса………………………………………………………………………………………….30

Заключение………………………………………………………………………………………………...31

Список  используемой литературы…………………………………………………………….32 
 
 
 
 
 
 
 
 

Введение. 

     Рассмотрим алгоритмы разложения натурального числа n на множители, делающие O(n^с) арифметических операций, где c—некоторая постоянная, 0 < c < 1; либо делающие O(n^c1log^c2 n) арифметических операций при некоторых постоянных c₁, c₂. Мы будем ограничиваться поиском разложения на два множителя: n=ab, 1< a ≤ b < n. Если алгоритм находит такое разложение за O(f (n)) арифметических операций, то полное разложение n на простые множители будет найдено за O(f(n) log n) арифметических операций, поскольку n состоит из произведения не более чем log₂ n простых чисел.

     Прежде  чем приступать к факторизации целого числа, следует убедиться, что оно  действительно составное. Для этого  лучше всего использовать один из вероятностных тестов на простоту, например, алгоритм Миллера—Рабина.

     Опишем здесь некоторые алгоритмы, например алгоритм П.Ферма, полученный им в 1643 г. Этот алгоритм вычисляет наибольший множитель a числа n, не превосходящий n^1/2. При этом в алгоритме не используется операция деления, а только сложение, вычитание и умножение. Заметим, что если n = pq, где p и q—простые числа, примерно одинаковые по величине, то алгоритм Ферма быстро разложит n. Это следует учитывать при выборе модулей в криптосистеме RSA.

Метод Ферма. 

Алгоритм.

     Пусть n — составное число, , где , причем —наибольшее возможное. Положим , , где и — натуральные числа, , , n = ab = u² − v². Алгоритм Ферма ищет представление n в виде n= u² −v², откуда получается разложение n = = (u − v) (u+ v) = ab.

     Мы  работаем с величинами 

, k = 0, 1, 2, . . . 

Начальное значение (x₀, y₀) = ([√n] , 0). Увеличение номера k происходит по следующим правилам. Если r_k = 0, то наша цель достигнута, n = = (x_k − y_k) (x_k + y_k), и алгоритм останавливается. Если r_k > 0, то 

(x_k+1, y_k+1) : = (x_k, y_k + 1),

если же r_k < 0, то

(x_k+1, y_k+1) := (x_k + 1, y_k);

затем

r _k+1 := . 

     Наша цель—доказать, что за конечное число шагов алгоритм дойдет до значения r_k = 0, и что для первого такого значения справедливо равенство x_k − y_k = a, где a — наибольший натуральный делитель n, не превосходящий n ^1/2. Если n является полным квадратом, то это очевидно по определению x₀ и y₀. Далее мы считаем, что n — не полный квадрат.

     Рассмотрим  функцию r(x, y) = x² − y² − n. Очевидно, что при неотрицательных x и y выполнены неравенства 

r(x, y+ 1) < r(x, y) < r(x+ 1, y). 

Кроме того, в алгоритме Ферма x_k и y_k всегда неотрицательны и не убывают (по построению).

     Рассмотрим  декартову систему координат на плоскости и решетку целых точек Z². Она разбивает плоскость на единичные квадраты; каждый квадрат будем нумеровать точкой (x, y), стоящей в его левом нижнем углу. В квадрат, пронумерованный точкой (x, y) ∈ Z² мы впишем знак величины r(x, y): + (плюс), − (минус) или 0, если r(x, y) = 0. Очевидно, что если в некотором квадрате стоит знак − (минус), то и во всех квадратах над ним тоже стоит знак − (минус); если в некотором квадрате стоит знак + (плюс), то и во всех квадратах правее тоже стоит знак + (плюс).

     В алгоритме Ферма мы двигаемся по квадратам. Начало движения — квадрат, занумерованный (x₀, y₀); в нем стоит знак − (минус). Очередной шаг мы делаем вверх, если в квадрате стоит знак + (плюс), и вправо—если в квадрате стоит знак − (минус). Самый первый шаг

мы  делаем вправо.

     При движении по квадратам в алгоритме  Ферма мы не можем двигаться все время вверх, а обязательно будем делать шаги вправо. Пусть мы достигли точки (x_k, y_k), где y_k ≥ 1. Покажем индукцией по k, что тогда r(x_k, y_k − 1) > 0, т. е. под квадратом (x_k, y_k) стоит знак + (плюс).

     Основание индукции мы проверяем для значения k = l, для которого

квадрат, занумерованный (x_l, y_l) = (x_l, 1), есть первый квадрат, в котором y_l=1, а(x_l−1, y_l−1) = (x_l−1, 0). В этот квадрат мы пришли снизу, а это означает, что r(x_l−1, y_l−1) =r(x_l, y_l − 1) >0. Это и есть выполнение основания индукции.

     В квадрат(x_k, y_k) мы попали либо слева, либо снизу. Если снизу, то мы наращивали y, и тогда очевидно, что r(x_k, y_k − 1) > 0. Если слева, то (x_k−1, y_k−1) = (x_k − 1, y_k). Тогда по предположению индукции

     r(x_k−1, y_k−1 − 1) > 0. 

Из  предположения индукции теперь следует, что r(x_k−1 + 1, y_k−1 −1) >

> 0, т. е. r(x_k, y_k − 1) > 0, что и требовалось доказать.

     Заметим, что число u — наименьшее натуральное число, для которого возможно представление n = u² − v². В самом деле, n = ab,, , , и поскольку a² <n, то u’ (a) <0; с ростом a величина u = u(a) убывает и принимает наименьшее значение при наибольшем a, a² < n.

     Пусть мы первый раз достигли точки (x_k, y_k), в которой x_k = u (этот момент обязательно наступит согласно доказанному выше). Если y_k = v, то мы достигли желаемого результата, r(x_k, y_k) = 0, алгоритм заканчивает работу и выдаст пару (a, b) = (u −v, u +v).

     Если y_k < v, то r(x_k, y_k) = u² −y²_k − n=u₂ − y²_k− (u²−v²) = v²−y²_k > 0. В этом случае мы двигаемся вверх, наращивая y, до тех пор, пока y_k+j =v, т.е. мы найдем x_k+j = u, y_k+j = v, r(x_k+j, y_k+j) = 0 и алгоритм

закончит  работу и выдаст пару (a, b) = (u −v, u + v).

     Осталось  рассмотреть последний случай y_k >v. Этот случай невозможен, так как по доказанному выше под квадратом (x_k, y_k) стоит знак + (плюс), т. е. r(u, y_k − 1) >0. Значит, и всюду ниже стоит знак + (плюс). А в нашем квадрате (x_k, y_k) = (u, y_k), r(x_k, y_k) = u² − y²_k− n = v² − y²_k < 0, т. е. стоит знак − (минус). Значит, 0 здесь нигде не может стоять, а он должен быть в этом столбце, поскольку n = u² − v².

     Итак, мы достигнем в алгоритме точки (x_k, y_k) = (u, v), получим значение r_k = 0 и найдем a = u −v, что и требовалось доказать.

(P− 1)-метод Полларда. 

     Он  основан на следующей идее. Допустим, что у числа n, которое мы хотим разложить на множители, есть простой делитель p такой, что число p − 1 является B-степенно-гладким для некоторой границы гладкости        B > 0. Это означает, что для любого простого числа q, q | p − 1,

выполнено неравенство 

q^{vq (p−1)} ≤B. 

Отсюда  следует, что p − 1 |НОК(1, 2, . . . , B). Если мы выберем a ∈ N такое, что (a, n) = 1, то по малой теореме Ферма 

a^{НОК(1,2,. . . ,B)} ≡1 (mod p). 

Следовательно, НОД(a^{НОК(1,2,. . . ,B)} − 1, n) делится на p и поэтому содержит нетривиальный делитель n (НОД может быть и равен n). 

1 стадия (P −1)-метода Полларда.

     В (P − 1)-методе Полларда мы выбираем априорную границу гладкости B, исходя из возможностей нашего компьютера и времени, которое мы рассчитываем потратить. Обычно B = 10⁵—10⁶. Далее составляем таблицу q₁ < q₂ < ...< q_k ≤ B всех простых чисел, не превосходящих B, и для каждого q_i полагаем 

, т.е. q_i^β(qi)≤B, q_i^β(qi)+1>B 

Далее мы выбираем значение a (например, a= 2). Затем последовательными возведениями в степень и приведениями по модулю n вычисляем 

(параметр 20 также априорный). Далее вычисляем НОД(P₂₀, n). Если этот НОД тривиальный, то добавляем к P₂₀ следующее произведение длины 20, т. е. находим 

снова считаем НОД(P40, n) и так далее. Предположим, что при некотором k ≥ 1 оказалось, что НОД(P20k, n) > 1. Тогда мы возвращаемся к значению k −1 и начинаем последовательно вычислять наибольшие общие делители 

до  первого нетривиального общего делителя.

     Значение  нахождения P₂₀, P₄₀, P₆₀, . . . состоящих из порций по 20 степеней простых чисел, состоит именно в экономии на вычислениях наибольшего общего делителя. Заметим, что поскольку количество простых чисел q_i не обязано делится на 20, то последняя порция может быть неполной. 

2 стадия (P − 1)-метода Полларда.

     Предположим, что p | n, p − 1 не является B-степенно-гладким числом, но p −1 =f * r, где f — B-степенно-гладкое число и r — простое число, B < r < B1. Допустим, что на 1 - й стадии (P − 1)-метода Полларда мы вычислили 

b =a^{НОК(1,2,. . . ,B)} (mod n). 

Тогда b^r ≡1 (mod p), и НОД(b^r −1 (mod n), n) будет делиться на p по малой теореме Ферма.

     Поэтому на 2 стадии (P − 1)-метода Полларда мы находим все простые числа r₁ , . . . , r_N, B < r₁ < r₂ < ...<r_N < B₁, и составляем разности      d_i = r_i − r_i−1, i=2, . . . , N. Эти разности обычно невелики и количество различных таких разностей также невелико (при подходящем выборе B₁). Затем мы табулируем элементы b^di (mod n) для всех различных

значений d_i.

     После этого в алгоритме мы находим 

x₁ ≡b^r1 (mod n), 

после чего вычисляем 

x_i ≡b^ri (mod n) ≡ x_i−1 * b^di (mod n), i= 2, . .., N,

и находим 

НОД(x_i −1 (mod n), n), i=1, . . . , N. 

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

     Замечание 1. Оценка сложности (P −1)-метода Полларда в худшем случае составляет O(n^1/2 log^c n) арифметических операций. Однако в некоторых случаях алгоритм может быстро выдать делитель числа n. Во всех случаях алгоритм хорошо находит небольшие простые делители n, потому что они являются степенно-гладкими для небольшой границы гладкости B.

     Замечание 2. Если какой-либо из вычисляемых в алгоритме наибольших общих делителей оказался равным n, то имеет смысл попробовать другое основание a, например, a= 3.

     На  практике (P − 1)-метод Полларда обычно используют

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

отделить  небольшие простые делители числа n.

p-метод Полларда. 

     С его помощью было разложено на множители число Ферма

     F₈ = 2²⁵⁶ + 1.

Схема p-метода.

     На  входе задано число n ∈ N, которое мы хотим разложить на множители.

     1 шаг. Выбрать отображение 

f : Z/nZ −→ Z/nZ. 

Обычно f (x) —многочлен степени большей или равной 2, например,             f (x) = x2 +1.

     2 шаг. Случайно выбрать x₀ ∈ Z/nZ и вычислять члены рекуррентной последовательности x₀, x₁, x₂, . . . по правилу 

x_i ≡ f (x_i−1) (mod n). 

     3 шаг. Для некоторых номеров j, k проверять условие 

1<НОД(x_j −x_k, n) <n 

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

     Конец алгоритма.

     Замечание 3. Выбор номеров j, k на третьем шаге алгоритма обычно делают одним из следующих способов.

     1. Для каждого j перебирают все k, k < j; это долго, и требуется большая память компьютера.

     2. Рассматривают пары k и 2k, т. е. проверяют условие                               1 < НОД(x_2k − x_k, n) < n.

     3. Если j заключено в пределах 2^h ≤ j < 2^h+1, где h ∈ N, то полагают        k = 2h − 1.

     Замечание 4. Основная идея p-метода очень проста. Если период последовательности x_i(mod n) может быть порядка n, то период последовательности x_i(mod p) для простого делителя p числа n не превосходит p. Это значит, что x_j и x_k могут быть различными по модулю n, но совпадать по модулю p, т.е. p | НОД(x_j −x_k, n).

     Утверждение 1. Пусть S — фиксированное множество из r элементов, f — какое-либо отображение f : S→S, x₀ ∈ S, последовательность x₀, x₁, x₂, . . . определяется соотношением x_j = f (x_j−1). Пусть λ > 0, l = 1 + [√2λr] < r. Тогда доля тех пар (f, x₀) (где f пробегает все отображения из S в S и x₀ пробегает все множество S), у которых x₀, x₁, x₂, . . . ,x_l попарно различны, среди всех пар (f, x₀) не превосходит e^−λ.