Сравнительный анализ методов факторизации натуральных чисел

 

Содержание

Введение

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

.1 Факторизация натурального числа

.2 Перебор делителей

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

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

1.5 ?-алгоритм Полларда

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

.7 Метод Лемана

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

.9 Факторизация методом непрерывных дробей

.10 Метод квадратичного решета

.11 Факторизация с помощью эллиптических кривых

.12 Специальный метод решета числового поля

.13 Общий метод решета числового поля

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

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

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

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

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

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

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

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

.1.7 Факторизация с помощью эллиптических кривых

.2 Факторизация в криптографии

.3 Примеры применения алгоритмов факторизации натуральных чисел в программной среде Maple

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

Заключение

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

Приложение

ВВЕДЕНИЕ

В настоящее время исследования в области построения быстрых алгоритмов факторизации интенсивно ведутся во всем мире. Ежегодно проводятся десятки конференций по этой тематике, достигаются новые рекорды факторизации длинных чисел, исследуются известные проблемы алгоритмической теории чисел и ставятся новые проблемы. Недавно (в конце 2009 г.) коллективом европейских ученых, возглавляемым Торштеном Кляйнъюнгом, был установлен новый рекорд по разложению 768- битового натурального числа с помощью метода решета числового поля. Предыдущий рекорд в 512-бит был установлен в 2000 г., т.е. переход от 512- битовых к 768-битовым числам потребовал почти 10 лет. Поэтому следующий рекорд в 1024 бита при сохранении прежних темпов роста исследований планируется выполнить не ранее, чем в 2020 г.

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

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

Целью написания работы является проведение сравнительного анализа методов факторизации натуральных чисел. В ходе работы были поставлены следующие задачи:

.Рассмотреть алгоритмы факторизации натуральных чисел;

.Провести сравнительную характеристику методов факторизации по группам сложности;

.Рассмотреть выбранные методы факторизации на практических примерах;

Объектом изучения данной работы является подборка методов факторизации натуральных чисел.

Предмет - практические примеры как результат применения того или иного метода.

В данной работе были рассмотрены следующие методы факторизации натуральных чисел:

Экспоненциальные алгоритмы

-Перебор возможных делителей

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

-?-алгоритм Полларда

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

-метод Лемана

Субэкспоненциальные алгоритмы

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

-метод непрерывных дробей

-метод квадратичного решета

-метод эллиптических кривых

Решето числового поля

Специальный метод решета числового поля

Общий метод решета числового поля

Научная постановка и разработка отдельных сторон исследования темы нашла свое отражение в работах отечественных ученых-математиков. При написании работы были использована учебная и периодическая литература следующих авторов: Панчишкин А.А., Нестеренко Ю.В., Бухштаб А.А. и др.

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

.1 Факторизация натурального числа

Натуральное число называется простым, если оно делится только на себя и на 1. Число, не являющееся простым, называется составным. Очевидно, что любое простое число, не равное 2, является нечетным. Существуют признаки делимости целых чисел на различные простые числа, например, чтобы число в десятичном виде делилось на 3 и 9 достаточно, чтобы сумма его цифр делилась на 3 и 9 соответственно. Чтобы число делилось на 5, достаточно, что его последняя цифра была 0 или 5. Такие частные признаки делимости можно использовать, если нужно уменьшить множество кандидатов проверки на простоту или отсечь заведомо составные числа. Альтернативным способом получения простых чисел является решето Эратосфена, приписываемое древнегреческому ученому Эратосфену Киренскому, жившему примерно в 276 - 194 г. до н.э. Для нахождения множества простых до заранее выбранной верхней границы B мы сначала выписываем последовательность всех нечетных чисел от 3 до B. Затем выбираем первое число в списке, т.е. тройку, и оставляя его в списке, вычеркиваем все кратные 3, начиная с 6. Потом переходим ко второму числу списка (пятерке) и вычеркиваем его кратные, оставив саму пятерку и т.д., пока не дойдем до конца списка. В оставшемся списке будут только простые числа.

Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики.

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

В данной работе были рассмотрены следующие методы факторизации натуральных чисел:

Экспоненциальные алгоритмы

-Перебор возможных делителей

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

-?-алгоритм Полларда

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

-метод Лемана

Субэкспоненциальные алгоритмы

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

-метод непрерывных дробей

-метод квадратичного решета

-метод эллиптических кривых

Решето числового поля

-Специальный метод решета числового поля

-Общий метод решета числового поля

Сложность факторизации

В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа - экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих параметров (то есть от длины самого числа в бинарном представлении). Для обозначения их сложности принята O-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.
Например, в функции при достаточно больших компонента будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида . Фраза «алгоритм факторизации с вычислительной сложностью » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем .
Вторая группа - субэкспоненциальные алгоритмы, это алгоритмы, которые работают более, чем за полиномиальное время («сверх-полиномиальное»), но менее, чем за экспоненциальное время («субэкспоненциальное»). Для обозначения их сложности принята L-нотация:

