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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 111
Функцию Вейля f
n,P
(Q) можно вычислить с помощью рекурсивного
алгоритма Миллера, основанного на вычислении промежуточных функций
Миллера f
j,P
(Q) для j < n по следующей формуле:
f
1,T
(Q) = 1 для любой т.Q ∈ E(K),
f
i+j,T
(Q) = f
i,T
(Q) · f
j,T
(Q) ·
l
i,j
v
i+j
Q
, (3.85)
где l
i,j
= Ax + By + C – уравнение прямой, проходящей через т.iT и jT ,
v
i+j
= x − x
0
– уравнение вертикальной прямой, проходящей через т. R =
(i + j)T .
Приведем формулы для вычисления коэффициентов 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). (3.86)
2. P 6= Q. Угловой коэффициент λ равен в этом случае
λ = (y
2
− y
1
)/(x
2
− x
1
) ( mod p). (3.87)
В обоих случаях уравнение прямой, проходящей через точку P (x
1
, y
1
)
и имеющей коэффициент наклона λ, имеет вид y −y
1
= λ · (x − x
1
), откуда
получим уравнение l:
l = y −λx + (λx
1
− y
1
). (3.88)
Последними выпишем формулы для вычисления координат суммы точек 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
).
(3.89)
Алгоритм Миллера вычисления функции Вейля f
P,n
Спаривание Вейля-Тейта                                                  111

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

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

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

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

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


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

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

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

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

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


       Алгоритм Миллера вычисления функции Вейля fP,n

Страницы