Прикладная алгебра.

Предисловие.

При создании и эксплуатации современных систем связи, локальных и глобальных систем все большую роль играют проблемы защиты информации. В курсе изучаются дополнительные разделы алгебры и теории чисел и их многочисленные применения в криптографии и алгебраической теории кодирования.

Дисциплина "Прикладная алгебра" отражает важное направление развития современной математики, тесно связанное с дискретными вычислениями.

Введение.

Области применения компьютерных методов защиты информации. Элементы теории чисел и ее приложения. Кольцо целы чисел, НОК, НОД, алгоритм Евклида. Взаимно простые числа, простые числа, факторизация. Сравнения первой степени, функция Эйлера, теорема Ферма. RSA-криптосистема и система цифровой подписи на ее основе. Пороговая схема на основе CRT. Распределение ключей по Диффи-Хелмену.

Конечные алгебраические системы и их роль в цифровой обработке сигналов и в машинных вычислениях.

Алгебраические системы и модели.

Отношения квазипорядка, порядка и эквивалентности. Линейно упорядоченные множества. Решетки. Булевы алгебры. Кольца вычетов. Порядок группы обратимых элементов. Числа Ферма и числа Мерсенена. Символ Лежандра и его свойства. Первообразный элемент по модулю p=2ⁿ+1, q=2p+1. Делители числа a^p±1. Первообразный элемент по модулю p^a. Гиперкомплексние конечные системы. Вычисления по модулю p.

Конечные поля.

Автоморфизмы Фробениуса. Квадраты конечного поля. Формулы для символа Лежандра. Закон взаимности. Символ Якоби. Конечные поля и дискретное преобразование Фурье.

Область целостности.

Факториальные кольца. Область главных идеалов. Евклидовы кольца. Евклидово кольцо как область главных идеалов.

Конечные кольца.

Примарные кольца. Локальность примарного кольца. Разложение конечного кольца в прямую сумму примарных.

Идеалы колец.

Решетка идеалов. Теоремы о гомоморфизмах колец. Нильпотенты и обратимые элементы колец. Максимальные и простые идеалы колец. Факторкольца по максимальным и простым идеалам. Простые и максимальные идеалы в области главных идеалов. Нётеровость области главных идеалов. Свойства отношения делимости в области главных идеалов. Неразложимые и простые элементы в области главных идеалов. Факториальность области главных идеалов.

Кольцо многочленов над кольцом.

Аналог теоремы о делении с остатком. Следствие из теоремы Безу. Число корней многочлена. Евклидовы кольца многочленов над полем. Факториальность кольца многочленов над факториальным кольцом. Примитивные многочлены. Лемма Гаусса. Многочлены от нескольких переменных. Кольцо многочленов как область целостности. Вычисления по модулю идеала, порожденного данным многочленом и циклическая свертка.

Теория групп и ее применение.

Основные понятия теории групп. Нормальные подгруппы и факторгруппы. Гомоморфизмы. Группы преобразований. Основы теории абелевых групп. Структура алгоритмов DES, ГОСТ, IDEA. Структура обратных преобразований, роль инволюций. Групповые коды.

Кольца, поля и их приложения к теории кодирования. Гомоморфизмы и идеалы колец. Сравнения по модулю идеала. Факторкольца. Поля и их характеристики. Алгебраические расширения полей. Строение конечных полей. Многочлены над конечными полями. Полиномиальные коды, линейные рекурренты, регистры сдвига с прямой и обратной связью. Код Хэмминга, БЧХ-коды.

Поле частных области целостности.

Целые элементы поля относительно кольца. Конечнопорождённые модули. Целое замыкание кольца. Алгебраическое замыкание поля. Целозамкнутость целого замыкания кольца. Коэффициенты минимального многочлена целого элемента. Целое замыкание кольца целых чисел в квадратичном поле. Гиперкомплексные системы и их роль в цифровой обработке сигналов.

Задачи цифровой обработки данных.

КИО-фильтры. Авторегрессионые фильтры. Линейные и циклические свертки. Преобразование Фурье. Теорема о циклической свертке.

• Биркгоф Г., Барти Т. Современная прикладная алгебра. Москва, 1976.
• Ван дер Варден Б. Алгебра. Москва, Мир, 1975.
• Вариченко Л. В., Лабунец В. Г., Раков М. А. Алгебраические структуры и цифровая обработка сигналов. Киев, Навукова Думка, 1986.
• Зарисский О., Самюэль П. Коммутативная алгебра. Москва, Иностранная литература, 1963.
• Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, 1988.
• Лидл Р., Нидерайтер Р. Конечные поля. Москва, 1989.
• Salomaa A. Public Key Cryptography, Springer, 1995.
• Muzakami H., Reed I. S., Albert A. Recursive FIR digital filter design using a z-transform on a finitering-IEEE Trans Fcoust Spech and signal Proc. 1983, №5, p. 1155-1166.
• Humprays J. Numbers Groups Codes., 1989.