Применение эллиптических кривых в криптографии. Жданов О.Н - 8 стр.

UptoLike

Составители: 

Рис. 2. Геометрическая интерпретация эллиптической кривой
над полем комплексных чисел
Фактически эта аналогия идет значительно дальше, чем может показаться. «Эллип-
тические функции» (которые показывают, как по точке (
х, у)
Е найти то комплексное
число
z, для которого ))(,)'((),( zzyx
= ), как оказывается, имеют свойства, аналогичные
свойствам известной функции Arcsin(
z) (которая показывает, как найти вещественное
число, которое соответствует точке единичной окружности при «наматывании» вещест-
венной прямой на окружность). При рассмотрении эллиптических кривых с точки зрения
теории алгебраических чисел обнаруживается глубокая аналогия между координатами
«точек, делящих эллиптические кривые на
n частей» (т.е. таких точек Р, что nP = О) и точ-
ками, делящими на
n частей единичную окружность (которые соответствуют корням сте-
пени
n из единицы в комплексной плоскости).
Точки конечного порядка.
Порядком n точки Р на эллиптической кривой называется такое наименьшее нату-
ральное число, что
nP = 0; разумеется, такого конечного n может и не существовать, в
этом случае мы будем говорить о точке бесконечного порядка. Часто требуется найти точ-
ки конечного порядка на эллиптической кривой, в особенности, на эллиптических кривых,
определенных над полем рациональных чисел
Q.
Пример 3. Найти порядок точки Р = (2, 3) на 1
32
+= xy .
Решение.
Применяя (5), находим, что 2Р = (0, 1), и вновь, с помощью (5), что 4Р =
2(2
Р) = (0, -1). Поэтому 4Р = -2P и, следовательно, 6P = О. Тем самым порядок Р может
быть равен 2, 3 или 6. Но 2
Р = (0,1)
О, а если бы Р имела порядок 3, то было бы 4Р = Р,
что неверно. Итак,
Р имеет порядок 6.
Эллиптические кривые над полем рациональных чисел.
Если в уравнении (1)
а и bрациональные числа, то естественно рассматривать
рациональные решения (
х, у), т.е. эллиптическую кривую над полем Q рациональных чи-
сел. Теория эллиптических кривых над полем рациональных чисел очень обширна. Было
доказано, что соответствующие абелевы группы являются конечнопорожденными (теоре-
ма Морделла). Это означает, что каждая из таких групп есть сумма конечной «подгруппы
кручения» Tors
E(Q) (точек конечного порядка) и подгруппы, порожденной конечным
числом точек бесконечного порядка: )(Tors)( QEZQE
r
. Число (минимальное) обра-
зующих бесконечной части называется рангом
r; оно равно нулю тогда и только тогда, ко-
гда вся группа конечна. Изучение ранга
r и других свойств группы точек эллиптической
кривой над
Q связано со многими интересными вопросами теории чисел и алгебраической
геометрии. Например, известный с древних времен вопрос «Существует ли прямоуголь-
ный треугольник с рациональными сторонами, площадь которого равна данному целому