где N - число, подлежащее факторизации, и c - некоторые константы.

·Экспоненциальные алгоритмы

-Перебор возможных делителей - наиболее тривиальный алгоритм факторизации с вычислительной сложностью .

?-алгоритм Полларда имеет сложность ;

метод квадратичных форм Шенкса имеет сложность ;

метод Лемана имеет сложность

·Субэкспоненциальные алгоритмы

алгоритм Диксона имеет сложность ;

метод непрерывных дробей имеет сложность ;

метод квадратичного решета имеет сложность ;

метод эллиптических кривых имеет сложность , где - наименьшее простое, которое делит .

·Решето числового поля

В настоящее время самыми эффективными алгоритмами факторизации являются вариации решета числового поля:

Специальный метод решета числового поля со сложностью (метод применим для факторизации чисел только специального вида);

Общий метод решета числового поля со сложностью (метод применим ко всем числам).

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

Описание наиболее известных методов факторизации натуральных чисел.

факторизация натуральный число алгоритм

1.2 Перебор делителей

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

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

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.

Практическое применение

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

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

Метод факторизации Ферма - алгоритм факторизации (разложения на множители) нечётного целого числа , предложенный Пьером Ферма (1601-1665) в 1643 году.

Метод основан на поиске таких целых чисел и , которые удовлетворяют соотношению , что ведёт к разложению.

Обоснование

Метод Ферма основан на теореме о представлении числа в виде разности двух квадратов:

Если нечетно, то существует взаимно однозначное соответствие между разложениями на множители и представлениями в виде разности квадратов с , задаваемое формулами

Доказательство

Если задана факторизация , то имеет место соотношение: . Таким образом, получается представление в виде разности двух квадратов.

Обратно, если дано, что , то правую часть можно разложить на множители: .

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

Для разложения на множители нечётного числа ищется пара чисел таких, что , или . При этом числа и являются множителями , возможно, тривиальными (то есть одно из них равно 1, а другое - .)

Равенство равносильно , то есть тому, что является квадратом.

Поиск квадрата такого вида начинается с - наименьшего числа, при котором разность неотрицательна. Для каждого значения начиная с , вычисляют и проверяют, не является ли это число точным квадратом. Если не является - то увеличивают на единицу и переходят на следующую итерацию.

Если является точным квадратом, т.е. то получено разложение:

в котором

Если оно является тривиальным и единственным, то - простое.

На практике значение выражения на -ом шаге вычисляется с учетом значения на -ом шаге:

где

Таким образом, как и метод пробного деления, алгоритм Ферма имеет экспоненциальную оценку и не эффективен для разложения длинных чисел. Можно улучшить метод Ферма, выполнив сначала пробное деление числа n на числа от 2 до некоторой константы B, исключив тем самым малые делители n до B включительно, и только потом выполнить поиск методом Ферма.

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

Обобщение метода Ферма было предложено Морисом Крайчиком (1882-1957). Он предложил рассматривать вместо пар чисел которые удовлетворяют соотношению искать пары чисел, удовлетворяющих более общему уравнению Крайчик заметил, что многие из чисел, получаемых по формуле раскладываются на простые множители, т.е. числа являются гладкими.

Последовательность действий по Крайчику

1. Найти множество пар которые удовлетворяют соотношению

. Определить полное или частное разложение чисел и на множители для каждой пары

. Выбрать пары произведение которых удовлетворит соотношению

. Разложить число на множители.

1.5 ?-алгоритм Полларда

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

?-aлгоритм Джона Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основывается на алгоритме Флойда поиска длины цикла в последовательности и некоторых следствиях из парадокса дней рождений. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается, как .

Во всех ?-методах Полларда строится числовая последовательность, элементы которой образуют цикл, начиная с некоторого номера n, что может быть проиллюстрировано, расположением чисел в виде греческой буквы ?. Это и послужило названием семейству методов.

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

Оригинальная версия

Рассмотрим последовательность целых чисел , такую что и , где - число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом.

. Будем вычислять тройки чисел

, где .

Причем каждая такая тройка получается из предыдущей.

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

. Если , то найдено частичное разложения числа , причем .

Найденный делитель может быть составным, поэтому его также необходимо факторизовать. Если число составное, то продолжаем алгоритм с модулем .

. Вычисления повторяются раз. Например, можно прекратить алгоритм при . Если при этом число не было до конца факторизовано, можно выбрать, например, другое начальное число .

Современная версия

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

1.Выбираем небольшое число и строим последовательность , определяя каждое следующее как .

2.Одновременно на каждом i-ом шаге вычисляем для каких-либо , таких, что , например, .

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

