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


Купить