Факторизация натуральных чисел

Abstract

Факторизация натуральных чисел – одна из ключевых задач теории чисел, заключающаяся в разложении числа на простые множители. Эта задача имеет важное значение в криптографии, в частности в алгоритме RSA, где безопасность основана на вычислительной сложности факторизации больших чисел. Алгоритм RSA использует пару ключей: открытый для шифрования и закрытый для расшифровки, причем нахождение закрытого ключа по открытому требует факторизации про-изведения двух больших простых чисел. В данной работе рассмотрены три алгоритма факторизации: метод перебора делителей, алгоритм Ферма и ρ-метод Полларда.