Как на практике выбирать функцию ? Функция должна быть не слишком сложной для вычисления, но в то же время не должна быть линейным многочленом, а также не должна порождать взаимно однозначное отображение. Обычно в качестве берут функцию или . Однако не следует использовать функции и .

Если известно, что для делителя числа справедливо при некотором , то имеет смысл использовать .

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

Улучшения алгоритма

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

Пусть . Заметим, что если , то , поэтому, если пара дает нам решение, то решение даст любая пара .

Поэтому, нет необходимости проверять все пары , а можно ограничиться парами вида , где , и пробегает набор последовательны значений 1, 2, 3, ..., а принимает значения из интервала . Например, , , а .

Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25%.

Еще одна вариация P-метода Полларда была разработана Флойдом. Согласно Флойду, значение обновляется на каждом шаге по формуле , поэтому на шаге i будут получены значения , , и НОД на этом шаге вычисляется для и .

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

Это метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом в 1975 году, как развитие метода факторизации Ферма.

Для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами из алгоритмов факторизации для чисел между до и, вероятно, таковым и останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду. Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел типа чисел Ферма.

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

Для того чтобы понять, как реализован этот алгоритм, необходимо узнать минимальные сведения о математических объектах, используемых в данном методе, а именно о квадратичных формах. Бинарной квадратичной формой называется полином от двух переменных и :

В методе Шенкса используются только неопределенные формы. Под будем понимать дискриминант квадратичной формы. Будем говорить, что квадратичная форма представляет целое число , если существуют такие целые числа , что выполнено равенство: . В случае если выполнено равенство , то представление называется примитивным.

Для любой неопределенной квадратичной формы можно определить оператор редукции как:

,

где - определено, как целое число , однозначно определяемое условиями:

Результат применения оператора к форме раз записывается в виде . Также определен оператор как:

,

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

Метод получения редуцированной формы, эквивалентной данной, был найден еще Карлом Гауссом и состоит в последовательном применении оператора редукции , пока не станет редуцированной.

Теорема.

Каждая форма эквивалентна некоторой редуцированной форме, и любая редуцированная форма для равна для некоторого положительного . Если - редуцирована, то также редуцирована.

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

Варианты

Идея метода Шенкса состоит в сопоставлении числу , которое надо разложить квадратичной бинарной формы с дискриминантом , с которой потом выполняется серия эквивалентных преобразований и переход от формы к неоднозначной форме . Тогда, будет являться делителем .

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

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

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

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

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

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

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

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

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

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

1.7 Метод Лемана

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

Алгоритм

Пусть нечетно и .

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

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

или .

В этом случае для проверяется неравенство . Если оно выполнено, то - разложение на два множителя.

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

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

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

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

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

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

Алгоритм Диксона - алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и

Метод Диксона является обобщением метода Ферма.

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

1.Составить факторную базу , состоящую из всех простых чисел , где .

2.Выбрать случайное и вычисляется .

.Вычислить .

4.Проверить число на гладкость пробными делениями. Если является <#"46" src="doc_zip265.jpg" />, следует запомнить вектора и :

.

5.Повторять процедуру генерации чисел до тех пор, пока не будет найдено -гладких чисел .

6.Методом Гаусса найти линейную зависимость среди векторов :

и положить:

.

7.Проверить . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

1.9 Факторизация методом непрерывных дробей

В теории чисел факторизация методом непрерывных дробей (CFRAC) - это алгоритм факторизации целых чисел. Это алгоритм общего вида, пригодный для факторизации любого целого n не опирающийся на специальные формы или свойства. Он был найден Д. Г. Лемером и Р. Е. Поверсом в 1931-ем году, и переработан в алгоритм для компьютера Михаэлем А. Моррисоном и Джоном Бриллхартом в 1975-ом.

Метод непрерывных дробей основывается на алгоритме Диксона. Он использует непрерывную дробь, сходящуюся к .

1.10 Метод квадратичного решета

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

Основные цели

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

Один из простых методов отыскания равных квадратов заключается в том, чтобы выбрать случайное число, возвести его в квадрат и надеяться, что остаток от деления на n является квадратом какого-либо другого числа. Например, 802 mod 5959 = 441 = 212. Этот способ находит равные квадраты лишь в редких случаях для больших n, но если он действительно найдет эти числа, то можно считать, что факторизация завершена. Этот метод похож на метод факторизации Ферма.

Метод квадратичного решета является модификацией метода разложения на множители Диксона.

Продолжительность расчёта для квадратичного решета (n - факторизуемое число):

.

Подход

Пусть x mod y обозначает остаток от деления x на y. В методе факторизации Ферма в отдельности подбираем число a, чтобы a2 mod n являлось квадратом. Но такое число подобрать тяжело. В квадратичном решете мы вычисляем a2 mod n для некоторых a, и затем находим такое подмножество, произведение элементов которого является квадратом. Это приведёт к сравнению квадратов.

