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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Спаривание Вейля-Тейта 124
Алгоритм Миллера вычисления функции Вейля f
P,n
1. Найдем бинарное представление числа n = (n
t
... n
0
)
2
.
2. Определим исходные значения переменной точки Z и функции f равными
P и 1 соответственно.
3. Выполняем цикл по i от i = t − 1 до i = 0:
• Установим
f = f
2
· l
Z,Z
/v
2Z
,
Z = 2Z.
• Если n
i
= 1, тогда выполним операцию сложения P + Z :
f = f
2
· l
P,Z
/v
P +Z
,
Z = P + Z.
4. Определим выходное значение функции Вейля f
P,n
= f .
Пример 1. Дана кривая y
2
= x
3
+ 11 над полем F
31
. Она содержит
25 точек и изоморфна группе Z
5
× Z
5
. Эта группа порождается точками
P = (2; 9) и Q = (3; 10), имеющими порядок n = 5. Степень вложения
k = 1, т.к. p
1
− 1 = 30 делится на n = 5. Вычислим функцию Вейля f
5,P
,
используя алгоритм Миллера:
1. Найдем двоичное представление n = 5 = (101)
2
, t = 2.
2. Положим Z = (2; 9). Выполним вычисления шага 3 алгоритма
Миллера при i = t − 1 = 1.
λ = 3 · 2
2
/(2 · 9) mod 31 = 2/3 mod 31 = 2 · 21 mod 31 = 11.
l = y −λx + (λx
1
− y
1
) = y − 11x + 11 · 2 − 9 = y − 11x + 13.
Z = 2Z = (λ
2
− 2x
1
; −y
1
− λ(x
2
− x
1
)) = (24; 28)
v = x − 24 ≡ x + 7.
f
2,P
= (−11x + y + 13)/(x + 7).
Проверим условие n
i
= 1. Т.к. n
i
= 0, то операция сложения на i–м
шаге не выполняется. Переходим к следующей итерации при i = 0.
Спаривание Вейля-Тейта                                                   124

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

1. Найдем бинарное представление числа n = (nt ... n0 )2 .

2. Определим исходные значения переменной точки Z и функции f равными
P и 1 соответственно.

3. Выполняем цикл по i от i = t − 1 до i = 0:

   • Установим
                   f = f 2 · lZ,Z /v2Z ,
                   Z = 2Z.

   • Если ni = 1, тогда выполним операцию сложения P + Z :

                  f = f 2 · lP,Z /vP +Z ,
                  Z = P + Z.

4. Определим выходное значение функции Вейля fP,n = f .

      Пример 1. Дана кривая y 2 = x3 + 11 над полем F31 . Она содержит
25 точек и изоморфна группе Z5 × Z5 . Эта группа порождается точками
P = (2; 9) и Q = (3; 10), имеющими порядок n = 5. Степень вложения
k = 1, т.к. p1 − 1 = 30 делится на n = 5. Вычислим функцию Вейля f5,P ,
используя алгоритм Миллера:

      1. Найдем двоичное представление n = 5 = (101)2 , t = 2.

      2. Положим Z = (2; 9). Выполним вычисления шага 3 алгоритма
Миллера при i = t − 1 = 1.

       λ = 3 · 22 /(2 · 9) mod 31 = 2/3 mod 31 = 2 · 21 mod 31 = 11.
       l = y − λx + (λx1 − y1 ) = y − 11x + 11 · 2 − 9 = y − 11x + 13.
       Z = 2Z = (λ2 − 2x1 ; −y1 − λ(x2 − x1 )) = (24; 28)
       v = x − 24 ≡ x + 7.
       f2,P = (−11x + y + 13)/(x + 7).
      Проверим условие ni = 1. Т.к. ni = 0, то операция сложения на i–м
шаге не выполняется. Переходим к следующей итерации при i = 0.

Страницы