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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 123
которые удовлетворяют условиям теоремы (6.2). Обозначим через f
j,P
функцию, дивизор которой равен D
j
. Эти функции называются функциями
Миллера.
Функцию Вейля f
n,P
(Q) можно вычислить с помощью рекурсивного
алгоритма Миллера, основанного на вычислении промежуточных функций
Миллера f
j,P
(Q) для j < n по следующей формуле:
f
1,P
(Q) = 1 для любой т.Q ∈ E(K),
f
i+j,P
(Q) = f
i,P
(Q) · f
j,P
(Q) ·
l
i,j
v
i+j
Q
, (6.93)
где l
i,j
= Ax + By + C – уравнение прямой, проходящей через т.iP и jP ,
v
i+j
= x − x
0
– уравнение вертикальной прямой, проходящей через т. R =
(i + j)P .
Приведем формулы для вычисления коэффициентов A, B и C прямой
l
P,Q
, проходящей через т.P (x
1
, y
1
) и Q(x
2
, y
2
):
1. P = Q. Угловой коэффициент λ наклона касательной равен
λ = (3x
2
1
+ a)/(2y
1
) ( mod p). (6.94)
2. P ̸= Q. Угловой коэффициент λ равен в этом случае
λ = (y
2
− y
1
)/(x
2
− x
1
) ( mod p). (6.95)
В обоих случаях уравнение прямой, проходящей через точку P (x
1
, y
1
)
и имеющей коэффициент наклона λ, имеет вид y −y
1
= λ ·(x −x
1
), откуда
получим уравнение l:
l = y − λx + (λx
1
− y
1
). (6.96)
Последними выпишем формулы для вычисления координат суммы точек P +
Q = (x
3
, y
3
) (формулы для удвоенной точки можно получить, приравнивая
x
2
= x
1
):
{
x
3
= λ
2
− x
1
− x
2
y
3
= −y
1
+ λ(x
1
− x
3
).
(6.97)
Спаривание Вейля-Тейта                                                  123

которые удовлетворяют условиям теоремы (6.2). Обозначим через fj,P
функцию, дивизор которой равен Dj . Эти функции называются функциями
Миллера.
       Функцию Вейля fn,P (Q) можно вычислить с помощью рекурсивного
алгоритма Миллера, основанного на вычислении промежуточных функций
Миллера fj,P (Q) для j < n по следующей формуле:

             f1,P (Q) = 1 для любой т.Q ∈ E(K),

                                              li,j
        fi+j,P (Q) = fi,P (Q) · fj,P (Q) ·               ,            (6.93)
                                             vi+j    Q
где li,j = Ax + By + C – уравнение прямой, проходящей через т.iP и jP ,
vi+j = x − x0 – уравнение вертикальной прямой, проходящей через т. R =
(i + j)P .
       Приведем формулы для вычисления коэффициентов A, B и C прямой
lP,Q , проходящей через т.P (x1 , y1 ) и Q(x2 , y2 ):

1. P = Q. Угловой коэффициент λ наклона касательной равен

       λ = (3x21 + a)/(2y1 ) ( mod p).                                (6.94)


2. P ̸= Q. Угловой коэффициент λ равен в этом случае

        λ = (y2 − y1 )/(x2 − x1 ) ( mod p).                           (6.95)

       В обоих случаях уравнение прямой, проходящей через точку P (x1 , y1 )
и имеющей коэффициент наклона λ, имеет вид y − y1 = λ · (x − x1 ), откуда
получим уравнение l :

        l = y − λx + (λx1 − y1 ).                                     (6.96)

Последними выпишем формулы для вычисления координат суммы точек P +
Q = (x3 , y3 ) (формулы для удвоенной точки можно получить, приравнивая
x2 = x1 ):
       {
             x3 = λ 2 − x1 − x2
                                                                      (6.97)
             y3 = −y1 + λ(x1 − x3 ).

Страницы