Вычисления в конечных полях

Описание алгоритма Ев]01ида: на вход подаются натуральные числа а и Ь\ на выходе: значение h) или ответ о неприме­ нимости сшгоритма. Шаги алгоритма Евклида: 1) ввод натуральных чисел а и />; 2) если параметры а и h не являются натуральными числами, то выход; 3) нахождение среди а н b наибольшего max и наименьшего min чисел (для исключения возможности деления меньшего числа на большее); 4) а) ost - max mod min - нахождение остатка ost от деления чисел max и min; б) max = min; min = osf, в) если (Ш Ф О, то переход к шагу 4) а), иначе к шагу 5); 5) вывод max - значение НОД чисел а и 1г, выход. Вычислительная сложность алгоритма Евклида равна 0(log2(max(a,b))). Пример 1.1. Вычислить НОД для чисел 1234 и 54. Решение. Произведем деления с остатком: 1 2 3 ^ 5 4 x 2 2 ^ 4 6 ; 5 ^ 4 £ Х Д > 8 ; 4 ^ 8 ' 2 J > 6 ; 6 =2 * ' х Т + 0. Представим полученное реп1сние с помощью трассировочной таблицы (табл. 1.1). Таблица 1.1 Шаги в цигсле Условие; остаток #07 Остаток (Л mod В) Л<~1} Z?< — остаток 0 - 4 6= 1234 mod .14 54 46 1 Да; 46 ф 0 8 = 54 mod 46 46 8 2 Да; К # 0 6 = 46 mod 8 8 6 3 Да; 6 Ф 0 2 = 8 mod 6 6 2 4 Да: 1фй 0 = 6 mod 2 2 0 Итог: Нет - НОД = 2 - 7