Всю систему шифрования можно поделить на 2 класса: симметричные и ассиметричные алгоритмы шифрования. Суть симметричных алгоритмов состоит в том, что и шифрующий, и дешифрующий человек должны знать алгоритм шифрования, называемый ключом. Самым известным устройством, работающим симметричным методом, была немецкая шифровальная машина «Энигма». Ассиметричные алгоритмы шифрования являются более надежными[1], так как в них используются 2 ключа - открытый и закрытый. Открытый применяется для шифрования информации, а закрытый - для дешифрования. Таким образом, шанс попадания обоих ключей в руки взломщика очень мал. К тому же, зная закрытый ключ, достаточно просто узнать открытый, но из открытого ключа получить закрытый практически невозможно: для подбора закрытого ключа понадобится очень много времени, так как вариантов может быть столько, что даже самый мощный компьютер будет подбирать их несколько десятков лет.
Одним из самых популярных алгоритмов шифрования на сегодняшний день является алгоритм ассиметричного шифрования RSA. В его основе лежит задача факторизации произведения двух больших чисел, результат которой и определяет криптостойкость алгоритма.
Что же такое факторизация? Факторизация - это разложение числа на простые множители[2]. Существует много алгоритмов, которые решают данную задачу, и поиск новых ведется до сих пор. К сожалению, на данный момент совершенного алгоритма пока нет. Несмотря на то, что существуют алгоритмы, способные правильно разложить число на множители, ни один из них не в силах разложить достаточно большое число за разумное время.
Все алгоритмы факторизации делятся на 2 типа: экспоненциальные и субэкспоненциальные. Сложность экспоненциальных алгоритмов зависит от длины входящих параметров, а для субэкспоненциальных алгоритмов сложность принято обозначать L - нотацией[3]:
Ln(a,c) := 0(e((c+o(i))(logn)a(loglogn)1
где n - число, подлежащее факторизации, а 0 < а < 1 и с — некоторые константы.
К экспоненциальным алгоритмам относятся такие алгоритмы, как:
- перебор возможных делителей;
- метод факторизации Ферма;
- р-алгоритм Полларда;
- Р-1 алгоритм Полларда;
- алгоритм Ленстры;
- алгоритм Полларда-Штрассена;
- метод квадратичных форм Шенкса;
- метод Лемана.
К субэкспоненциальным алгоритмам относятся такие алгоритмы, как:
- алгоритм Диксона;
- факторизация методом непрерывных дробей;
- метод квадратичного решета;
- факторизация с помощью эллиптических кривых.
Вопрос о существовании алгоритма с полиномиальной сложностью, который будет работать на обычном компьютере, до сих пор остается открытым и является достаточно важной проблемой. Но также же существует алгоритм с полиномиальной сложностью, работающий на квантовом компьютере - алгоритм Шора[4].
В данной работе рассматривались как экспоненциальные, так и субэкспоненциальные алгоритмы. Из экспоненциальных алгоритмов были выбраны такие как:
- метод факторизации Ферма;
- р - алгоритм Полларда;
- Р-1 - алгоритм Полларда;
- метод квадратичных форм Шенкса;
- метод Лемана.
Из субэкспоненциальных алгоритмов были отобраны следующие алгоритмы:
- алгоритм Диксона;
- метод непрерывных дробей. Метод Лемера и Пауэрса;
- метод непрерывных дробей. Метод Моррисона и Бриллхарта[5]. Целью данной работы является исследование алгоритмов факторизации
и проведения сравнительного анализа.
По ходу работы были выявлены следующие задачи:
- рассмотрение нескольких алгоритмов факторизации натуральных чисел;
- их реализация на языке программирования Python;
- исследование каждого алгоритма и выявление зависимости времени работы от размера факторизуемого числа;
- сравнение времени работы алгоритмов между собой на разных числовых интервалах;
- подведение итогов.
Глава 1. Алгоритмы факторизации
1.1. Метод Ферма
Метод Ферма разложения на множители делит число п на два положительных целых числа а и Ь, которые необязательно являются простыми, так, чтобы п = ab[ 6].
Метод основан на поиске чисел х и у, таких что (х — у)(х + у) = п.
Основная идея:
Метод сводится к поиску чисел а и Ь, близких друг к другу:
1) находится наименьшее целое число х, которое больше ^п;
2) находится такое число у, что у2 = х2 — п;
3) проверяем, является ли х2 — п полным квадратом. Если да, то находим а = х — у и Ь = х + у. Если нет, то повторяем пункт b) до тех пор, пока х2 — п не будет являться полным квадратом, каждый раз меняя значение х на х + 1.
Для каких чисел работает?
Для всех нечетных чисел.
Сложность: О(п) или 0(еп)[1].
Так как метод факторизации Ферма имеет экспоненциальную оценку, он не эффективен на больших числах. Для ускорения алгоритма можно сначала выполнять пробное деление факторизуемого числа п на простые числа от 2 до некоторой константы. Это позволяет исключить все малые делители числа п от 2 до выбранной константы. И только потом применять метод Ферма.
1.2. р-алгоритм Полларда
р-алгоритм Полларда является вероятностным алгоритмом, который находит делитель составного числа п. Сложность данного алгоритма зависит от величины делителя, а не от величины факторизуемого числа п. Его удобно использовать, когда алгоритмы, зависящие от п, становятся неэффективны^].
Основная идея:
Метод сводится к поиску такого р, что р делится на х1 — х2 без остатка, но в то же время х1 — х2 без остатка на п не делится[9]:
1) выбираем случайно х1;
2) вычисляем х2, используя функцию f(x1) такую, чтобы п не делилось без остатка на х1 — х2;
3) считаем Н.О.Д. для х1 — х2 и п. Если результат не равен 1, то это ответ. А если 1, то повторяем пункт b) и находим xi+1. Повторяем до тех пор, пока результат не станет равен 1.
Факторизацией натурального числа называется его разложение на простые множители. Данная задача имеет очень большую вычислительную сложность. Алгоритм RSA, основанный на трудоемкости задачи факторизации длинных чисел, является одним из самых популярных методов криптографии с открытым ключом[21].
Проведение экспериментов для различных методов, показало, что время выполнения алгоритма напрямую зависит от его типа и вычислительной сложности.
В данной работе были рассмотрены несколько известных алгоритмов для решения задачи факторизации и также было проведено их сравнение.
Была достигнута цель реализовать метод факторизации Ферма, р- алгоритм Полларда, Р-1 алгоритм Полларда, метод квадратичных форм Шенкса, метод Лемана, алгоритм Диксона, метод непрерывных дробей (метод Лемера и Пауэрса) и метод непрерывных дробей (метод Моррисона и Бриллхарта). На основе полученных результатов был проведен сравнительный анализ данных алгоритмов[22].
У каждого алгоритма можно отметить как плюсы, так и минусы:
- метод факторизации Ферма работает вполне эффективно, только если делители числа N находятся близко к друг другу. В противном случае эффективность данного алгоритма падает до сложности полного перебора;
- р-алгоритм Полларда является вероятностным алгоритмом и эффективность данного алгоритма во многом зависит от исходного полинома. Но не смотря на это он мало затратный по памяти, и к тому же его сложность зависит только от величины делителя р, а не входного числа N. То есть главное достоинство этого алгоритма: он применим в тех случаях, когда остальные алгоритмы, зависящие напрямую от числа N, перестают быть эффективными;
- Р-1 алгоритм Полларда работает достаточно быстро на фоне остальных выбранных экспоненциальных алгоритмов. Он быстро находит небольшой простой делитель р, который является степенно-гладким для выбранной границы. Однако выбор правильной границы является сложным дополнением;
- метод квадратичных форм Шенкса довольно легкий в плане реализации, к тому же число итераций первого и второго циклов алгоритма определяется числом сомножителей факторизуемого числа N;
- метод Лемана так же, как и Р-1 алгоритм Полларда, работает достаточно быстро на фоне остальных выбранных экспоненциальных алгоритмов. Это связано с тем, что он развивает идеи, на которых была основана теорема Ферма;
- алгоритм Диксона имеет субэкспоненциальную сложность, но его эффективность для факторизации чисел в рамках моей работы просматривается недостаточно хорошо;
- метод непрерывных дробей (вариант Лемера и Пауэрса) показал лучшие результаты среди остальных субэкспоненциальных алгоритмов благодаря относительной легкости реализации. Здесь не нужно было вычислять факторную базу и вычислять линейно независимые вектора, как для алгоритма Диксона и второго варианта Моррисона и Бриллхарта метода непрерывных дробей.
В итоге благодаря результатам, полученным в ходе экспериментальных работ, получилось еще раз обосновать
Помощь студентам и аспирантам в выполнении работ от наших партнеров
