Неприводимые многочлены в конечном поле K.

В этом разделе мы научимся определять для заданного многочлена с коэффициентами из конечного поля P={0, 1, 2,... q - 1}, является ли этот многочлен неприводимым в поле P. Неприводимые многочлены используются для построения линейных сдвиговых регистров с обратной связью (см. раздел 3.1.6). Наш алгоритм основывается на следующей теореме.

Теорема. Пусть F – конечное поле, состоящее из q элементов. Тогда для любого натурального многочлен является произведением всех неприводимых над полем F многочленов степени k.

Из этой теоремы сразу следует, что для произвольного многочлена является произведением всех линейных сомножителей , является произведением всех квадратичных сомножителей и т.д. Поэтому, если =1 для , то является неприводимым многочленом. Наибольший общий делитель двух многочленов находят с помощью алгоритма Евклида, используя соотношение , где - остаток от деления на .

Упомянутый тест на неприводимость можно заменить более быстрым альтернативным тестом: многочлен над полем F= является неприводимым тогда и только тогда, когда , и для всех простых делителей k степени n.

Пример. Показать неразложимость многочлена над полем F₂={0,1}.

В данном случае, n=3, q=2. Для вычисления поделим столбиком на и найдем остаток: . Остаток равен x. Простым делителям числа n=3 являются только k=1, поэтому остается только проверить, что . Для этого делим первый многочлен на второй и находим остаток . Теперь по алгоритму Евклида .

Упражнение 1. Являются ли неприводимыми над полем F₂={0,1} трехчлены , , , , ?

Упражнение 2. Найдите все неприводимые многочлены третьей степени над полем F₂.

Упражнение 3. Определите периоды линейных сдвиговых регистров с обратной связью, построенных на основе неприводимых трехчленов, найденных в предыдущих упражнениях.

Упражнение 4. Какой степени должен быть многочлен, чтобы длины порождаемой им им последовательности бит хватило для кодирования сообщения длины 1 гб?

Упражнение 5. Написать программу на каком-нибудь языке программирования, проверяющую является ли заданный многочлен неприводимым над конечным полем F.

Лабораторная работа №3.

Название работы. Разработка клиент-серверного приложения в Delphi.

Цель работы: Изучить современные средства создания клиент-серверных приложений в системе Delphi. Научиться практической работе по организации и решению задач информационной безопасности в сети.

Задание на лабораторную работу. 1. Разработать, используя среду программирования Delphi (или любую среду Visual C++) клиент-серверное приложение для двустороннего обмена информацией между компьютерами в сети. Выполнить пробную передачу и прием данных.

2. Выработать секретный ключ по протоколу Диффи-Хелмана.

3. Провести аутентификацию пользователей по «слово-вызов».

Требования к выполнению задания. Клиентское приложение должно содержать форму, на которой содержатся поля для ввода IP-адреса компьютера – сервера, поле для ввода информации, передаваемое на сервер и поле для получения информации, возвращаемой с сервера.

Приложение должен содержать кнопки Старт/Стоп для запуска и остановки сервера, поле для вывода информации, передаваемой с сервера, и поля для вывода информации, передаваемой клиентами.

Приложение также должно содержать генератор ключей для протокола Диффи-Хелмана и вычисления секретного ключа.

При сдаче необходимо установить клиентскую часть на один компьютер, а серверную часть приложения на другой компьютер, и продемонстрировать диалог обмена данными.

Программно-аппаратные средства. Компьютерная лаборатория, состоящая из компьютеров, соединенных в локальную сеть, пакет Delphi 7 (Delphi 2005).

Задание на лабораторную работу

1. Изучить теоретический материал по данной лабораторной работе.
2. Ознакомиться с указаниями по программированию в на языке Pascal в среде Delphi.
3. Разработать программный комплекс, представляющий собой клиент-серверное приложение в среде Delphi, осуществляющее передачу данных между двумя хостами в сети.
4. Выполнить пробное шифрование/расшифровку данных, передаваемых по сети в рамках компьютерного класса. Вставить в отчет полученные данные, описать методику выполнения задания.
5. Ответить на контрольные вопросы в конце задания.

Теоретический материал.

Рассмотрим процедуры создания приложений для обмена сообщениями в сети по протоколам TCP/IP.