Математические основы защиты информации. Ишмухаметов Ш.Т - 45 стр.

Глава 2. Криптостойкость RSA. Алгоритмы факторизации                           46

3. Криптостойкость                           RSA.             Алгоритмы
    факторизации
         Факторизацией    целого    числа    называется     его   разложение    в
произведение простых сомножителей. Такое разложение, согласно основной
теореме арифметики, всегда существует и является единственным (с
точностью до порядка следования множителей). Известно, что задача
факторизации является вычислительно сложной задачей. Однако никому
пока не удалось получить высоких нижних оценок этого алгоритма.
Известно, что эта задача не является также NP-полной.
        Криптостойкость   RSA      базируется     на   предположении,   что    не
существует быстрых (полиномиальных) алгоритмов факторизации. В
силу отсутствия высоких нижних оценок криптостойкость RSA – только
гипотеза, подобно тезису Черча. Поэтому вопрос о существовании алгоритма
факторизации с полиномиальной сложностью на классическом компьютере
для выполнения факторизации является одной из важных открытых проблем
современной теории чисел. В то же время факторизация с полиномиальной
сложностью возможна на квантовом компьютере с помощью алгоритма
Шора.
        Все методы факторизации в зависимости от их производительности
можно     разбить   на    две      группы:      экспоненциальные    методы     и
субэкспоненциальные методы. Все эти методы достаточно трудоемки,
поэтому требуют значительных вычислительных ресурсов для чисел
большой длины. В этой главе мы дадим описание наиболее известных
алгоритмов факторизации, имеющих экспоненциальную оценку сходимости.
        Среди субэкспоненциальных алгоритмов следует выделить метод
эллиптических кривых Ленстры, являющийся аналогом p − 1-метода
Полларда, метод квадратичного решета Карла Померанса и метод решета
числового поля. Описание первого из них будет дано в главе ”Эллиптические
кривые и их использование в криптографии”.