Например, 412 mod 1649 = 32, 422 mod 1649 = 115, и 432 mod 1649 = 200. Ни один из полученных результатов не является квадратом, но результат произведения (32)(200) = 6400 = 802. С другой стороны, рассмотрев предыдущее произведение по mod 1649, мы получим, что (32)(200) = (412)(432) = ((41)(43))2. Так как (41)?(43) mod 1649 = 114, мы имеем сравнение квадратов: 1142 ? 802 (mod 1649).

Но как мы решаем проблему, фиксируя множество чисел и, находя подмножество, произведение элементов, которого является квадратом? Начнём с понятия вектор показателей степеней. Например, что у нас есть число 504. Его разложение на простые множители имеет следующий вид 504 = 23325071. Мы могли бы представить это разложение в виде вектора показателей степеней (3,2,0,1), который фиксирует степени простых чисел 2, 3, 5 и 7, участвующих в разложении. Число 490 по аналогии имело бы вектор (1,0,1,2). Умножение чисел - это то же самое, что и поэлементное сложение их векторов показателей степеней, то есть произведение 504 ? 490 имеет вектор (4,2,1,3).

Теперь обратите внимание, что число является квадратом, если каждый элемент в его векторе показателей степеней чётный. К примеру, при сложении векторов (3,0,0,1) и (1,2,0,1) получаем (4,2,0,2). Это говорит нам о том, что произведение чисел 56 ? 126 является квадратом. На самом деле, мы не заботимся о точных значениях, получаемых в векторе, до тех пор, пока каждый элемент в результирующем векторе чётный. По этой причине мы берём каждый элемент по mod 2 и выполняем сложение элементов по mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0).

Таким образом, наша задача приняла следующий вид: задано множество векторов (0,1), найти такое подмножество, которое дополняется до нулевого вектора, при использовании сложения по mod 2. Это задача линейной алгебры, то есть необходимо найти линейно зависимые вектора. Из теоремы линейной алгебры следует, что, до тех пор, пока количество векторов больше, чем количество элементов в каждом векторе, такая зависимость должна существовать. Мы можем эффективно находить линейно зависимые векторы, например, поместив исходные векторы, в качестве столбцов матрицы и затем, использовать метод Гаусса, который легко приспособить для работы с целыми числами по mod 2. Как только мы найдём линейно зависимые векторы, мы просто перемножаем числа, соответствующие этим векторам и получаем квадрат, который ищем.

Однако, возведение в квадрат множества случайных чисел по mod n приводит к большому числу различных простых множителей, длинным векторам и большой матрице. Чтобы избавиться от этой проблемы, мы специально ищем числа, такие, что a2 mod n имеет только небольшие простые множители (такие числа называются гладкими числами). Их сложнее найти, но использование таких чисел позволяет избежать больших векторов и матриц.

Основная идея метода

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

Множество целых чисел, в котором ищутся -числа (-число - целое число, делящееся только на простые числа из ) выглядит следующим образом:

Далее, вместо того, чтобы брать одно за другим , и делить его на простые числа из , берутся одно за другим каждое и проверяется делимость на (и его степени) одновременно для всех . Для построения списка всех простых , не превосходящих , можно использовать решето Эратосфена.

Алгоритм

. Выбираются границы и порядка величины (далее обозначается как ), такие что .

. Для , ,…, по порядку в столбец выписываются целые числа .

. Для каждого нечетного простого числа проверяется условие . Если оно не выполняется, удаляется из факторной базы.

. Предполагая, что - такое нечетное простое число, что - квадратичный вычет по модулю , решается уравнение для 1,2,… . Значения берутся в порядке возрастания пока не окажется, что уравнение не имеет решений , сравнимых по модулю с каким-либо из чисел в области .

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

Пусть и решения и .

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

. При добавлении очередной единицы к числу в столбце в п.5, соответствующее число делится на и полученный результат сохраняется.

. В столбце под при просто ставится 1 против с нечетным и соответствующее делится на 2. При решается уравнение и решение продолжается в том же ключе, как при нечетном .

. Когда все указанные действия будут проведены для всех простых чисел, не превосходящих , следует отбросить все числа , кроме обратившихся в 1 после деления на все степени , не превосходящих . В итоге получится таблица, в которой в столбце будут содержаться все такие значения из интервала , что есть -число, а остальные столбцы будут соответствовать тем значениям , для которых - квадратичный вычет.

. Далее используется обобщенный метод факторизации Ферма (метод факторных баз).

1.11 Факторизация с помощью эллиптических кривых

Алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.

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

Алгоритм

Дано составное целое нечетное число . Нужно найти его нетривиальный делитель , .

