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

Глава 1. АРИФМЕТИЧЕСКИЕ АЛГОРИТМЫ ТЕОРИИ ЧИСЕЛ В данной главе рассматриваются арифметические алгоритмы, являющиеся основой для изучения дальнейшего материала посо­ бия; алгебраических структур, вычислений в конечном поле GF(2"), приложений теории чисел и конечных полей, В разделе представ­ лены следующие алгоритмы: вычисления наибольшего общего делителя, проверки чисел на простоту, разложения чисел на со­ множители, модульной арифметики, вычисления функции Эйлера и возведения чисел в большие степени (алгоритм степеней). 1.1. Наибольший общий делитель и наименьшее общее кратное Алгоритм Евклида предназначен для вычисления наибольшего общего делителя двух натуральных чисел. Наибольший оСяций делитель (НОД) натуральных чисел аи Ь- ото наибольшее натуральное число с1, на которое данные числа де­ лятся без остатка; d = Н О Д ( А , Ь). Если Н О Д ( « , Ь)= 1 , т.е. если числа не имеют общих делителей, кроме единицы, то числа а я b являют­ ся взаимно простыми. Наименьшим оСпцим кратным (НОК) нескольких натураль­ ных чисел называется наименьшее натуральное число, которое де­ лится без остатка на каждое из данных чисел. НОК двух чисел а и b можно вычислить через значение Н О Д ( Й , Ь) П О формуле: 5