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

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

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

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

РЕФЕРАТ

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

на тему:

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

                                Выполнила: ст-ка 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².