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

Применим алгоритм больших-малых шагов для решения сравнения

x P = O mod p,

которое является аддитивным аналогом дискретного логарифма. Алгоритм позволяет найти порядок точки P .

 

Пусть n – максимальная оценка порядка группы точек эллиптической кривой, полученная по теореме Хассе, P – точка эллиптической кривой.

Вычисляем m := é√nù, где énù - округление с избытком.

  1. Строим таблицу пар ( j , j P ) для j = 1, 2 , m.
  2. Вычисляем t := – m P .
  3. g := O .
  4. Цикл по i от 0 до m – 1

проверяем, является ли g второй компонентой в таблице п.2

если g = j P , то полагаем x = m i + j

g := g + t.

 

 

Пример. Возьмем эллиптическую кривую y2 = x3 + x + 1 mod 5, p = 5. По теореме Хассе максимальная оценка порядка кривой равна n == 5+1+2=10. Отсюда m = 3.

С помощью алгоритма больших-малых шагов найдем порядок точки P = (0,1).

Построим таблицу

j
j P (0,1) (4,2) (2,1)

 

Найдем t := – m P = – 3 (0,1) = – (2,1) = (2, –1) = (2,4).

g := O.

i = 0 g := g + t = O + (2,4) = (2,4).

i = 1 g = g + t = (2,4) + (2,4) = (2,1).

i = 2 j = 3 Þ x = m i + j = 3*2 + 3 = 9.

 

 

На рисунке 3 показан пример эллиптической кривой над полем

,

с параметрами –простое, .Точки кривой определены как все решения уравнения , включая бесконечную точку (для расчетов ее можно принять равной (0,0)). Следовательно, порядок группы точек будет равен 27+1=28.

 

Контрольные вопросы

 

1. Дать определение эллиптической кривой.

2. Как определить точку, обратную данной?

3. Какие параметры эллиптической кривой необходимо знать для ее применения?

4. Что называется порядком группы точек эллиптической кривой?

5. Что называется порядком точки эллиптической кривой?

6. Как определить базовую точку?

7. В каких криптографических алгоритмах применяются эллиптические кривые?

 

 

Рисунок 3. Пример эллиптической кривой над полем GF(23).