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

Глава 1. Системы шифрования с открытым ключом                              25

        A     B   A mod B [A/B]       x     y
        40    7        5         5     3   -17
        7     5        2         1    -2   3
        5     2        1         2     1   -2
        2     1        0         2     0   1
      Значение y = −17, находящееся в верхней строке, и есть искомое
значение обратного элемента:

                  d = y mod φ(n) = −17 mod 40 = 23

Оценка сложности алгоритма Евклида

     Расширенный       алгоритм      Евклида     используется     во   многих
криптографических методах, поэтому оценка его производительности
играет важную роль в расчетах эффективности криптографических
алгоритмов.
      Основным фактором в оценке РАЕ является число итераций в главном
цикле вычисления новой пары (A; B), или, другими словами, число строчек
в таблице вычисления вычислений. Чтобы оценить это число, заметим, что
на шаге k произвольной итерации возможны два случая:

      Случай 1. B < A/2. На шаге k + 1 новое значение A, равное
предыдущему B , будет меньше, чем A/2.
      Случай 2. B ≥ A/2. Остаток r = A mod B = A − B будет меньше
A/2, и на шаге k + 2 новое значение A станет равным остатку r < A/2.

      В любом случае, после каждой пары итераций первый аргумент A
уменьшается более, чем в 2 раза, значит, общее число итераций не может
быть больше, чем 2 log2 A. Число операций на каждой итерации постоянно
(как при прямом ходе, так и при подъеме при вычислении коэффициентов
уравнения Ax+By = d), поэтому, оценка РАЕ равна O(L), где L = ⌈log2 A⌉–
длина двоичного представления меньшего из чисел.
      Эта     оценка       не   является   завышенной,     т.к.    существует
последовательность чисел Фибоначчи, {Fn }, на парах соседних элементов