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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 91
Приведем также формулы для утроения точки, которая может
оказаться полезной для вычисления кратных kP для специальных значений
k , например, для k = 3
t
, t ∈ Z .
P
3
= 3 × P
1
(X
1
, Y
,
Z
1
), и стоимость операции = 10M+6S.
A = 3X
1
+ aZ
4
, B = 8Y
4
1
, C = 12X
1
Y
2
1
− A
2
, D = BC
X
3
= 8Y
2
1
(B − D) + X
2
1
C
2
,
Y
3
= Y
1
[4(D − B)(2B − D) − C
3
],
Z
3
= Z
1
C.
(5.53)
5.4. Число точек эллиптической кривой
Одной из трудных проблем, имеющих важное значение для
приложений, является проблема вычисления количества точек на
эллиптической кривой. Известное неравенство Хассе (Hasse) утверждает, что
#E(F
q
) = q + 1 − t, (5.54)
где |t| ≤ 2
√
q .
Если выполнено условие p |t, то кривая называется суперсингулярной
(supersingular), иначе кривая называется обыкновенной (ordinary). Отметим,
что условие p |t при p ≥ 5 эквивалентно условию t = 0.
Неравенство Хассе вытекает из уравнения
#E(F
q
) = p
k
+ 1 −
∑
x∈F
p
k
χ(x
3
+ ax + b), (5.55)
где χ(z) – квадратичный характер в поле F
q
(иными словами, χ(z) = 1, −1, 0
в зависимости от того, является z квадратичным вычетом, квадратичным
невычетом или равен 0). Напомним, что квадратичные вычеты можно
вычислять с помощью символа Лежандра (см. раздел 2.12). Однако
практически формула (5.55) не применима, поскольку выполнение расчетов
с ее использованием занимает слишком много времени.
Из неравенства Хассе вытекает, что число точек на эллиптической
кривой отличается от мощности поля q = p
n
самое большее на величину
t меньшего порядка O(q
1/2
). Однако вычисления в абелевой группе точек
Глава 3. Эллиптические кривые                                               91

      Приведем также формулы для утроения точки, которая может
оказаться полезной для вычисления кратных kP для специальных значений
k , например, для k = 3t , t ∈ Z .
       P3 = 3 × P1 (X1 , Y, Z1 ), и стоимость операции = 10M+6S.
   
   
    A = 3X1 + aZ 4 , B = 8Y14 , C = 12X1 Y12 − A2 , D = BC
   
   
    X = 8Y 2 (B − D) + X 2 C 2 ,
       3      1           1
                                                                        (5.53)
   
    Y3 = Y1 [4(D − B)(2B − D) − C 3 ],
   
   
   
     Z3 = Z1 C.

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

                   #E(Fq ) = q + 1 − t,                                 (5.54)
           √
где |t| ≤ 2 q .
      Если выполнено условие p | t, то кривая называется суперсингулярной
(supersingular), иначе кривая называется обыкновенной (ordinary). Отметим,
что условие p | t при p ≥ 5 эквивалентно условию t = 0.
      Неравенство Хассе вытекает из уравнения
                       ∑
     #E(Fq ) = p + 1 −
                k
                          χ(x3 + ax + b),                               (5.55)
                             x∈Fpk


где χ(z) – квадратичный характер в поле Fq (иными словами, χ(z) = 1, −1, 0
в зависимости от того, является z квадратичным вычетом, квадратичным
невычетом или равен 0). Напомним, что квадратичные вычеты можно
вычислять с помощью символа Лежандра (см. раздел 2.12). Однако
практически формула (5.55) не применима, поскольку выполнение расчетов
с ее использованием занимает слишком много времени.
      Из неравенства Хассе вытекает, что число точек на эллиптической
кривой отличается от мощности поля q = pn самое большее на величину
t меньшего порядка O(q 1/2 ). Однако вычисления в абелевой группе точек

Страницы