Эллиптические группы

Эллиптическая группа по модулю p определяется следующим образом. Выбираются два неотрицательных числа a и b, которые меньше p и удовлетворяют условию

4a3 + 27b2 (mod p) ¹ 0 (кривая не аномальная и не суперсингулярная).

Тогда Ep(a, b) обозначает эллиптическую группу по модулю p, элементами которой (x, y) являются пары неотрицательных целых чисел, которые меньше p и удовлетворяют условию

y2x3 + ax + b (mod p)

вместе с точкой в бесконечности O.

Пример.

p = 23. Рассмотрим эллиптическую кривую y2 = x3 + x + 1. В этом случае a = b = 1 и мы имеем 4 ´ 13 + 27 ´ 12 (mod 23) = 8 ¹ 0, что удовлетворяет условиям эллиптической группы по модулю 23.

Для эллиптической группы рассматриваются только целые значения от (0, 0) до (p, p) в квадранте неотрицательных чисел, удовлетворяющих уравнению по модулю p.

В общем случае список таких точек (см. табл.) составляется по следующим правилам.

1. Для каждого такого значения x, что , вычисляется x3 + ax + b (mod p).

2. Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю p (вычисляется символ Лежандра). Если нет, то в Ep(a, b) нет точек с этим значением x. Если же корень существует, имеется два значения y, соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным таким значением оказывается y = 0). Эти значения (x, y) и будут точками Ep(a, b).

Таблица 15. Точки на эллиптической кривой E23(1, 1)

(0, 1) (1, 7) (3, 10) (4, 0) (5, 4) (6, 4) (7, 11)
(0, 22) (1, 16) (3, 13) O (5, 19) (6, 19) (7, 12)
(9, 7) (11, 3) (12, 4) (13, 7) (17, 3) (18, 3) (19, 5)
(9, 16) (11, 20) (12, 19) (13, 16) (17, 20) (18, 20) (19, 18)

 

Пример. Сложение и удвоение точек данной группы. P = (3, 10), Q = (9, 7).

Сложение:

 

Удвоение:

 

Умножение определяется как повторное применение операции сложения

[4]P = P + P + P + P.