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

                                                                        84

[60] и «Алгоритмические основы эллиптической криптографии» [61]. На
английском языке следует отметить, в первую очередь, 2-е издание книги
Л. Вашингтона «Elliptic Curves Number Theory and Cryptography». [54]
Хороший обзор по алгоритмам использования эллиптических кривых в
криптографии можно найти в [16].
      Начнем наше изложение с определения эллиптической кривой над
конечным полем.


3.1. Определение эллиптической кривой

      Определение.     Пусть Fq , q = pk , конечное поле характеристики
p ≥ 2. Эллиптической кривой над полем Fq называется множество точек
(x, y) ∈ Fq ⊕ Fq , удовлетворяющих уравнению Вейерштрассе

     y 2 + ay + b = x3 + cx2 + dx + e (mod q).                       (3.57)

      Кроме того, к множеству точек ЭК добавляется специальная точка,
обозначаемая через ∞ и называемая точкой в бесконечности.
      Если характеристика поля p ≥ 3 (а именно этот случай для нас
наиболее интересен), уравнение (3.57) может быть преобразовано путем
замены переменных в уравнение

             y 2 = x3 + ax + b (mod q),                              (3.58)

где a, b ∈ Fq . Дополнительным требованием на параметры a и b является
условие 4a3 + 27b2 6= 0, в силу которого дискриминант полинома x3 + ax + b
не равен 0, и полином не имеет кратных корней.
      Поскольку все операции в уравнении ЭК выполняются по модулю
числа q , знак равенства в уравнении (3.58) следовало бы заменить знаком
эквивалентности ≡, однако, следуя традициям записи уравнения ЭК, мы
используем знак =.
      На множестве точек E эллиптической кривой можно определить
групповую операцию сложения +, с помощью которой это множество
становится аддитивной абелевой группой с точкой ∞ в качестве нуля.