Вычисление мультипликативно обратных элементов в поле вычетов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Российский экономический университет имени Г.В. Плеханова»

филиал в г. Пятигорске Ставропольского края

Кафедра Информационных технологий и правового регулирования управления

ЛАБОРАТОРНАЯ РАБОТА №1

по дисциплине  Информационная безопасность

на тему Вычисление мультипликативно обратных элементов в поле вычетов. Вариант №5

Дата защиты__________________

Оценка______________________

Пятигорск – 2018

Содержание

1. Постановка и анализ задачи проектирования        3

1.1 Пример для отладки и тестирования        4

1.2 Расширенный алгоритм Евклида        5

1.3 Метод Эйлера        7

2. Руководство пользователя        9

Листинг приложения        12

1. Постановка и анализ задачи проектирования

Согласно заданию, необходимо разработать приложение для  нахождения мультипликативно обратных элементов. Заданный вариант - №5.

Теоретическая часть. Для вычисления обратных элементов в поле вычетов используется расширенный алгоритм Евклида. Известно, что если числа n и х являются взаимно простыми и х < n, то для х существует единственное значение х' — такое, что х'

Экспериментальная часть. Выполняется вычисление мультипликативно обратных элементов для ряда чисел хi, i = 1,2, ... 10, для трех простых модулей р1, р2, рз и трех составных модулей n1, n2 и n3. Вычисления выполняются двумя способами: 1) с использованием расширенного алгоритма Евклида и 2) с использованием формулы Эйлера. Составляется сопоставительная таблица, показывающаяся идентичность результатов вычисления по двум способам.

1.1 Пример для отладки и тестирования

Задача нахождения обратного элемента для заданного числа X по заданному модулю M (инверсия) состоит в нахождении такого числа Y, что

        X * Y ≡ 1 (mod M)

что означает существование такого целого K, что

        X * Y = 1 + K * M

Очевидно, что для существования обратного элемента необходимо и достаточно, чтобы выполнялось равенство

        НОД(X, M) = 1

В программе реализованы два способа нахождения обратного элемента: при помощи расширенного алгоритма Евклида и с использованием формулы Эйлера.

1.2 Расширенный алгоритм Евклида

Рассмотрим работу этих способов на примере вычисления обратного элемента для числа 15 по модулю 73.

Для первого способа выполняем запуск расширенного алгоритма Евклида для чисел 15 и 73.

Устанавливаем коэффициенты в начале работы: X = 0, Y = 1

На первом шаге алгоритма N = 15, M = 73, X = 0, Y = 1.

Производим перевычисление коэффициентов:

Коэффициент X переносится из Y: X = 1

Коэффициент Y вычисляется по формуле Y := X - (M div N) * Y:  Y = 0 - (73 div 15) * 1 = -4

Производим перевычисление самих чисел: