Главная | Обратная связь

Обобщенный алгоритм Евклида

На вход алгоритма подаются два натуральных числа a и b. На выходе алгоритма получается следующая линейная композиция , где при :

Ниже приведен обобщенный алгоритм Евклида в редакции Д.Кнута [7], достаточной для его программной реализации:

Алгоритм X. (Обобщенный алгоритм Евклида).

X1. [Начальная установка.] Присвоить

(u₁, u₂, u₃) (1, 0, a), (v₁, v₂, v₃) (0, 1, b).

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

(s_m, t_m, r_m) (u₁, u₂, u₃)

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

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

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

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

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

При решении задач, содержащихся в данном пособии более удобно пользоваться шаблоном электронной таблицы, построение которого рассмотрено ниже. Диапазон ячеек A1:C1 соответствует начальному значению вектора u. Диапазон ячеек D1:F1 соответствует начальному значению вектора v. В ячейки A2, D2 и G1 вводим формулы согласно рис.3.

Рис. 3. Исходные данные

Распространяем введенные формулы согласно рис.4.

Рис. 4. Распространение формул

 

При работе с шаблоном значение a вводится в ячейку C1, а значение b в ячейку F1 (см рис.5 ).

Рис. 5. Общий вид шаблона

Далее выделяем диапазон A2:G2 и распространяем формулы вниз по строкам до появления в столбце G ошибки деления на 0. Значения s_m, t_m и r_m берутся из последней строки столбцов A, B, C соответственно. В случае отрицательной величины s_m или t_m – к ним прибавляются величины b и a соответственно.

Рис. 6. Работа алгоритма

В данном примере 7^-1 mod 113 = 113 – 16 = 97. Обязательно следить за тем, чтобы значение r_m из последней строки столбца C было равно единице.

Задача 1.2. Осуществить зашифрование и расшифрование символа m₁ на алфавите N при помощи аффинного шифра на ключевой паре k₁, k₂. Проверить правильность расшифрования.

 

Пример решения.

Дано: k1 = 7 k2 = 36 m1 = 24 N = 113	Решение:
Найти: C1, m1’ Проверить: m1’ = m1