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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 87
удаленной точки ∞ будет соответствовать класс (0, 1, 0) проективной
плоскости. Если P = (X, Y, Z) 6= ∞, тогда сопоставляя точке P точку
P
0
= (x, y), x = X/Z, y = Y/Z , получим взаимно-однозначное соответствие
между точками между точками исходной ЭК и классами проективной ЭК.
Для получения формул сложения и удвоения точек ЭК в проективных
координатах заметим, что коэффициент λ входит в формулы (3.58)
во второй и третьей степени и содержит знаменатель 2y
1
, поэтому,
чтобы в результате знаменатель сократился полностью, надо домножить
полученные координаты новой точки (X
0
, Y
0
, Z
0
) на коэффициент 8y
3
1
.
После соответствующих преобразований, получим формулы для вычисления
операции удвоения точек в проективных координатах, не использующую
вычисление обратного элемента:
X
3
= 2Y
1
Z
1
((3X
2
1
+ aZ
2
1
)
2
− 8X
1
Y
2
1
Z
1
)(modp)
Y
3
= 4Y
2
1
Z
1
(3X
1
(3X
2
1
+ aZ
2
1
) − 2Y
2
1
Z
1
) − (3X
2
1
+ aZ
2
1
)
3
(modp)
Z
3
= 8Y
3
1
Z
3
1
(modp)
(3.61)
При сложении двух точек примем Z
3
= Z
1
Z
2
(X
1
X
2
−X
1
Z
2
)
3
(modp), откуда
две другие координаты будут находиться по формулам:
X
3
= (X
2
Z
1
− X
1
Z
2
)[Z
1
Z
2
(Y
2
Z
1
− Y
1
Z
2
)
2
− (X
2
Z
1
+ X
1
Z
2
)·
(X
2
Z
1
− X
1
Z
2
)
2
](modp)
Y
3
= (X
2
Z
1
− X
1
Z
2
)
2
[Y
2
Z
1
(Y
2
Z
1
+ 2Y
1
Z
2
) − Y
1
Z
2
(X
1
Z
2
+ 2X
2
Z
1
)]−
−Z
1
Z
2
(Y
2
Z
1
− Y
1
Z
2
)
3
(modp)
(3.62)
3.2. Число точек эллиптической кривой
Одной из трудных проблем, имеющих важное значение для
приложений, является проблема вычисления количества точек на
эллиптической кривой. Известное неравенство Хассе (Hasse) утверждает, что
#E(F
q
) = q + 1 − t, (3.63)
где |t| ≤ 2
√
q .
Глава 3. Эллиптические кривые                                                     87

удаленной точки ∞ будет соответствовать класс (0, 1, 0) проективной
плоскости. Если P = (X, Y, Z) 6= ∞, тогда сопоставляя точке P точку
P 0 = (x, y), x = X/Z, y = Y /Z , получим взаимно-однозначное соответствие
между точками между точками исходной ЭК и классами проективной ЭК.
       Для получения формул сложения и удвоения точек ЭК в проективных
координатах заметим, что коэффициент λ входит в формулы (3.58)
во второй и третьей степени и содержит знаменатель 2y1 , поэтому,
чтобы в результате знаменатель сократился полностью, надо домножить
полученные координаты новой точки (X 0 , Y 0 , Z 0 ) на коэффициент 8y13 .
После соответствующих преобразований, получим формулы для вычисления
операции удвоения точек в проективных координатах, не использующую
вычисление обратного элемента:
  
                    2     2 2         2
   X3 = 2Y1 Z1 ((3X1 + aZ1 ) − 8X1 Y1 Z1 )(modp)
  
  
      Y3 = 4Y12 Z1 (3X1 (3X12 + aZ12 ) − 2Y12 Z1 ) − (3X12 + aZ12 )3 (modp)   (3.61)
   
    Z3 = 8Y 3 Z 3 (modp)
   
            1 1


При сложении двух точек примем Z3 = Z1 Z2 (X1 X2 − X1 Z2 )3 (modp), откуда
две другие координаты будут находиться по формулам:
   
   
   
     X3 = (X2 Z1 − X1 Z2 )[Z1 Z2 (Y2 Z1 − Y1 Z2 )2 − (X2 Z1 + X1 Z2 )·
    (X Z − X Z )2 ](modp)
   
         2   1     1   2
   
   
    Y3 = (X2 Z1 − X1 Z2 )2 [Y2 Z1 (Y2 Z1 + 2Y1 Z2 ) − Y1 Z2 (X1 Z2 + 2X2 Z1 )]−
   
     −Z1 Z2 (Y2 Z1 − Y1 Z2 )3 (modp)
   
                                                                               (3.62)


3.2. Число точек эллиптической кривой
        Одной из трудных проблем, имеющих важное значение для
приложений,       является   проблема     вычисления      количества      точек   на
эллиптической кривой. Известное неравенство Хассе (Hasse) утверждает, что

                   #E(Fq ) = q + 1 − t,                                       (3.63)
           √
где |t| ≤ 2 q .

Страницы