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

Глава 3. Эллиптические кривые                                                99

факторизации, а, значит, работает быстрее любого метода, упомянутого во
второй главе.
        Если сравнивать его с методом квадратичного решета QS и методом
решета числового поля NFS, то все зависит от размера наименьшего делителя
числа n. Если число n выбрано по методу RSA как произведение двух
простых чисел примерно одинаковой длины, то метод ЕК имеет ту же оценку,
что и метод квадратичного решета, но уступает методу решета числового
поля.
        Однако если    n   имеет размерность, превышающую рекордные
показателя для методов QS и NFS, (напомним, что последнее рекордное
разложение чисел RSA с использованием NFS относится к числу длины 768
бит), то единственная надежда найти делитель n может выполнена только
с помощью метода эллиптических кривых.
        За последние годы получено много новых рекордных разложений
с   использованием    этого   метода   (см.   сайт   http://www.loria.fr/   zim-
merma/records/top50.html). Самые большие делители, содержащие 73
десятичные цифры, чисел 21181 − 1, 21163 − 1 и 21237 − 1 были найдены
в 2010 году коллективом авторов, включающим Д.Босты, А.Ленстры,
Т.Кляйнъюнга и П.Монтгомери. Б.Додсон нашел в 2011 году делитель,
состоящий из 69 десятичных цифр, числа 21822 + 1. Делитель такой же
размерности числа 31443 + 1 нашел в 2010 году С.Вагстафф.

        Классический алгоритм Ленстры 1987 г. завершается в своей
первой стадии. Последующие улучшения этого алгоритма, выполненные
Монтгомери, Брентом и др., позволили решать задачу факторизации n даже
в случае, если порядок l содержит более одного множителя, превышающего
B1 . Описание алгоритма Монтгомери для вычисления кратного точки ЭК
можно найти в книге Болотова и др. [42], а улучшения Монтгомери к методу
Ленстры в статьях [30] и [31]. В следующем параграфе мы рассмотрим
метод Монтгомери по книге Крендела и Померанса "Простые числа:
вычислительная перспектива" [14].