Бинарный алгоритм вычисления НОД

Бинарный алгоритм Евклида — метод нахождения наибольшегообщего делителя двух целых чисел. Данный алгоритм быстрее обычногоалгоритма Евклида, т.к. вместо медленных операций деления и умноженияиспользуются сдвиги. Возможно алгоритм был известен еще в Китае 1-говека, но опубликован был лишь в 1967 году израильским физиком ипрограммистом Джозефом Стайном. Он основан на использовании следующихсвойств НОД:

  • НОД(2m, 2n) = 2 НОД(m, n),
  • НОД(2m, 2n+1) = НОД(m, 2n+1),
  • НОД(-m, n) = НОД(m, n)

Алгоритм



  1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
  2. НОД(1, n) = 1; НОД(m, 1) = 1;
  3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
  4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
  5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
  6. Если m, n нечётные и n \textgreater m, то НОД(m, n) = НОД(m, (n-m)/2) = НОД((n-m)/2, n);
  7. Если m, n нечётные и n \textless m, то НОД(m, n) = НОД((m-n)/2, n);

 Так как алгоритм является хвостовой рекурсией, то рекурсию можнозаменить итерацией.
 Существует также бинарная версия обобщенного алгоритма Евклида,описанная в книге Д. Кнута, а так же в книге Василенко О.Н.``Теоретико-числовые методы в криптографии'', с. 300.