Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Раздел VІ
Эллиптические кривые
Пусть F – произвольное поле, . Рассмотрим уравнение , где , при условии (условие равенства нулю является неприемлемым для применения в криптографии). Эллиптической кривой назыв. множество всех пар , (точек на плоскости xOy), удовлетворяющих данному уравнению. К эллиптической кривой относят также точку 0E на бесконечности на оси Oy, называемой нулем эллиптической кривой.
Если , то в качетсве эллиптической кривой рассматривают множество , если же , то берется множество пар, удовлетворяющих условию и ноль.
Эллиптическая кривая обозначается
(Elliptic Curve),
некоторая пара обозначается через P.
! Ниже рассматриваются, если не оговорено, рассматриваются эллиптические кривые над полем характеристики, не равной 2 и 3.
Утверждение 6.1 Точки эллиптической кривой образуют аддитивную абелеву группу с 0E в качестве нуля.
Утверждение 6.2 Свойства пар
Если – некоторая прямая, которая проходит через точки P и Q данной эллиптической кривой, тогда:
Рассмотрим некторую эллиптическую кривую (над полем F, ). Пусть , , , . Через эти две точки проведем прямую . Это дает нам систему уравнений:
откуда определяем
, .
Подставим уравнение прямой в равенство :
,
,
Так как точка удовлетворяет полученному уравнению, то в силу теоремы Виета (сумма корней равна второму коэффициенту) имеем:
,
откуда
.
Так как точка также принадлежит прямой , то
.
Учитывая свойство 4) утв. 6.2, имеем окончательно:
Теперь рассмотрим случай , . Через точку P проведем некоторую прямую . Тогда . Продифференцируем равенство эллиптической кривой:
,
откуда . Тогда снова подставляем уравнение прямой в уравнение эллиптической кривой, откудо по теореме Виета имеем , откуда получаем.
.
Подставляя полученное x3 в уравнение прямой, находим
.
Учитывая свойство 4) утв. 6.2, имеем окончательно:
Рассматриваются кривые . Пусть , .
Основные формулы:
, .
, .
Пусть F – некоторое поле, . Рассмотрим множество трехмерных векторов над F:
.
Введем отношение эквивалентности: . Данное отношение разбивает множество векторов на классы эквивалентности, множество которых назыв. проектальной плоскостью.
Соответсвие между точками эллиптической кривой и элементами проектальной плоскости вводится следующим образом:
, ,
т.е. паре ставится в соответствие некоторый класс эквивалентности.
,
,
т.е. если , то , и тогда единственной проективной точкой будет . Эта точка соответствует нулю эллиптической кривой:
.
Если ,, то , .
,
, , .
Одной из самых сложных задач криптографии является задача определения N, если заданы P и Q, и изветсно, что . Вычисление значения выражения при заданных n и P является более простой задачей – количество шагов оценивается , например:
.
Утверждение 6.3 Пусть Fq – поле, . Тогда эллиптическая кривая над Fq может содержать не более точек.
Введем индикатор вычетов: . Тогда при каждом фиксированном x число решений уравнения относительно y можно выразить числом . Следовательно, количество точек эллиптической кривой определяется выражением . Доказано, что .
ТЕОРЕМА 6.1 (Хоссе) Пусть эллиптическая кривая над полем Fq имеет N точек. Тогда справедливо неравенство:
.
ТЕОРЕМА 6.2 (Нейла) Для любого нечетного t, существует эллиптическая кривая над полем Fq с количеством точек .
Рассматривается поле , его расширение и эллиптическая кривая над Fq. Утверждается, что эту кривую можно представить над расширением.
Пусть N – количество точек эллиптической кривой над Fq, Nr – количество точек эллиптической кривой над расширением . Дзета функцией заданной эллиптической кривой назыв. функция вида
,
где T – аргумент функции, – количество точек эллиптической кривой над расширением .
ТЕОРЕМА 6.3 При дзета-функция имеет вид .
Обозначим через корни числителя. Дискриминант , , , . Тогда т.е. зная t, можно посчитать .