Случайным образом выбирается эллиптическая кривая

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

. Выбирается целое число , делящееся на степени малых простых чисел (не больших некоторого ), не превосходящих , то есть

где - наибольший из возможных показателей, при котором .

. Вычисление (все действия производятся по модулю n)

где - операция сложения, определенная по групповому закону.

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

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

Обоснование

Если числа p и q - два простых делителя числа n, то эллиптическая кривая y2 = x3 + ax + b (mod n) соответствует двум эллиптическим кривым: по модулю p и по модулю q. Эти две кривые с заданной операцией сложения точек образуют группы, содержащие Np и Nq элементов, соответственно. По теореме Лагранжа для любой точки Р на исходной кривой по модулю p из равенства для минимального положительного числа k следует, что k делит Np (в частности, ). Аналогичное утверждение справедливо и для кривой по модулю q. Для случайно выбранной эллиптической кривой порядки Np и Nq являются случайными числами, близкими к p+1 и q + 1, соответственно (см. ниже). Поэтому маловероятно, что большинство простых делителей Np и Nq совпадают, и вполне вероятно, что при вычислении eP мы столкнёмся с некоторыми по модулю р, но не по модулю q, или наоборот. Если это так, то kP не существует на исходной кривой, а в вычислениях мы нашли такое v, что либо НОД (v, p) = p, либо НОД (v, q) = q, но не одновременно. Тогда НОД (v, n) является нетривиальным делителем числа n.

1.12 Специальный метод решета числового поля

Специальный метод решета числового поля является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел . Метод эффективен для целых чисел вида re ± s, где r N s Z, r и s невелики(например Числа Мерсенна).

Эвристическая оценка сложности факторизации числа n выражается формулой:

С помощью SNFS было разложено на множители число Ферма , содержащее 155 десятичных цифр.

Обзор метода

SNFS основан на более простом методе рационального решета. Читателю предлагается ознакомиться с данным методом до изучения SNFS.
SNFS работает следующим образом. Пусть n число для факторизации. Аналогично методу рационального решета, алгоритм SNFS может быть разбит на два шага:
·Нахождение числа мультипликативных соотношений факторной базы Z/nZ, большего чем число элементов в факторной базе.

·Перемножение соотношений между собой таким образом, чтобы степени полученных произведений были одинаковыми, то есть получение соотношений вида a2?b2(mod n). Это в свою очередь приведет к факторизации n: n=НОД(a+b,n)×НОД(a-b,n). В случае, если полученное разложение является тривиальным (то есть n=n×1), следует искать другие произведения соотношений, удовлетворяющие данному условию.

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

Детали метода

Пусть n - это факторизуемое число. Возьмем неприводимый многочлен f и целое число m, такое что f(m)?0 (mod n) (принципы их выбора будут объяснены в следующем разделе). Пусть ? корень f; тогда существует кольцо Z[?]. Тогда существует единственное кольцо гомоморфизма (англ.) ? между Z[?] и Z/nZ, которое отображает ? в m. Для простоты полагаем, что Z[?] является факториальным кольцом; метод может быть модифицирован для случая, когда это условие не выполняется, что приведет к дополнительным вычислениям.

Затем создадим две факторных базы, одну для Z[?] и одну для Z. Факторная база Z[?] содержит все простые числа Z[?], чей размер ограничен значением . Факторная база Z, как и в методе рационального решета, состоит из простых чисел до некоторого граничного числа.

Затем ищем такие взаимно простые числа (a,b) что:

·a+bm является гладким по отношению к элементам факторной базы Z (то есть все его простые делители содержатся в факторной базе).

·a+b? является гладким по отношению к элементам факторной базы Z[?];из того как мы выбирали элементы факторной базы, это условие эквивалентно тому, что a+b? делится только на простые числа, меньшие .

Эти пары чисел находятся методом просеивания, аналогичным методу решета Эратосфена; это объясняет название метода решета числового поля.

Для каждой такой пары чисел (a,b) мы можем применить кольцо гомоморфизма ? для факторизации a+b? и каноническое кольцо гомоморфизма от Z до Z/nZ для факторизации a+bm. Приравняв их, получим мультипликативные соотношения для элементов факторной базы Z/nZ. Найдя достаточное количество таких соотношений, перемножаем их между собой, как описано выше.

Ограничения

Этот метод, как подмечено выше, очень эффективен для чисел вида re±s, где r и s относительно маленькие. Он также эффективен для чисел, представимых в виде полинома с небольшими коэффициентами. Дело в том, что специальный метод решета числового поля производит просеивание для двух числовых полей. Эффективность метода сильно зависит от размера определенных элементов в этих полях. Если число можно представить в виде полинома с маленькими коэффициентами, числа, с которыми производятся вычисления, намного меньше чисел, с которыми приходится иметь дело, если такого полинома не существует.

