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

Содержание Введение 3 Глава 1. Арифметические алгоритмы теории чисел 5 1.1. Наибольший общий делитель и наименьшее общее крат- нос 5 1.2. «Решето» Эратосфена 10 1.3. Разложение чисел на два простых сомножителя 16 Алгоритм Бухштаба 16 Алгоритм Ферма 19 1.4. Модульная арифметика 21 1.5. Проверка простоты чисел Мерсенна 24 Тест Люка - Лемера 25 1.6. Функция и теорема Эйлера 28 1.7. Возведение натуральных чисел по модулю в большие степени 32 Глава 2. Алгебраические структуры 38 2.1. Понятия алгебраических структур. Группа, Кольцо. Поле 38 2.2. Вычисление обратных элементов 43 2.3. Вычисление первообразного элемента 49 2.4. Расширения конечных полей - GF{q"). Поле полиномов над полем GF{q) 57 2.5. Вычисление примитивных олементов в поле GF{q'^) 60 131