Interested Article - Алгоритм НОД Лемера

Алгоритм НОД Лемера — названный в честь Деррика Генри Лемера быстрый алгоритм по поиску НОД , является улучшением более простого, но более медленного алгоритма Евклида . Он в основном используется для больших целых чисел, которые имеют представление в виде строки цифр относительно некоторой выбранной основы системы счисления , скажем, β = 1000 или β = 2 ³² .

Алгоритм

Лемер отметил, что большинство частных с каждого шага части деления стандартного алгоритма невелики. (Например, Дональд Кнут заметил, что коэффициенты 1, 2 и 3 составляют 67,7% всех коэффициентов .) Эти небольшие частные могут быть идентифицированы только из нескольких начальных цифр. Таким образом, алгоритм начинается с разделения этих начальных цифр и вычисления последовательности частных, пока это правильно.

Скажем, мы хотим получить НОД из двух целых чисел a и b . Пусть a ≥ b .

Если b содержит только одну цифру (в выбранной системе счисления, скажем, β = 1000 или β = 2 ³² ), используйте какой-то другой метод, такой как алгоритм Евклида, чтобы получить результат.
Если a и b отличаются по длине цифр, выполните деление так, чтобы a и b были равны по длине с длиной, равной m .
Внешний цикл: Итерируйте, пока один из a или b не станет равным нулю:
- Уменьшить m на единицу. Пусть x будет ведущей (самой значимой) цифрой в a , x = a div β ^m и y — начальная цифра в b , y = b div β ^m .
- Инициализируйте 2 на 3 матрицу
$\textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}$ $\textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}$ к расширенной единичной матрице $\textstyle {\begin{bmatrix}1&0&x\\0&1&y\end{bmatrix}},$ $\textstyle {\begin{bmatrix}1&0&x\\0&1&y\end{bmatrix}},$
и выполнить алгоритм Евклида одновременно на парах ( x + A , y + C ) и ( x + B , y + D ),
- Вычислить коэффициенты w ₁ длинных делений ( x + A ) на ( y + C ) и w ₂ ( x + B ) на ( y + D ) соответственно. Также пусть w будет (не вычисленным) частным от текущего длинного деления в цепочке длинных делений алгоритма Евклида.
- - Заменить текущую матрицу
  $\textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}$ $\textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}$
  
  матричным произведением
  
  $\textstyle {\begin{bmatrix}0&1\\1&-w\end{bmatrix}}\cdot {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}={\begin{bmatrix}C&D&y\\A-wC&B-wD&x-wy\end{bmatrix}}$ $\textstyle {\begin{bmatrix}0&1\\1&-w\end{bmatrix}}\cdot {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}={\begin{bmatrix}C&D&y\\A-wC&B-wD&x-wy\end{bmatrix}}$
  
  согласно матричной формулировке расширенного алгоритма Евклида.
  - Если B ≠ 0, перейти к началу внутреннего цикла.
- Если B = 0, мы достигли «тупика»; выполните нормальный шаг алгоритма Евклида с помощью a и b и перезапустите внешний цикл.
- Установите a в aA + bB и b в Ca + Db (снова одновременно). Это применяет шаги евклидова алгоритма, которые были выполнены с начальными цифрами в сжатой форме, к длинным целым числам a и b . Если b ≠ 0, переходите к началу внешнего цикла.