1.13 Общий метод решета числового поля

Суть метода

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

Основные принципы

·Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что , что ведет к разложению .

·Нахождение подмножества множества целых чисел, произведение которых - квадрат

·Составление факторной базы: набора , где pi - простые числа такие, что для некоторого B.

·Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркиваются», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.

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

Алгоритм

Пусть - нечетное составное число, которое требуется факторизовать.

1.Выберем степень неприводимого многочлена (при не будет выигрыша в сравнении с методом квадратичного решета).

2.Выберем целое такое, что , и разложим n по основанию :

(1)

3.Свяжем с разложением (1) неприводимый в кольце полиномов с целыми коэффициентами многочлен

4.Определим полином просеивания как однородный многочлен от двух переменных и :

(2)

5.Определим второй полином и соответствующий однородный многочлен .

6.Выберем два положительных числа и , определяющих область просеивания (англ. sieve region):

7.Пусть - корень . Рассмотрим кольцо полиномов . Определим множество, называемое алгебраической факторной базой , состоящее из многочленов первого порядка вида с нормой (2), являющейся простым числом. Эти многочлены - простые неразложимые в кольце алгебраических целых поля . Ограничим абсолютные значения норм полиномов из константой .

8.Определим рациональную факторную базу , состоящую из всех простых чисел, ограниченных сверху константой .

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

.Выполним просеивание многочленов по факторной базе и целых чисел по факторной базе . В результате получим множество , состоящее из гладких пар , то есть таких пар , что НОД(a,b) = 1, полином и число и раскладываются полностью по и соответственно.

.Найдём такое подмножество , что

12.Определим многочлен

где - производная

13.Многочлен является полным квадратом в кольце полиномов . Пусть тогда есть корень из и - корень из .

14.Строим отображение , заменяя полином числом . Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел в кольцо , откуда получаем соотношение:

15.Пусть . Найдём пару чисел таких, что . Тогда найдём делитель числа , вычисляя НОД(n, A ± B), как это делается, например, в методе квадратичного решета.

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

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

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

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

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

136319,052257624

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

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

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

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

7752374228,8547853129230,4977953886232,1348054645233,7638155406235,3858256169237

Данное разложение является не конечным, т.к., очевидно, что число не является простым. Применив метод Ферма, получимВ итоге, конечное разложение исходного числа на произведение простых множителей

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

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

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

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

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

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

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

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

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

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

Пусть , , , .

ixiyiНОД(|xi ? yi|, 8051)1526122674741367787197

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

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

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

Цикл №1Цикл №2

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

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

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

Для всех и всех проверяем, является ли число квадратом натурального числа. В нашем случае существуют такие и , что выражение является полным квадратом и равно . Следовательно, и . Тогда , удовлетворяет неравенству и является делителем числа . В итоге, мы разложили число на два множителя: и .

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

Факторизуем число .

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

337238141502004305390101210519965100006009802012006701250030008173920424002086021560301210

Решая линейную систему уравнений, получаем, что . Тогда

Следовательно,

.

Получилось разложение

2.1.7 Факторизация с помощью эллиптических кривых

Допустим, нам нужно факторизовать число n = 455839.

Возьмем эллиптическую кривую и точку, лежащую на этой кривой

Попробуем вычислить 10!P:

Для начала вычислим координаты точки . Тангенс угла наклона касательной в точке P равен:

Находим координаты точки :

.

-Проверяем, что точка 2P действительно лежит на кривой:

. Теперь вычислим .

Тангенс угла наклона касательной в точке 2P составляет

.

Для вычисления 593 / 106 по модулю n можно воспользоваться расширенным алгоритмом Евклида: 455839 = 4300·106 + 39, далее 106 = 2·39 + 28, далее 39 = 28 + 11, далее 28 = 2·11 + 6, далее 11 = 6 + 5, далее 6 = 5 + 1. Откуда получаем, что НОД(455839, 106) = 1, и в обратную сторону: 1 = 6 - 5 = 2·6 - 11 = 2·28 - 5·11 = 7·28 - 5·39 = 7·106 - 19·39 = 81707·106 - 19·455839. Откуда 1/106 = 81707 (mod 455839), таким образом, -593 / 106 = 322522 (mod 455839).

Учитывая вычисленное s, мы можем вычислить координаты точки 2(2P), так же, как это было сделано выше: 4P = (259851, 116255). Проверяем, что точка действительно лежит на нашей эллиптической кривой.

Суммируя 4P и 2P, находим .

Аналогичным образом можно вычислить , , и так далее. Когда дойдем до 8!P заметим, что требуется вычисление обратного элемента к 599 (mod 455839). Так как 455839 делится на 599, то мы нашли искомое разложение: 455839 = 599·761.

2.2 Факторизация в криптографии

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

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

