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

Спаривание Вейля-Тейта                                                102

таких, как, например, имя или адрес электронной почты (identity based open
keys) (см. Advances in Elliptic Curve [4]).

Решение проблемы дискретного логарифмирования с помощью
MOV–алгоритма

Описание этого алгоритма можно найти в главе 5 книги Л. Вашингтона [54].
      Пусть заданы эллиптическая кривая EC : y 2 = x3 + ax + b (modpr ),
и точки P , Q ∈ EC порядка n, где n–простое число, причем существует
m такое, что Q = mP . Требуется найти множитель m. Отображение Вейля
будем обозначать через e(X, Y ). Алгоритм вычисления m заключается в
следующем:
      1. Находим случайную точку T ∈ EC(Fqk ).
      2. Находим порядок M точки T .
      3. Находим d =Н.О.Д.(n, M ). Если d = 1, то возвращаемся к п.1.
Иначе, перейдем к следующему пункту. Определим, что в этом случае т.T
имеет порядок n.
      4. Вычислим a = e(P, T ) и с = e(Q, T ).
      5. Вычисляя дискретный логарифм в поле Fqk , найдем искомый
множитель m.

      Отметим, что можно выполнять этот алгоритм с составным n, тогда
число d может оказаться собственным делителем n и найденный множитель
окажется равным m mod d. В этом случае можно повторять вычисление
с различными точками Ti , вычисляя mi = m mod di до тех пор, пока
произведение различных di не станет больше или равно n. После этого можно
найти m с помощью китайской теоремы об остатках.

      Замечание. Если речь идет о произвольной точке Q, то прежде,
чем вычислять дискретный логарифм, полезно знать, найдется ли такое
m, что Q = mP . Эту проверку можно выполнить, используя следующее
утверждение:

Теорема 3.2. Для произвольной т.Q ∈ EC(Fqk ) найдется число m такое,