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

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

простые числа и их степени пока не получим

    kP0 = ∞ (mod p),                                                 (5.56)

где p–один из делителей n.

      Замечание 1. Поскольку, ни один из делителей n нам заранее не
известен, то условие выполнения (5.56) невозможно проверить, поэтому
признаком успешного завершения работы алгоритма является выполнение
условия Н.О.Д.(n, C) = d > 1 при очередном вычислении коэффициента λ в
операции удвоения или сложения точек при вычислении очередного кратного
C точки P0 .

      Замечание 2. Работа алгоритма состоит из двух стадий, называемых
этапом 1 и этапом 2 (stage-one and stage-two). На первом этапе существенную
роль играет настраиваемый параметр B1 , называемый ограничителем 1 этапа
(stage-one limit). По сути алгоритм Ленстры является полным аналогом
(p − 1)–алгоритма Полларда (см.разд 3.2), где операция возведения в степень
простого числа p заменена операцией домножения точки ЭК на множитель
p. В остальном, организация работы первого и второго этапов может быть
выполнена полностью аналогично работе (p − 1)–метода.

          Описание первой стадии алгоритма

I. Инициализация:
      1. Выберем некоторое значение B1 , например, B1 = 10000.
      2. Выберем случайным образом числа x, y, a ∈ [0, n − 1].
      3. Вычислим b = y 2 −x3 −ax mod n и g = Н.О.Д. (n, 4a3 +27b2 ). Если
g = n, возвращаемся к п.2. Если 1 < g < n, тогда прекратим вычисление –
делитель найден. Иначе, определим кривую E : y 2 = x3 + ax + b и базовую
точку-генератор P0 (x, y).
      4. Присвоим изменяемому параметру P (x, y) начальное значение,
равное P0 .

II. Вычисление: