Алгоритмы нахождения НОД и мультипликативного обратного по модулю

Алгоритм Евклида.

Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель.

A1. [ v = 0?] Если v = 0, то выполнение алгоритма заканчивается, а в качестве результата возвращается число u.

A2. [Взять u mod v. ] Присвоить r u mod v, u v, v r и вернуться к шагу A1. (В результате выполняемых на этом шаге операций значение v уменьшается, значение НОД(u, v) остается неизменным.)

Бинарный алгоритм НОД.

Алгоритм B. (Бинарный алгоритм нахождения наибольшего общего делителя). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель. (Использует знаковое представление чисел).

B1. [Найти степень 2.] Присвоить k 0, затем повторно присваивать kk + 1, u u / 2, v v / 2 нуль или более раз до тех пор, пока одно или оба числа u и v станут нечетными.

B2. [Начальная установка.] (Исходные значения чисел u и v уже разделены на 2 ^k, и по крайней мере одно из текущих значений нечетно.) Если нечетно u, то присвоить t - v и перейти к шагу B4. В противном случае присвоить tu.

B3. [Уменьшить t наполовину.] (Здесь t четно и не нуль.) Присвоить tt / 2.

B4. [ t четно?] Если t четно, то вернуться к шагу B3.

В5. [Установить max(u, v) заново.] Если t > 0, то присвоить u t, в противном случае присвоить v - t. (Большее из чисел u и v заменяется на | t | за исключением, возможно, первого выполнения этого шага.)

B6. [Вычесть.] Присвоить t u – v. Если t ¹ 0, то вернуться к шагу B3. В противном случае алгоритм останавливает выполнение, а на выходе будет u · 2 ^k.

Рис.33. Бинарный алгоритм НОД.

Расширенный алгоритм Евклида.

Алгоритм X. (Обобщенный алгоритм Евклида). Для заданных целых чисел u и v этот алгоритм определяет вектор (u ₁, u ₂, u ₃), такой, что uu ₁ + vu ₂ = u ₃ = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v ₁, v ₂, v ₃), (t ₁, t ₂, t ₃); действия производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

ut ₁ + vt ₂ = t ₃ uu ₁ + vu ₂ = u ₃ uv ₁ + vv ₂ = v ₃.

X1. [Начальная установка.] Присвоить (u ₁, u ₂, u ₃) (1, 0, u), (v ₁, v ₂, v ₃) (0, 1, v).

X2. [v3 = 0?] Если v3 = 0, то выполнение алгоритма заканчивается.

X3. [Разделить и вычесть.] Присвоить , затем присвоить

(t ₁, t ₂, t ₃) (u ₁, u ₂, u ₃) – (v ₁, v ₂, v ₃) · q,

(u ₁, u ₂, u ₃) (v ₁, v ₂, v ₃),

(v ₁, v ₂, v ₃) (t ₁, t ₂, t ₃).

Возвратиться к шагу X2.

Расширенный бинарный алгоритм НОД.

Алгоритм Y. Модификация алгоритма X с использованием принципов алгоритма B. Для заданных целых чисел u и v этот алгоритм определяет вектор (u ₁, u ₂, u ₃), такой, что uu ₁ + vu ₂ = u ₃ = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v ₁, v ₂, v ₃), (t ₁, t ₂, t ₃); в течение всего процесса вычисления так же, как и в X выполняются соотношения

ut ₁ + vt ₂ = t ₃ uu ₁ + vu ₂ = u ₃ uv ₁ + vv ₂ = v ₃.

(Использует знаковое представление чисел).

Y1. [Найти степень 2.] То же, что в шаге B1.

Y2. [Начальная установка.] Присвоить (u ₁, u ₂, u ₃) (1, 0, u), (v ₁, v ₂, v ₃) (v, 1 – u, v). Если число u нечетно, присвоить (t ₁, t ₂, t ₃) (0, –1, – v) и прейти к шагу Y4. В противном случае присвоить (t ₁, t ₂, t ₃) (1, 0, u).

Y3. [Выполнить половинное деление t ₃.] Если t ₁ и t ₂ четны, присвоить (t ₁, t ₂, t ₃) (t ₁, t ₂, t ₃)/2; иначе присвоить (t ₁, t ₂, t ₃) (t ₁ + v, t ₂ – u, t ₃)/2. (В последнем случае t1 + v и t2 – u будут оба четными.)

Y4. [ t ₃ четно?] Если t ₃ четно, вернуться к шагу Y3.

Y5. [Переустановить max(u ₃ v ₃).] Если t ₃ положительно, присвоить (u ₁, u ₂, u ₃) (t ₁, t ₂, t ₃); иначе присвоить (v ₁, v ₂, v ₃) (v – t ₁, – u – t ₂, – t ₃).

Y6. [Вычесть.] Присвоить (t ₁, t ₂, t ₃) (u ₁, u ₂, u ₃) – (v ₁, v ₂, v ₃). Затем, если t ₁ £ 0, присвоить (t ₁, t ₂) (t ₁+ v –, t ₂ – u). Если t3 ¹ 0, вернуться к шагу Y3. В противном случае закончить выполнение алгоритма с результатом, равным (u ₁, u ₂, u ₃ · 2 ^k).