Эллиптическая группа по модулю p определяется следующим образом. Выбираются два неотрицательных числа a и b, которые меньше p и удовлетворяют условию
4a3 + 27b2 (mod p) ¹ 0 (кривая не аномальная и не суперсингулярная).
Тогда Ep(a, b) обозначает эллиптическую группу по модулю p, элементами которой (x, y) являются пары неотрицательных целых чисел, которые меньше p и удовлетворяют условию
y2 ≡ x3 + 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.