·Если известно , то вычислить относительно просто

·Если известно , то для вычисления нет простого (эффективного) пути.

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

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом, так и закрытым ключом. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:

сообщения , где - множество допустимых сообщений

допустимых открытого и закрытого ключей и

соответствующие функции шифрования и расшифрования , такие что

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом:

1.Выбираются два различных случайных простых числа и заданного размера.

2.Вычисляется их произведение , которое называется модулем.

.Вычисляется значение функции Эйлера от числа :

4.Выбирается целое число , взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.

·Число называется открытой экспонентой.

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

·Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.

5.Вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее условию:

·Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

6.Пара публикуется в качестве открытого ключа RSA.

7.Пара играет роль закрытого ключа RSA секрете.

2.3 Примеры применения алгоритмов факторизации натуральных чисел в программной среде Maple

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

Далее приведены списки методов, которые включены в разные версии Maple.

В Maple 6:

'squfof' - метод Квадратичных форм Шенкса;

'pollard' - алгоритм Полларда;

'lenstra' - метод эллиптических кривых Ленстры;

'easy' - без дальнейшей обработки.

В последних версиях Maple:

'mpqs' - множественный полиномиальный метод квадратичного решета;

'morrbril' - алгоритм Брилхарта-Моррисона;

'squfof' - метод квадратичных форм Шенкса;

'pollard' - алгоритм Полларда;

'lenstra' - метод эллиптических кривых Ленстры;

'mpqsmixed' - 'mpqs', 'morrbril' и 'pollard';

'mixed' - 'morrbril' и 'pollard' (по умолчанию в версиях Maple 11 и более ранних)

'easy' - без дальнейшей обработки;

Easy - если данный вариант разложения будет выбран, результатом ifactor будет произведение чисел, которые легко было отделить, а также «_c.m._.n», которое обозначает m-значное составное число, которое не было разложено, где n - уникальный номер данного составного числа.

Pollard - метод Полларда, опционально требующий дополнительное целое k (ifactor(n,pollard,k)), которое повышает эффективность метода в том случае, если один из сомножителей имеет форму k*m+1.

В процессе написания данной работы мной была использована платформа Maple 6 для более детального рассмотрения различных алгоритмов факторизации натуральных чисел. Так как моей целью было проанализировать и сравнить некоторые алгоритмы, реализованные в среде Maple, и время их исполнения, я проделал следующие действия (см. Приложение, с.50):

.Для проверки времени исполнения алгоритмов для неструктурированного числа.

Сгенерировал два крупных простых числа посредством функций nextprime и prevprime;

Перемножил их и запустил для полученного числа процедуру ifactor без дополнительных параметров, с параметром squifof, pollard и lenstra. Так как мне нужно было время исполнения, я ипользовал функцию time от ifactor;

Получил значения для разных алгоритмов. Для алгоритма по умолчанию (алгоритм Моррисона-Брилхарта вместе с алгоритмом Полларда), получил значение 632,795 секунды.

Для squifof это значение было 0., то есть малейшие доли секунды. Алгоритм Полларда пришлось остановить на 308ой тысяче секунд(3,56 суток), алгоритм Ленстры дал результат через 20311,795 секунды.

.Далее я применил алгоритмы для структурированного числа вида k*(2^t+1).

Взял k равным простому числу 331, а t (степень двойки в выражении) равным 190. Нашёл значение выражения с этими данными;

Применил ifactor и нашёл время выполнения ifactor от нашего числа. Время выполнения составило 47193,554 секунды;

Далее я применил алгоритм squifof для числа той же структуры, но с большим показателем степени двойки, t = 9290. Данным алгоритмом число разложилось за 77.5 секунды;

.В третий раз я взял также структурированное число, но теперь это был факториал от данного числа t.

Я положил t равным 1221 и получил очень крупное число в 2800 знаков;

Воспользовавшись алгоритмом Ленстры, я получил время выполнения - всего 0,63 секунды.

Отсюда мы видим, что при изменении структуры числа, алгоритмы ведут себя по-разному. Применяя один и тот же алгоритм, для разложения числа с 2800 знаков требуется примерно в 32000 раз меньше времени, чем для разложения числа с 48 знаками. При этом структура числа различна. В первом случае в числе очень много небольших делителей, а во втором случае их всего два, и оба - крупные простые числа.

2.4 Оценка эффективности алгоритмов факторизации натуральных чисел

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

Алгоритм Ленстры на практике часто используется для выявления (отбрасывания) небольших простых делителей числа. И в этом мы убедились, разложив 32000-значное число 1221! за время в 0,63 секунды. Так как в числе 1221! содержатся все первые 1221 числа, то выявить и отбросить все тривиальные делители не составит труда. Однако если мы работаем с числом, содержащим в себе крупные простые множители, то нам нужно увеличивать количество кривых, так как при увеличении количества кривых шансы найти простой делитель возрастают, тем не менее, зависимость ожидаемого количества эллиптических кривых от количества цифр в искомом делителе экспоненциальна. Метод Полларда очень быстро находит простые факторы малой и средней величины, однако, столкнувшись с крупным простым сомножителем, становится малоэффективным.

