2020-01-14
120
Нахождение обратного элемента с помощью расширенного алгоритма Евклида
Пример вычисления выражения x*173 = 151 mod 200
1. Устанавливаем начальные значения:
2. Вычисляем значения по формулам:
Последовательно выполняем вычисление шага 2. В ответ пойдет последний отличный от нуля остаток r:
Далее не считаем, так как процесс остановился – получен нулевой остаток. В ответ идут вычисленные на предыдущем шаге значения r5 = 1 – это НОД, u5 = -32 – это коэффициент перед 200, v5 – коэффициент пред 173.
3. Теперь, имея обратный элемент поля (равный 37), мы умножаем его на 151, и затем берем модуль от значения:
37 * 151 mod 200=187;
4. Данное значение и есть х, в уравнении x*173 = 151 mod 200 проверяем:
187*173 mod 200=32351 mod 200 = 151.
Результаты расчета с использованием разработанного программного средства
Результаты совпадают
Алгоритм формирования конечного поля Галуа GF(p) и подсчет количества точек эллиптической кривой n=#Ep
Возьмем р = 7, а = 2, b = 6.
Рассмотрим кривую:
|
|
|
Проверяем условие:
Итак, данная кривая несингулярна. Рассчитаем координату первой точки:
Координаты первой точки найдены G1[5,1]. Находим следующую точку поля, путем удваивания первой точки
Теперь чтобы найти значение 
преобразуем текущее значение к виду: 2*х = mod 7, после чего применяем алгоритм нахождения обратного элемента с помощью расширенного алгоритма Евклида. В результате получаем 
.
Находим третью точку поля:
Преобразуем, текущее значение к виду: 6*х = 5 mod 7, и также применим алгоритм нахождения обратного элемента Евклида. В результате получим 
.
Таким же образом продолжаем формировать поле, пока не получим деление на 0, и получаем G2[5,4], G3[2,5], G4[1,3], G5[3,5], G6[3,2], G7[1,4], G8[2,2], G9[4,1], G10[5,6]. Таким образом, мы сформировали конечное поле GF(p). Теперь добавляем к полученному количеству точек точку в бесконечности О, и тем самым определяем конечное количество точек, равное 11.
Результаты расчета с использованием разработанного программного средства
Результаты совпадают
