Алгоритм вычисления точек эллиптической кривой

Пусть задано уравнение эллиптической кривой y2 = x3 + ax + b mod p.

Для каждого значения x, 0 £ x £ p – 1

1. Вычисляем A = x3 + ax + b mod p

2. Решаем сравнение y2 = A mod p

Если сравнение имеет решение – квадратичный вычет по mod p – , то имеются два значения y (кроме случая y = 0 ) – y1, y2 : yi = A mod p. В этом случае точки (x, y1) и (x, y2) принадлежат эллиптической кривой.

 

Пример сложения точек эллиптической кривой y2 = x3 + x + 1 mod 5.

 

Пусть P1 = (0,1), P2 = (4,2), x1 = 0, y1 = 1, x2 =4, y2 = 2 .

 

а) P1 + P2 = ( x3, y3 ) .

Так как P1 ¹ P2 , то , l = (2-1)/(4-0) = ¼ mod 5 = 4.

x3 = ( l2 – x1 – x2 ) mod p = 16 – 0 – 4 = 12 mod 5 = 2.

y3 = ( l ( x1 – x3 ) – y1 ) mod p = 4 (0 – 2) – 1 = – 9 mod 5 = 1.

Таким образом, (0,1) + (4,2) = (2,1).

 

b) 2 P1 = ( x3, y3 )

Так как P1 = P2 , то , l = (3*0 + 1)/(2*1) = 1/2 mod 5 = 3.

x3 = ( l2 – x1 – x2 ) mod p = 9 – 0 – 0 = 9 mod 5 = 4.

y3 = ( l ( x1 – x3 ) – y1 ) mod p = 3 (0 – 4) – 1 = – 13 mod 5 = 2.

Таким образом, 2*(0,1) = (4,2).

 

c) Аналогичным образом можно вычислить

3 P1 = 2 P1 + P1 = (4,2) + (0,1) = (2,1)

4 P1 = 3 P1 + P1 = (2,1) + (0,1) = (3,4)

5 P1 = 4 P1 + P1 = (3,4) + (0,1) = (3,1)

6 P1 = 5 P1 + P1 = (3,1) + (0,1) = (2,4)

7 P1 = 6 P1 + P1 = (2,4) + (0,1) = (4,3)

8 P1 = 7 P1 + P1 = (4,3) + (0,1) = (0,4)

9 P1 = 8 P1 + P1 = (0,4) + (0,1) = O

 

Определение. Точка P Î Ep(a,b) называется базовой точкой группы точек эллиптической кривой Ep(a,b), если любая точка Q Î Ep(a,b) может быть представлена в виде Q = k P , где k = 1, 2,…, #Ep(a,b) .

 

Если порядок группы #Ep(a,b) = n , то для базовой точки P имеет место

n P = O .

 

Точка P = (0,1) является базовой для группы точек эллиптической кривой

y2 = x3 + x + 1 mod 5 .

 

Утверждение (теорема Хассе). Значение порядка группы имеет верхнюю и нижнюю границы:

 

Пример. Пусть Q = (2,4) – точка эллиптической кривой y2 = x3 + x + 1 mod 5.

Тогда 2 Q = (2,1), 3 Q = O.

Точка Q = (2,4) порождает циклическую подгруппу порядка 3: (2,4), (2,1), O.

 

Определение. Порядком точки Q эллиптической кривой называется наименьшее число k, т.ч. k Q = O .

 

Точка Q = (2,4), принадлежащая группе точек эллиптической кривой y2 = x3 + x + 1 mod 5, имеет порядок, равный 3.