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

Спаривание Вейля-Тейта                                                 122

Определение 6.3. Отображение (спаривание) Тейта – это билинейное
отображение

 τn : E[n] × E/E[n] → F∗qk × F∗qk \ µn ,                             (6.90)

где µn –подгруппа по умножению корней n–й степени из 1 поля Fqk ,
задаваемое следующей формулой:
                         fP (Q + R)
           τn (P, Q) =              ,                                (6.91)
                           fP (R)
где R ̸∈ {P, −Q, P − Q, ∞}.

      Одним из важных отличий отображение Тейта от преобразования
Вейля является то, что оно не вырождено (не равно 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). Обозначим эту функцию через τ ∗ :

    τ ∗ (P, Q) = τ (P, Q)(q       −1)/n
                              k
                                          .                          (6.92)


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

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