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

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

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

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

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

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

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

Пусть P ₁ = (0,1), P ₂ = (4,2), x ₁ = 0, y ₁ = 1, x ₂ =4, y ₂ = 2.

а) P ₁ + P ₂ = (x ₃, y ₃).

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

x ₃ = (l ² – x ₁ – x ₂) mod p = 16 – 0 – 4 = 12 mod 5 = 2.

y ₃ = (l (x ₁ – x ₃) – y ₁) mod p = 4 (0 – 2) – 1 = – 9 mod 5 = 1.

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

b) 2 P ₁ = (x ₃, y ₃)

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

x ₃ = (l ² – x ₁ – x ₂) mod p = 9 – 0 – 0 = 9 mod 5 = 4.

y ₃ = (l (x ₁ – x ₃) – y ₁) mod p = 3 (0 – 4) – 1 = – 13 mod 5 = 2.

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

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

3 P ₁ = 2 P ₁ + P ₁ = (4,2) + (0,1) = (2,1)

4 P ₁ = 3 P ₁ + P ₁ = (2,1) + (0,1) = (3,4)

5 P ₁ = 4 P ₁ + P ₁ = (3,4) + (0,1) = (3,1)

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

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

8 P ₁ = 7 P ₁ + P ₁ = (4,3) + (0,1) = (0,4)

9 P ₁ = 8 P ₁ + P ₁ = (0,4) + (0,1) = O

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

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

n P = O.

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

y ² = x ³ + x + 1 mod 5.

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

Пример. Пусть Q = (2,4) – точка эллиптической кривой y ² = x ³ + 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), принадлежащая группе точек эллиптической кривой y ² = x ³ + x + 1 mod 5, имеет порядок, равный 3.