Математические основы защиты информации. Ишмухаметов Ш.Т - 82 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 83
Если точки P
1
и P
2
совпадают, то прямая L является касательной
в т.P
1
и угловой коэффициент прямой L можно найти, дифференциируя
уравнение (5.33) по x. Общие формулы для коэффициента λ получат вид:
λ =
{
y
2
−y
1
x
2
−x
1
, если P
1
̸= P
2
,
3x
2
1
+a
2y
1
если P
1
= P
2
(5.40)
Формулы для координат удвоенной точки можно получить из (6.1),
подставляя x
2
= x
1
, y
2
= y
1
:
{
x
3
= λ
2
− 2x
1
− с
y
3
= λ(x
1
− x
3
) − y
1
= λ(3x
1
− λ
2
+ c) − y
1
(5.41)
где опять для сокращенного уравнения (5.34) значение параметра c равно 0.
Группа точек эллиптической кривой над полем F
q
обозначается
символом EC(F
q
), а ее мощность (количество элементов) символом
#EC(F
q
).
Известно, что группа точек эллиптической кривой либо является
циклической (т.е. найдется точка P ∈ EC такая, что все точки являются
кратными этой точки), либо E(F
q
)
∼
=
Z
n
1
⊕ Z
n
2
, где n
1
|n
2
, и n
1
|q − 1.
Инвариант j определяет кривую с точностью до изоморфизма: любые две
кривые с одинаковым инвариантом являются изоморфными (как абелевы
группы).
Пример. Пусть E(F
q
) - группа точек кривой y
2
= x
3
+x+1 над полем
F
23
. Эта группа является циклической с генератором P (0, 1). Рассмотрим все
кратные kP точки P :
P (0, 1) 2P = (6, −4) 3P = (3, −10) 4P = (−10, −7)
5P = (−5, 3) 6P = (7, 11) 7P = (11, 3) 8P = (5, −4)
9P = (−4, −5) 10P = (12, 4) 11P = (1, −7) 12P = (−6, −3)
13P = (9, −7) 14P = (4, 10) 15P = (9, 7) 16P = (−6, 3)
17P = (1, 7) 18P = (12, −4) 19P = (−4, 5) 20P = (5, 4)
21P = (11, −3) 22P = (7, −11) 23P = (−5, −3) 24P = (10, 7)
25P = (3, 10) 26P = (6, 4) 27P = (0, −1) 28P = (∞)
Глава 3. Эллиптические кривые                                                 83

      Если точки P1 и P2 совпадают, то прямая L является касательной
в т.P1 и угловой коэффициент прямой L можно найти, дифференциируя
уравнение (5.33) по x. Общие формулы для коэффициента λ получат вид:
         {
             y2 −y1
            x2 −x1 , если P1 ̸= P2 ,
     λ=     3x21 +a                                             (5.40)
              2y1   если P1 =  P2



      Формулы для координат удвоенной точки можно получить из (6.1),
подставляя x2 = x1 , y2 = y1 :
       {
          x3 = λ2 − 2x1 − с
                                                                           (5.41)
            y3 = λ(x1 − x3 ) − y1 = λ(3x1 − λ2 + c) − y1

где опять для сокращенного уравнения (5.34) значение параметра c равно 0.

      Группа точек эллиптической кривой над полем Fq обозначается
символом EC(Fq ), а ее мощность (количество элементов) символом
#EC(Fq ).
      Известно, что группа точек эллиптической кривой либо является
циклической (т.е. найдется точка P ∈ EC такая, что все точки являются
кратными этой точки), либо E(Fq ) ∼= Zn1 ⊕ Zn2 , где n1 |n2 , и n1 |q − 1.
Инвариант j определяет кривую с точностью до изоморфизма: любые две
кривые с одинаковым инвариантом являются изоморфными (как абелевы
группы).

      Пример. Пусть E(Fq ) - группа точек кривой y 2 = x3 +x+1 над полем
F23 . Эта группа является циклической с генератором P (0, 1). Рассмотрим все
кратные kP точки P :

     P (0, 1)           2P = (6, −4)     3P = (3, −10)     4P = (−10, −7)
     5P = (−5, 3)       6P = (7, 11)     7P = (11, 3)      8P = (5, −4)
     9P = (−4, −5)      10P = (12, 4)    11P = (1, −7)     12P = (−6, −3)
     13P = (9, −7)      14P = (4, 10)    15P = (9, 7)      16P = (−6, 3)
     17P = (1, 7)       18P = (12, −4) 19P = (−4, 5)       20P = (5, 4)
     21P = (11, −3)     22P = (7, −11) 23P = (−5, −3) 24P = (10, 7)
     25P = (3, 10)      26P = (6, 4)     27P = (0, −1)     28P = (∞)

Страницы