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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 110
где µ
n
–подгруппа по умножению корней n–й степени из 1 поля F
q
k
,
задаваемое следующей формулой:
τ
n
(T, S) =
f
T
(S + R)
f
T
(R)
, (3.83)
где R 6∈ {T, −S, T − S, ∞}.
Одним из важных отличий отображение Тейта является то, что оно не
вырождено (не равно 1) при P = Q. Это позволяет вычислить множитель m
такой, что Q = mP за одно вычисление. Действительно,
τ(P, Q) = τ(P, mP ) = τ(P, P )
m
= b ( mod q).
Чтобы найти теперь m, достаточно вычислить дискретный логарифм
log
a
b (modq), где a = τ(P, P ), в поле K = F
q
.
Отметим, что значение преобразования Тейта τ(P, Q) определяется
точками P и Q не однозначно, а с точностью до множителя из группы µ
n
.
Чтобы получить уникальное значение, элемент τ(P, Q) возводят в степень
(q
k
− 1)/n). Обозначим эту функцию через τ
un
:
τ
un
(P, Q) = τ(P, Q)
(q
k
−1)/n
. (3.84)
Алгоритм Миллера
Главной проблемой в вычислении преобразований Вейля и Тейта
является нахождение функции f , дивизор которой совпадает с заданным
дивизором D. Пусть т.T ∈ E[n]. В этом разделе будем обозначать функцию
Вейля (3.77) с дивизором n[T ]−n[∞] через f
n,T
, подчеркивая ее зависимость
от порядка n т.T . Определим вспомогательные дивизоры
D
j
= j[S + R] − j[R] −[jS] + [∞],
которые удовлетворяют условиям теоремы (3.3). Обозначим через f
j,T
функцию, дивизор которой равен D
j
. Эти функции называются функциями
Миллера.
Спаривание Вейля-Тейта                                                 110

где µn –подгруппа по умножению корней n–й степени из 1 поля Fqk ,
задаваемое следующей формулой:
                          fT (S + R)
            τn (T, S) =              ,                               (3.83)
                            fT (R)

где R 6∈ {T, −S, T − S, ∞}.

      Одним из важных отличий отображение Тейта является то, что оно не
вырождено (не равно 1) при P = Q. Это позволяет вычислить множитель m
такой, что Q = mP за одно вычисление. Действительно,

τ (P, Q) = τ (P, mP ) = τ (P, P )m = b ( mod q).

Чтобы найти теперь m, достаточно вычислить дискретный логарифм
loga b (modq), где a = τ (P, P ), в поле K = Fq .
      Отметим, что значение преобразования Тейта τ (P, Q) определяется
точками P и Q не однозначно, а с точностью до множителя из группы µn .
Чтобы получить уникальное значение, элемент τ (P, Q) возводят в степень
(q k − 1)/n). Обозначим эту функцию через τun :
                              k
                                  −1)/n
    τun (P, Q) = τ (P, Q)(q               .                          (3.84)

Алгоритм Миллера

       Главной проблемой в вычислении преобразований Вейля и Тейта
является нахождение функции f , дивизор которой совпадает с заданным
дивизором D . Пусть т.T ∈ E[n]. В этом разделе будем обозначать функцию
Вейля (3.77) с дивизором n[T ]−n[∞] через fn,T , подчеркивая ее зависимость
от порядка n т.T . Определим вспомогательные дивизоры

     Dj = j[S + R] − j[R] − [jS] + [∞],

которые удовлетворяют условиям теоремы (3.3). Обозначим через fj,T
функцию, дивизор которой равен Dj . Эти функции называются функциями
Миллера.

Страницы