ВУЗ:
Составители:
ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
В последние два десятилетия все большее применение в криптографии находит од-
на из областей теории чисел и алгебраической геометрии – теория эллиптических кривых
над конечными полями. Основная причина этого состоит в том, что эллиптические кривые
над конечными полями доставляют неисчерпаемый источник конечных абелевых групп,
которые (даже если они велики) удобны для вычислений и обладают богатой структурой.
Во многих отношениях эллиптические кривые – естественный аналог мультипликативных
групп полей, но более удобный, так как существует бóльшая свобода в выборе эллиптиче-
ской кривой, чем в выборе конечного поля.
Начнем с изложения основных определений и свойств эллиптических кривых. Мы
ограничимся минимальным числом основных фактов, необходимых для понимания при-
ложений к криптографии, уделяя больше внимания примерам и конкретным описаниям и
меньше заботясь о доказательствах и общности. Более систематическое изложение этих
вопросов можно найти в литературе (см. список).
§ 1. Основные факты
В этом параграфе мы предполагаем, что K – поле: либо поле R вещественных чи-
сел, либо поле Q рациональных чисел, либо поле C комплексных чисел, либо поле
q
E из
r
pq = элементов. Напомним, что характеристикой поля K называется такое натуральное
число Kp char= , что 01 =⋅p , где 1 и 0 – единичный и нулевой элементы K соответст-
венно.
Определение.
Пусть K – поле характеристики, отличной от 2 и 3, и baxx
3
++ (где
Kba ∈,) – кубический многочлен без кратных корней. Эллиптическая кривая над K – это
множество точек
(
)
yx, (где
Kyx
∈
,
), удовлетворявших уравнению
,
32
baxxy ++= (1)
вместе с единственным элементом, обозначаемым O и называемым «точка в бесконечно-
сти» (о ней подробнее будет сказано ниже).
Если K – поле характеристики 2, то эллиптическая кривая над K – это множество
точек, удовлетворяющих уравнению либо типа
,baxxcyy
32
++=+ (2а)
либо типа
baxxxyy
232
++=+ (2б)
(здесь кубические многочлены в правых частях могут иметь кратные корни), вместе с
«точкой в бесконечности» О.
Если К – поле характеристики 3, то эллиптическая кривая над К – это множество
точек, удовлетворяющих уравнению
cbxaxxy
232
+++= (3)
(где кубический многочлен справа не имеет кратных корней), вместе с «точкой в беско-
нечности» О.
Замечания.
1. Имеется общая форма уравнения эллиптической кривой, которая применима для
поля любой характеристики:
64
2
2
2
31
2
axaxaxyaxyay +++=++ : в случае, когда
2char
≠K , ее можно привести к виду cbxaxxy
232
+++= (или к виду cbxxy
32
++= ,
если 3char
>K ). В случае, когда поле К имеет характеристику 2, это уравнение преобра-
зуется либо к виду (2а), либо к виду (2б).
2. Если F(x, у) = 0 – неявное уравнение, выражающее у как функцию х в (1) (или в
(2), (3)), т. е.
