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

Задачей решения сравнения является нахождение такого це­ лого числа .V, при котором будет выполняться сравнение ах-х mod ni= 1, где а - известное натуральное число, а е {1, 2, ш - 1}; /и -- числовой модуль (натуральное число) для нормирования резуль­ тата; - искомое неизвестное, .v = 1, m- 1 . Сравнение акх mod т = 1 также можно записать в виде: сГ' S .tmod/H или а"' mod т = .v modт . Сравнение а"' =.vmodw имеет единственное решение (един­ ственный обратный элемент а"'), если; - числа а ш т являются взаимно простыми; - числа а п й"' удовлетворяют условию (а • сГ') mod /и = 1; - й""' =1, 1П- \ . В других случаях сравнение не имеет решения. Пример 2.2. Найдем обратный элемент для числа 5 по про­ стому модулю 17. Обратный элемент будет равен 7 (например, ре­ зультат можно получить перебором), гак как 5x7 = 33 mod 17=1. Найдем также обратный элемент для числа 5 по модулю 14. Обратный элемент будет равен 3, так как 5x3 = 15 mod 1 4 s | , а число 2 не имеет обратного элемента, так как числа 14 и 2 не вза­ имно просты. В поле GF{m), где т - простое число, все ненулевые элементы имеют обратные элементы. Основные способы нахождения обратных элементов I. Для упрощения ручного счета обратные элементы для чи­ сел, сравнимых с размерностью машинного слова, в модульной арифметике можно вычислять по следующему итеративному алго­ ритму. Выполняется перебор возможных значений в интервале а"' = 1, 1П-\ до тех пор, пока не будет найдено такое а~\ при кото­ ром будет выполняться условие (а • сГ') mod т = 1. 44