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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 1. Системы шифрования с открытым ключом 26
которых и достигается эта верхняя оценка. Последовательность или ряд
Фибоначчи определяется следующими формулами:
F
0
= 1, F
1
= 1, F
n+2
= F
n
+ F
n+1
, n ≥ 2.
Выпишем начальный интервал этого ряда:
S = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181}.
2.6. Алгоритм быстрого возведения в степень по модулю
Большинство операций в кольце вычетов Z
n
можно выполнять, выполнив
сначала действия с числами, а затем находя остаток от деления результата
на модуль n. Однако с операциями возведения в степень и вычисления
дискретного (модулярного) логарифма, такой порядок является очень
неэффективным. Например, если мы захотим вычислять 2
199
(mod1003),
используя калькулятор, входящий в состав операционной системы Windows,
то результат окажется неверным. В то же время эту же операции несложно
выполнить с помощью алгоритма быстрого возведения в степень по модулю
заданного натурального числа, который мы сейчас опишем.
Предположим, что требуется вычислить z = a
b
mod n.
Рассмотрим следующий алгоритм:
1. Представим b в двоичный системе исчисления: b = (b
0
b
1
... b
k
)
2
,
b
i
∈ {0, 1}. Например, 199 = 11000111
2
,
2. Заполним следующую таблицу
b b
0
b
1
... b
k
a a
0
a
1
... a
k
где a
0
= a, a
i+1
=
{
a
2
i
mod n, если b
i+1
= 0,
a
2
i
· a mod n, если b
i+1
= 1
для i ≥ 0.
Результат появится в последней ячейке второй строки.
Пример. Вычислить 2
199
mod 1003:
Глава 1. Системы шифрования с открытым ключом                                   26

которых и достигается эта верхняя оценка. Последовательность или ряд
Фибоначчи определяется следующими формулами:

      F0 = 1, F1 = 1, Fn+2 = Fn + Fn+1 , n ≥ 2.

Выпишем начальный интервал этого ряда:

S = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181}.


2.6. Алгоритм быстрого возведения в степень по модулю
   Большинство операций в кольце вычетов Z n можно выполнять, выполнив
сначала действия с числами, а затем находя остаток от деления результата
на модуль n. Однако с операциями возведения в степень и вычисления
дискретного (модулярного) логарифма, такой порядок является очень
неэффективным. Например, если мы захотим вычислять 2199 (mod1003),
используя калькулятор, входящий в состав операционной системы Windows,
то результат окажется неверным. В то же время эту же операции несложно
выполнить с помощью алгоритма быстрого возведения в степень по модулю
заданного натурального числа, который мы сейчас опишем.
            Предположим, что требуется вычислить z                   =   ab mod n.
Рассмотрим следующий алгоритм:

      1. Представим b в двоичный системе исчисления: b = (b0 b1 ... bk )2 ,
bi ∈ {0, 1}. Например, 199 = 110001112 ,
      2. Заполним следующую таблицу

       b    b0 b1    ...    bk
        a   a0 a1    ...    ak

                     {
                         a2i mod n, если bi+1 = 0,
где a0 = a, ai+1 =                                      для i ≥ 0.
                         a2i · a mod n, если bi+1 = 1

      Результат появится в последней ячейке второй строки.

Пример. Вычислить 2199 mod 1003:

Страницы