Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Замечания. 1. Имеется общая форма уравнения эллиптической кривой, которая применима при любом поле: у + агху + а3у = X + о-2х + а4х + об! в случае, когда char К ф 2, ее можно привести к
2 3 2 *^ 23
виду у = X 4 ах 4- Ьх + с (или к виду у = х 4- Ьх 4- с, если К > 3). В случае, когда поле К имеет характеристику 2, это уравнение преобразуется либо к виду (2а), либо к виду (26).
2. Если F(x,y) = О — неявное уравнение, выражающее у как
2 3
функцию а;в(1) (или в (2), (3)), т. е. F(x, у) = у - х - ах - Ь (или F(x, у) = у2 4 су 4 X3 4 ах 4 Ь, у2 4 ху 4 х3 4 ах 4 Ь, у2 — х3 — ах2 — Ьх — с), то точка (х,у) этой кривой называется неособенной (или гладкой) точкой, если, по крайней мере, одна из частных производных dF/dx, dF/dy в этой точке не равна нулю. (Производные многочленов можно определить обычными формулами над любым полем; см. 5-й абзац в начале главы IL)
Нетрудно показать, что условие отсутствия кратных корней у кубических многочленов в правой части в (1) и (3) эквивалентно требованию, чтобы все точки кривой были неособенными.
Эллиптические кривые над вещественными числами. Перед обсуждением конкретных примеров эллиптических кривых над разными полями мы отметим чрезвычайно важное свойство множества точек эллиптической кривой: они образуют абелеву группу. Чтобы объяснить наглядно, как это получается, мы временно будем полагать, что К = R, т. е. что эллиптическая кривая — обычная плоская кривая (с добавлением еще одной точки О «в бесконечности»).
190
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
Определение. Пусть E — эллиптическая кривая над вещественными числами, и пусть P и Q — две точки на Е. Определим точки —Р и P + Q по следующим правилам.
1. Если P — точка в бесконечности О, то— P = OhPA-Q = Q, т.е. О — тождественный элемент по сложению («нулевой элемент») группы точек. В следующих пунктах предполагается, что ни Р, ни Q не являются точками в бесконечности.
2. Точки P = (х,у) и — P имеют одинаковые ж-координаты, а их у-координаты различаются только знаком, т.е. — (х,у) = (х,—у). Из (1) сразу следует, что (х, —у) — также точка на Е.
3. Если PaQ имеют различные ж-координаты, то прямая / = PQ имеет с E еще в точности одну точку пересечения R (за исключением двух случаев: когда она оказывается касательной в Р, и мы тогда полагаем R = P, или касательной в Q1 и мы тогда полагаем R = Q). Определяем теперь PA-Q как точку —R, т.е. как отражение от оси X третьей точки пересечения. Ееометрическое построение, дающее P + Q, приводится ниже в примере 1.
4. Если Q = —Р (т.е. ж-координата Q та же, что и у Р, а у-координата отличается лишь знаком), то полагаем P -f Q = О (точке в бесконечности; это является следствием правила 1).
5. Остается возможность P = Q. Тогда считаем, что / — касательная к кривой в точке Р. Пусть R — единственная другая точка пересечения / с Е. Полагаем PA-Q = —R (в качестве R берем Р, если касательная прямая в P имеет «двойное касание», т.е. если P есть точка перегиба кривой). V
Пример 1. На рисунке спра ва изображены эллиптическая кри-
2 3
вая у = X — X в плоскости ху и типичный случай сложения точек P и Q. Чтобы найти P + Q, проводим прямую PQ и в качестве P + Q берем точку, симметричную относительно оси X третьей точке, определяемой пересечением прямой PQ и кривой. Если бы P совпадала с Q, т.е. если бы нам нужно было найти 2Р, мы использовали бы касательную к кривой в Р; тогда точка 2Р симметрична третьей точке, в которой эта касательная пересекает кривую.
§ 1. ОСНОВНЫЕ ФАКТЫ
191
Теперь мы покажем, почему существует в точности еще одна точка, где прямая I, проходящая через P и Q, пересекает кривую; заодно мы выведем формулу для координат этой третьей точки и тем самым — для координат P + Q.
Пусть (хг,уі), (2:2,2/2) и (хз,Уз) обозначают координаты соответственно Р, Q и P + Q. Мы хотим выразить х3,у3 через хі,У\,х2,у2.
Предположим, что мы находимся в ситуации п. 3 определения P+Q, и пусть у = ax-\-? есть уравнение прямой, проходящей через P и Q (в этой ситуации она не вертикальна). Тогда а = (у2 ~Уі)/(х2 ~х\) и ? = 2/1 — ах\ ¦ Точка на /, т. е. точка (х, ах + /3), лежит на эллиптиче-
2 3
ской кривой тогда и только тогда, когда (ax + ?) = х + ах + Ь. Таким образом, каждому корню кубического многочлена х3 — (ax + ?)2 + ах + b соответствует точка пересечения. Мы уже знаем, что имеется два корня Xi и х2, так как (xx,axi + ?), (х2,ах2 + ?) — точки Р, Q на кривой. Так как сумма корней нормированного многочлена равна взятому с обратным знаком коэффициенту при второй по старшинству степени многочлена, то в нашем случае третий корень — это х3 = a —Xi-X2. Тем самым получаем выражение для х3, и, следовательно, P + Q — (х3, — (ах3 + ?)) или, в терминах хі,ух,х2,у2,
2
, 2/2-2/1 ,
X3 = - - X1 - X2
X2 - X1
. 2/2 - 2/1 / ч
Уз = -2/1 + -(zi - х3).
X2 - Xi
(4)
Ситуация в п. 5 аналогична, только теперь а — производная dy/dx в Р. Дифференцирование неявной функции, заданной уравнением (1), приводит к формуле а = (За;2 + а)/(2ух), и мы получаем следующие формулы для координат удвоенной точки Р:
