Тема: ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМА ФАКТОРИЗАЦИИ ЛЕНСТРЫ С ИСПОЛЬЗОВАНИЕМ К-АРНОГО АЛГОРИТМА НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ

Системы и средства криптографической защиты информации имеют важную роль в современном мире, они используются повсеместно, например в сфере финансовой и коммерческой деятельности. Внимание к ним обусловлено и увеличивающимися общественными потребностями в переводе экономических и государственно-правовых отношений на «электронную основу», и сильно расширившимися возможностями обработки, передачи и хранения информации в вычислительных системах. Применение специальных протоколов по защите информации и криптосистем дает возможность осуществлять многообразные экономические отношения «дистанционно», исключая необходимость личной встречи участников. А также поддерживать при этом должную финансовую и правовую дисциплину. К криптографическим протоколам относят протоколы шифрования, идентификации, электронной цифровой подписи (ЭЦП) и протоколы аутентифицированного распределения ключей. В тоже время совершенствуются методики криптоанализа. Многие алгоритмы шифрования используют сложность разложения больших чисел на простые множители.
В своей работе я проведу подробное исследование метода факторизации Ленстра на основе эллиптических кривых используя при этом к-арный алгоритм нахождения наибольшего общего кратного и реализую алгоритмы на языке Python.

Купить

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

Купить