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

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

13 · 3 mod 23 = 16. Теперь, x3 = λ2 − x1 − x2 = (162 − 3 − 11) mod 23 = 12, а
y3 = λ(x1 − x3 ) − y1 = (16 − 12 − (−10)) mod 23 = 14.
      Ответ: (3, −10) + (11, 3) = (12, 14).

      Замечание. При выполнении удвоения точки или вычислении суммы
необходимо вычисление обратного элемента в поле Fq . Эта операция
выполняется с помощью обобщенного алгоритма Евклида (см.разд.1.8).

Вычисление кратного kQ заданной точки Q

      Поскольку, арифметика эллиптических кривых не содержит прямых
формул для вычисления кратного kQ для заданной точки Q(x1 , y1 ), то эту
операцию выполняют с использованием операций сложения, вычитания и
удвоения точки. Для этого надо представить число k в двоичной системе
исчисления k = bt bt−1 ... b0 , bi ∈ {0, 1}, потом вычислить все точки 2Q, 4Q,
... , 2t · Q и подсчитать сумму тех точек 2i · Q, для которых bi = 1.
      Пример. Пусть k = 13. В двоичной системе k = 1 1 0 12 , тогда,
13Q = 8Q + 4Q + Q. Эту же точку можно вычислить как 16Q − 2Q − Q.

Преобразование уравнения кривой в проективные координаты

       Нахождение суммы и кратного точек ЭК требует вычисления
обратного элемента в конечном поле. Это трудоемкая операция, требующая
использование обобщенного алгоритма Евклида. Можно однако избавиться
от частого использования этой операции, если рассматривать уравнение
эллиптической кривой в трехмерных проективных координатах. Рассмотрим
новое уравнение кривой

                 Y 2 Z = X 3 + aXZ 2 + Z 3 ,                                (3.60)

которое получено из уравнения (3.58) при переходе к проективным
координатам. В этом случае кривая E(Fq ) рассматривается как множество
классов     эквивалентности      (X, Y, X)     с   отношением     эквивалентности
(X, Y, X)    ∼    (aX, aY, aX). Будем называть такие классы точками и
обозначать их любым представителем                 (X, Y, X)   класса. Бесконечно