Среди алгоритмов факторизации с экспоненциальной сложностью метод квадратичных форм Шенкса считается одним из самых эффективных. Этот алгоритм работает с целыми числами, не превосходящими . Мы знаем, что для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами из алгоритмов факторизации для чисел между до и, вероятно, таковым и останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду. Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел.

Заключение

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

Самым простым и самым трудоёмким экспоненциальным методом, реализуемым вручную, является подбор делителей. Он заключается в переборе потенциальных делителей числа в пределах от самого числа до его квадрата. Для разложения небольших чисел он вполне подходит, так как очень просто реализуется, но для разложения массивных чисел он практически непригоден.

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

В данной работе мы рассмотрели некоторые алгоритмы факторизации натуральных чисел, а также провели сравнительную характеристику оных по группам структур. На практических примерах мы убедились в эффективности и целесообразности применения одних методов перед другими, опять же с учётом структуры данного числа.

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

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

Список литературы

1.A. Heck. Introduction to Maple. Springer-Verlag, third edition, 2003.

2.Бухштаб А.А. Теория чисел. - М.: Учпедгиз, 1960.

3.Василенко О. Н. В19 Теоретико-числовые алгоритмы в криптографии. - М.:МЦНМО, 2003.-328 с. ISBN 5-94057-103-4.

.Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие. Казань: Казан. Ун-т, 2011. 190 с.

.Д. Кнут Раздел 4.5.4. Разложение на простые множители // Искусство программирования = The Art of Computer Programming. - 3-е изд. - М.: Вильямс, 2007. - Т. 2. Получисленные алгоритмы. - С. 425-468. - 832 с.

.Макаренко А.В., Пыхтеев А.В., Ефимов С.С. Параллельная реализация и сравнительный анализ алгоритмов факторизации в системах с распределённой памятью.

.Манин Ю.И., Панчишкин А.А. Введение в современную теорию чисел. - М.: МЦНМО, 2009.

8.Ю. И. Манин, А. А. Панчишкин. I.2.3. Разложение больших чисел на множители // Введение в теорию чисел.- М.: ВИНИТИ, 1990. - Т. 49. - С. 72-106. - 341 с.

.Молчанова Л.А. Введение в Maple. Учебно-методическое пособие. - Владивосток: Изд-во Дальневост. Ун-та, 2006. - 36 С.

.Ю. В. Нестеренко. Глава 4.7. Как раскладывают составные числа на множители // Введение в криптографию / Под ред. В. В. Ященко. - Питер, 2001. - 288 с.

11.<#"justify">Приложение

> restart;

> p:=nextprime(476523189475631579423453); (23 знака)

q:=prevprime(957532186478621546879541); (23 знака)

> n:=p*q;(48 знаков)

> time(ifactor(n));

> time(ifactor(n,squifof));

> time(ifactor(n,pollard)); (остановлено на 308 тысяче секунд ожидания)

Warning, computation interrupted

> time(ifactor(n,lenstra));

> restart;

> p:=nextprime(476523189475631579); (17 знаков):=prevprime(957532186478621546879548756); (26 знака)

> n:=p*q;(45 знаков)

> time(ifactor(n));

> time(ifactor(n,squifof));

> time(ifactor(n,lenstra));

>

>

> restart;

> p:=nextprime(4765231894756315791);(19 знаков):=prevprime(9575321869491284011);(19 знаков):=nextprime(1112154682);(10 знаков)

> n:=p*q*t;(52 знака)

> time(ifactor(n));

> time(ifactor(n,squifof));

> time(ifactor(n,lenstra));

> restart;:=nextprime(320);t:=190;

> n:=k*(2^t)+1;(60 знаков)

> time(ifactor(n));

> k:=nextprime(320);t:=160;:=k*(2^t)+1; (52 знака)

> time(ifactor(n));

> k:=nextprime(320);t:=150;:=k*(2^t)+1;(48 знаков)

> time(ifactor(n));

> k:=nextprime(320);t:=9290;:=k*(2^t)+1;

> time(ifactor(n,squifof));

> k:=nextprime(3);t:=1221;:=t!;(ifactor(n,lenstra));

> p:=nextprime(4761523466525157654535)::=nextprime(1182212457245723424513)::=p*q;

> time(ifactor(n,lenstra));

Содержание Введение Глава 1. Алгоритмы факторизации натуральных чисел .1 Факторизация натурального числа .2 Перебор делителей .3 Метод фактор

Больше работ по теме: