Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "Algorithms of integer factorization", Toch, 2005, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.

Московский Физико-Технический Институт (ГУ МФТИ)

Кафедра радиотехники

20 мая 2005 г.

Эссе по курсу «Защита информации»

Алгоритмы факторизации целых чисел

(с экспоненциальной сложностью)

Выполнил:

Точ Дмитрий

116 гр.

http://www.re.mipt.ru/infsec

Введение

Сложностью задачи факторизации (разложение на множители) определяется сложность нахождения секретного ключа некоторых шифрсистем (например RSA). Поэтому при проектировании таких систем необходимо учитывать это обстоятельство. И дело здесь не только в производственной мощности современных компьютеров. В последнее время появляется все больше и больше алгоритмов факторизации, позволяющие факторизовать большие числа за короткий (по сравнению с другими) срок времени. Эта область в теории чисел активно развивается и представяет большой интерес для криптоаналитиков.

Прежде чем непосредственно перейти к рассмотрению алгоритмов, формализуем нашу задачу следующим образом: требуется найти простые множители p и q числа n, т.е. такие целые числа, что n=p*q. (Следует сразу оговорить ситуацию, когда число множителей более 2-ух: в этом случае один из них находится довольно быстро и сложность задачи резко падает)

В дальнейшем будем считать, что n не является простым (это можно проверить каким нибудь алгоритмом проверки на простоту), и раскладывается в произведение 2-ух простых чисел.

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

В этой работе будут рассмотрены (без доказательств) следующие алгоритмы с эспоненциальной оценкой сложности:

«Пробных делений»
Ферма (P. de Fermat)
ρ-метод Полларда (Pollard J. M)
Шермана-Лемана (Lehman R. S.)
Ленстры (Lenstra H. W.)
Полларда-Штрассена (Strassen V.)
(P-1)-метод Полларда

Алгоритм «пробных делений».

Самый тривиальный и очевидный. Но даже он имеет несколько вариантов реализации:

1) Перебираем последовательно все простые числа, не превосходящие , пока не доберемся до делителя числа n.
2) Перебираем все целые числа меньше , пока не доберемся до делителя n.

У каждой из этих реализаций есть свои преимущества и недостатки по сравнению с другой:

1) необходимо строить таблицу простых чисел
2) требуется больше операций деления

Соответствующие сложности этого алгоритма для данных реализаций:

1)
2)

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

Алгоритм Ферма.

Этот алгоритм был впервые предложен французским математиком Пьером Ферма в 1643г. Он позволяет находить наибольший делитель n (в отличие от алгоритма пробных делений, который лучше подходит для поиска наименьшего делителя). Поэтому этот алгоритм очень хорош в случае, когда множители числа n примерно одинаковы по величине.

Пусть p и q удовлетворяют условию . Представим их в виде , , где числа u и v – натуральные. Т.к. p и q – нечетные (иначе один из сомножителей был бы уже известен), то такое представление возможно: , . Алгоритм основан на представлении числа n в виде , откуда нетрудно заметить .

Введем последовательность {}, введем переменную . Теперь вступает в силу следующий алгоритм:

1.
2. Если , то . Алгоритм останавливается, результатом будут числа и .
3. Иначе
a. Если , то ().
b. Если , то ().
4. Go to 2.

Сложность алгоритма Ферма , где С - некоторый параметр, определяемый практически из конкретных вычислительных возможностей.

ρ - Метод Полларда.

С помощью этого метода было впервые факторизовано число Ферма . Впервые этот алгоритм был предложен Дж. Поллардом в 1975 г. Суть его заключается в следующем:

1. Выбираем отображение , где - кольцо вычетов по модулю n. В качестве функции обычно берут полиномы степени ≥2 (например ).
2. Выбираем некоторое число и строим рекурсивную последовательность по следующему принципу .
3. Для некоторых номеров i и j вычисляем . Если или , то рассматриваем другую пару . Если , то d – делитель числа n.

Как видим, алгоритм может оказаться довольно громоздким из-за большого количества пар . Эта проблема решаема с помощью некоторых способов выбора номеров i и j. Рассмотрим некоторые из них:

1. , т.е.
2. Если j удовлетворяет условию , то берут

Если окажется, что алгоритм не нашел делителя, то можно попробовать другие функции f, например , где с – некоторая константа.

Сложность этого алгоритма оценивается, как битовых операций. Существует теорема, которая формулируется так: Пусть n – составное число, вероятность того, что метод Полларда не сможет найти нетривиальный делитель n за время не превышает величину .

ρ - Метод Полларда обычно используется для нахождения небольших делителей числа n.

Алгоритм Шермана-Лемана.

Предположим, что n – нечетно и .

1. Проверяем, являются ли числа делителями числа n. Если получен отрицательный результат, идем дальше.
2. Т.к. делителя не найдено, то . Для всех и проверяем, является ли число квадратом натурального числа. Если да, то числа и удовлетворяют условию . Теперь проверяем условие , и если оно выполнено, то алгоритм завершается.

Сложность этого алгоритма составляет арифметических операций. Этот алгоритм позволяет эффективно использовать параллельные вычисления.

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

Приведем без доказательства следующую теорему: Пусть r, s, и n – натуральные числа такие, что , и . Тогда найдется не более 11 чисел - делителей n, и таких, что , и имеется алгоритм, который находит все эти делители за арифметических операций.

Также можно доказать, что : при условии , и существует не более положительных делителей n, сравнимых с r по модулю s.

Перейдем теперь непосредственно к самому алгоритму. Полагаем, что на входе у нас даны числа r, s, и n, удовлетворяющие условию теоремы.

1. Находим такой, что , и r’ такой, что

