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

                                                                                   24

последовательно вычисляем значения xi и yi , i ≥ 0, по формулам:

             xi = yi+1 ,        yi = xi+1 − yi+1 · (A div B)i

      Пример. Решить уравнение 72x + 25y = 1. Помещаем в первую
строчку значения A = 72, B = 25. Вычисляем A mod B – остаток от деления
A на B , и A div B – целую часть от деления A на B . Потом переносим
значения B и A mod B на строчку вниз и на одну клетку влево. Повторяем
вычисления во второй строке. Продолжаем вычисления, пока значение в
столбце A mod B не станет равным 0. Тогда заносим в последнюю строчку
столбцов x и y значения 0 и 1, и ведем вычисление снизу вверх по формулам,
описанным выше.
        A        B   A mod B A div B           x      y
        72      25         22           2      8    -25
        25      22         3            1      -7     8
        22       3         1            7      1      -7
        3        1         0            3      0      1
Ответ: Н.О.Д.(72, 25) = 1 – последнее значение в столбце B . Пара (x, y) =
(8, −25), дающая решение уравнению 72x + 25y = 1, берется из первой
строки таблицы.

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

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

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