Алгоритм НОД Лемера (Glikjnmb UK: Lybyjg)

Алгоритм НОД Лемера — названный в честь Деррика Генри Лемера быстрый алгоритм по поиску НОД, является улучшением более простого, но более медленного алгоритма Евклида. Он в основном используется для больших целых чисел, которые имеют представление в виде строки цифр относительно некоторой выбранной основы системы счисления, скажем, β = 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}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}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, переходите к началу внешнего цикла.

Ссылки

• Капил Хари Параджапе, Алгоритм Лемера