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

                                                                     23

просеивания.


1.8. Расширенный алгоритм Евклида
      Расширенный алгоритм Евклида (РАЕ) используется во многих
криптографических и теоретико–числовых алгоритмах. Он состоит из двух
частей. В первой части алгоритма для заданных целых чисел A и B
вычисляется их наибольший общий делитель (greatest common divisor d) d.
Вычисление Н.О.Д. натуральных чисел A и B выполняется по рекуррентной
формуле:

           Н.О.Д.(A, B) = Н.О.Д.(B, A mod B),                      (1.3)

где A mod B означает операцию вычисления остатка при целочисленном
делении A на B . Производится последовательное использование этой
формулы, пока остаток от деления первого операнда на второй не станет
равным 0. Последнее ненулевое значение второго операнда и есть искомый
общий делитель:

       int Euclid(int A, B )
       {
       while (A mod B !=0) {
           int C=A mod B;
           A=B; B=C ; }
       return B ;
       }

      Для решения уравнений вида Ax+By = d, где A, B – заданные числа,
а d – их наибольший общий делитель, используется расширенный алгоритм
Евклида. Первая часть РАЕ в результате которой мы находим Н.О.Д. d,
выполняется также, как описано выше. Значения A, B , а также целую часть
и остаток от деления A на B сохраняются в таблице, содержащей 4 столбца.
      Во второй части работы алгоритма к таблице добавляются два новых
столбца, озаглавленных x и y . Поместим в последнюю строчку столбцов
x и y значения 0 и 1. Затем, считая значения xi+1 yi+1 известными,