2. Вводим последовательность , удовлетворяющую следующим условиям: , и при , где числа определяются однозначно из условий Т.е. фактически - частное от деления на за исключением случая, когда i – нечетно и остаток от деления равен 0.

3. Для очередного i найти все целые с, удовлетворяющие следующим условиям: и . Таких с будет не более 2-ух.
4. Для каждого с решаем в целых числах следующую систему уравнений Если , то - искомый делитель.
5. Если 0, то алгоритм закончен. Иначе Go to 2.

Оценка сложности алгоритма Ленстры .

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

Этот алгоритм основан на следующей теореме: Пусть , . Тогда наименьший простой делитель числа может быть найден за двоичных операций. Опуская доказательство, перейдем к способу, с помощью которого можно найти наименьший простой делитель числа .

Положим .

1. Находим
2. Вычисляем до получения первого нетривиального делителя.
3. Осуществляя пробные деления на числа (, …, (), находим наименьший простой делитель числа .

Для факторизации числа n берут . Находят наименьший простой делитель числа . Т.к. , то y! делится на наименьший простой делитель p числа n. Именно число p выдаст алгоритм.

Сложность рассмотренного алгоритма .

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

Прежде чем начать рассмотрение этого алгоритма введем определение: будем говорить, что число k является B-степенно-гладким для некоторого B>0, если : m – простое и является делителем числа k, выполнено условие , где - наибольшее число такое, что делит k.

Теперь непосредственно сам алгоритм:

1. Исходя из возможностей нашей вычислительной машины, выбираем границу гладкости B. Обычно B~.
2. Выбираем произвольное целое число a, удовлетворяющее условию , и вычисляем . Если , то d – искомый делитель.
3. Строим таблицу всех простых чисел и для каждого такого числа находим , т.е. .
4. Вычисляем
5. Находим . Если , то d – искомый делитель, иначе алгоритм не смог найти делитель. В этом случае можно взять другое основание a или границу гладкости.

Оценка сложности этого метода в худшем случае составляет арифметических операций. Однако в некоторых случаях этот алгоритм может довольно быстро найти делитель n.

Другие алгоритмы. Заключение.

Для некоторых чисел n существуют специальные алгоритмы факторизации. Приведем без доказательства следующую теорему: Пусть . Если p – простое и делит n, то выполнено одно из 2-ух следующих утверждений:

1. p является делителем при некотором d<k, делящем k.
2. . Причем если p>2 и k – нечетно, то .

Посмотрим, как можно воспользоваться этой теоремой, на следующем примере: . Первое утверждение не выполняется, значит , т.е. .

Итак, мы рассмотрели основные алгоритмы факторизации наиболее известные на данный момент. В работу не вошли описания некоторых алгоритмов, которые требуют применения дополнительных теоретических основ. Например, методы Шэнкса (Shanks D.), использующие бинарные квадратичные нормы и имеющие наилучшие из всех рассмотренных выше алгоритмов оценки сложности: для алгоритма, работающего с положительно определенными бинарными квадратичными формами отрицательного дискриминанта, и - положительного (этот метод носит название SQUFOF). Метод SQUFOF работает с числами, не превосходящими и среди алгоритмов с экспоненциальной сложностью считается одним из самых лучших.

Есть метод аналогичный (P-1)-методу Полларда, но использующий разложение числа Р+1 (с помощью последовательностей чисел Люка (Lucas F. A.)). Он носит название (Р+1)-метод Уильямса (Williams H. C.). Но на практике этот алгоритм оказывается довольно медленным, поэтому используется редко.

Также можно упомянуть алгоритм Ривеста-Пинтера (Rivest R. L.) со сложностью и метод Лемера-Пауэрса (Lehmer D. H.) с эвристической оценкой сложности , использующий разложение в непрерывную дробь.

Из описанных выше алгоритмов наибольшей популярностью пользуются ρ-метод Полларда, алгоритм Полларда-Штрассена и (P-1)-метод Полларда. Применяются они, как правило, в сочетании с алгоритмами с субэкспоненциальной оценкой сложности (оценка сложности задается формулой , где , ). Таким образом процесс факторизации распадается на 3 этапа:

1. Перебор первых 1-2 тыс. простых чисел.
2. С помощью какого-нибудь алгоритма с экспоненциальной сложностью ищут небольшие простые делители.
3. С помощью какого-нибудь алгоритма с субэкспоненциальной сложностью ищут большие простые делители.

Иногда перед вторым этапом можно сделать проверку на простоту с помощью какого-нибудь специального алгоритма.

Из алгоритмов, имеющих субэкспоненциальную оценку сложности, наиболее популярны метод Диксона (Dixon J. D.), алгоритм Бриллхарта-Моррисона (Brillhart J., Morrison M. A.), методы Шнорра-Ленстры (Schnorr C. P.) и Ленстры-Померанса (Pomerance C.), квадратичное решето и (самые эффективные для факторизации больших чисел) алгоритмы решета числового поля. А также следует упомянуть об алгоритме Ленстры для факторизации чисел с использованием эллиптических кривых.

Литература:

1. О. Н. Василенко «Теоретико-числовые алгоритмы в криптографии» МЦНМО, 2003 (http://www.cryptography.ru:8200/pubd/2003/12/04/0001169580/book.pdf)
2. А. В. Черемушкин «Лекции по арифметическим алгоритмам в криптографии» МЦНМО, 2002 (http://www.cryptography.ru:8200/pubd/2003/02/24/0001169266/cherem.pdf)
3. A. Menezes, P. van Oorschot, S. Vanstone „Handbook of Applied Cryptography” CRC Press, 1996
4. М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко «Криптография в банковском деле» М.: МИФИ, 1997 (http://www.cryptography.ru/db/msg.html?mid=1169307&uri=node189.html)


Page last update: Fri Jun 10 10:19:16 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru