Введение в криптографию




Описание задачи


Целочисленная проблема факторизации (IFP): находит p и q, учитывая составное число n, который является произведением двух больших простых чисел p и q.

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

В то время как целочисленная проблема факторизации занимала внимание  известных математиков подобно Фермату и Гауссу  более чем столетия ,только в прошлых 20 годах  был сделан прогресс в разрешении этой проблемы. Имеются две главных причины для этого явления. Сначала, изобретение RSA-системы шифрования в 1978 стимулировало много математиков к изучению этой проблему. И быстродействующие ЭВМ стали доступными для выполнения и испытания сложных алгоритмов. Фермат и Гаусс имели небольшой стимул для изобретения алгоритма разложения на множители решета поля цифр, так как этот алгоритм более громоздкий ,чем испытательное деление с целью разложения на множители целых чисел  вручную.




Содержание  Назад  Вперед