Как найти обратный элемент алгоритм евклида

Пояснительная записка к курсовой работе

по дискретной математике.

Мультипликативно обратные элементы в поле вычетов.

СОДЕРЖАНИЕ

ПРОВЕДЕНИЕ АНАЛИЗА СВОЙСТВ, ХАРАКТЕРИЗУЮЩИХ ЗАДАННУЮ ТЕМУ.. 3

ВЫВОДЫ… 5

ПОСТРОЕНИЕ ПРОГРАММНОЙ МОДЕЛИ.. 5

Выбор метода. 5

Построение алгоритма программы.. 6

Составление программы на BORLANDC++3.1. 8

ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ.. 8

ВЫВОДЫ ПО ВСЕЙ КУРСОВОЙ РАБОТЕ.. 9

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ… 10

ПРИЛОЖЕНИЕ.. 11

ПРОВЕДЕНИЕ АНАЛИЗА СВОЙСТВ, ХАРАКТЕРИЗУЮЩИХ ЗАДАННУЮ ТЕМУ

Полем называется множество с двумя определёнными операциями — сложением и умножением, причем имеют место следующие аксиомы:

1. Множество образует абелеву группу по сложению;
2. Поле замкнуто относительно умножения, и множество ненулевых элементов образует абелеву группу по умножению;
3. Закон дистрибутивности:

Единичный элемент относительно сложения принято обозначать через 0 и называть нулём, аддитивный обратный элементу a элемент — через — a; единичный элемент относительно умножения обозначать 1 и называть единицей, мультипликативный обратный к элементу a элемент — через a^-1.

Поле с конечным числом элементов называют полями Галуа GF(q).

Вычеты по mod(m) определяют разбиение множества целых чисел на m классов эквивалентности: {C₀, C₁, C₂, …, C_m-1}, где C_i={i, i+m, i+2m, …}. Например, для неотрицательных целых чисел по mod(4) имеется четыре класса —

C₀={0, 4, 8, 12, …}             C₂={2, 6, 10, 14, …}

C₁={1, 5, 9, 13, …}             C₃={3, 7, 11, 15, …}

Для представителей можно ввести операции сложения и умножения по mod(4):

Для многочлена, как и для чисел, можно ввести сравнение многочлена a(x) по модулю многочлена q(x): a(x)=r(x) mod q(x). Следовательно, можно говорить и о поле многочленов GF(q) над числовым полем GF(p). Если GF(2) и q(x)=x³+1, то имеем поле многочленов GF(x³+1), состоящее из восьми многочленов: {0, 1, x, x+1, x², x²+1, x²+x, x²+x+1}. Здесь p называется характеристикой поля GF(p); характеристика определяет размерность или порядок полей многочлена: q=pⁿ=2³=8, где n — степень многочлена q(x). Перемножая и складывая многочлены по данному модулю можно составить таблицу умножения и сложения. для GF(x²+x+1), размерность которого в два раза меньше описанного выше поля {0, 1, x, x+1} таблицы умножения и сложения представлены выше (если каждому элементу последнего множества сопоставить в соответствие число {0, 1, 2, 3}).

Наибольший общий делитель двух заданных положительных чисел s и t может быть вычислен с помощью итеративного применения алгоритма деления. Эта процедура известна как алгоритм Евклида. Предположим, что t<s; алгоритм Евклида сводится к последовательности шагов:

s=Q⁽¹⁾t+t⁽¹⁾

t=Q⁽²⁾t⁽¹⁾+t⁽²⁾

t⁽¹⁾=Q⁽³⁾ t⁽²⁾+t⁽³⁾

^……….

t^(n-2)=Q⁽ⁿ⁾t^(n-1)+t⁽ⁿ⁾

t^(n-1)=Q⁽ⁿ⁺¹⁾t⁽ⁿ⁾

где остановка процесса наступает при получении нулевого остатка. Последний ненулевой остаток t⁽ⁿ⁾ равен наибольшему общему делителю. Этот факт будет доказан в следующей теореме. Матричные обозначения позволяют кратко записать шаги алгоритма Евклида в виде:

Теорема. (Алгоритм Евклида).[2][3] Для двух заданных положительных чисел s и t, где s>t, пусть s⁽⁰⁾=s и t⁽⁰⁾=t. Решение рекуррентных уравнений:

при r=1, …, n даётся величиной

где n равно наименьшему целому числу, для которого t⁽ⁿ⁾=0.

Доказательство:

Так как t^(r+1)<t­­^(r) и все остатки неотрицательны, то в конце концов наступит n, для которого t⁽ⁿ⁾=0, так что завершение работы алгоритма произойдёт обязательно, легко проверить, что

Поэтому

так что s⁽ⁿ⁾ должно делить оба числа s и t и, следовательно, делит НОД[s, t]. Далее

так что любой делитель чисел s и t делит s⁽ⁿ⁾. Следовательно, НОД[s, t] делит s⁽ⁿ⁾ и делится на s⁽ⁿ⁾. Таким образом

s⁽ⁿ⁾=НОД[s, t]

Это завершает доказательство.

Из этой теоремы вытекает несколько важных следствий. Пусть

Тогда получаем следствие:

Для любых чисел s и t найдутся такие целые числа a и b, что

НОД[s, t]=as+bt

Доказательство

Достаточно доказать следствие для положительных s и t. Так как

и s⁽ⁿ⁾=НОД[s, t], то утверждение выполняется при  и .

Следствие 2:

Получаемые в процессе алгоритма Евклида матричные элементы и удовлетворяют равенствам:

Доказательство

Используя выписанные выше выражения для обратной матрицы и обращая первое равенство из доказательства прошлого следствия получаем

Утверждение вытекает отсюда непосредственно.

Теорема. (малая теорема Ферма).[1] Если m – простое число и a – произвольное целое число, не делящееся на m, то a^m-1=1 (mod m).

Доказательство.

a*a^m-2=a^m-1=1 (mod m).

Следствие. Если m – простое число, то в кольце Z_m выполняется равенство a^-1=a^m-2.

Пример: если a=2, m=5, то 2^-1=2^5-2(mod 5)=8(mod 5)=3(mod 5). Тогда 2^-1=3.

Нахождение обратных элементов с использованием алгоритма Евклида[1]

Так как у поля модуль m – простое число, то для нахождения обратного элемента для элемента x можно найти уравнение ax+my=1. Тогда слагаемое my равно нулю (вычисления производятся по модулю m). Следовательно, элемент a является обратным к элементу x.

Нахождения обратных чисел можно реализовать с помощью малой теоремы Ферма.

В соответствии с малой теоремой Ферма a^-1=a^m-2.

ВЫВОДЫ

В соответствии с вышеописанными теоремами программа должна находить обратный элемент используя малую теорему Ферма или алгоритм Евклида. Программа должна работать для достаточно широкого спектра значений модуля, по которому производятся вычисления и элемента для которого вычисляется обратный элемент. То есть программа не должна вычислять обратный элемент, например, только для чисел, которые меньше 3 или 5 (для этих чисел обратный элемент в поле вычетов по такому маленькому модулю можно вычислить и без компьютера). То есть программа должна быть предназначена для вычисления обратного элемента для достаточно большого (в разумных пределах) числа. Также программа должна проверять корректность входных данных. То есть, в случае, если НОД введённого модуля и элемента должно равняться единице, в противном случае программа должна сообщать, о том, что данный элемент не имеет обратного.

ПОСТРОЕНИЕ ПРОГРАММНОЙ МОДЕЛИ

Напишем программу нахождения обратного числа для данного элемента в данном поле.

Поле возьмём по модулю простого числа.

Выбор метода

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

9²¹=109418989131512359209.

Можно приводить числа по данному модулю после каждого умножения, что решит эту проблему для не очень больших чисел. Но для достаточно больших чисел эта проблема останется.

Причём значение имеет даже последняя девятка. хранения такого большого числа в компьютере и выполнения с ним операций вызывает определённые трудности. Следовательно, лучше реализовать алгоритм Евклида, работающий со стандартными типами данных, хотя для некоторых случаев (при небольших числах) алгоритм, построенный на следствии малой теоремы Ферма будет подходить больше.

Построение алгоритма программы

Напишем программу, реализующую нахождение обратного элемента с использованием алгоритма Евклида. По алгоритму Евклида (учитывая, что НОД[a, m]=1) выполняются следующие соотношения:

s=Q⁽¹⁾t+t⁽¹⁾

t=Q⁽²⁾t⁽¹⁾+t⁽²⁾

t⁽¹⁾=Q⁽³⁾ t⁽²⁾+t⁽³⁾

^……….

t^(n-3)=Q^(n-1)t^(n-2)+t^(n-1)

t^(n-2)=Q⁽ⁿ⁾t^(n-1)+t⁽ⁿ⁾

t^(n-1)=Q⁽ⁿ⁺¹⁾t⁽ⁿ⁾+1

Для нахождения уравнения ax+my=1 выразим с помощью предпоследнего уравнения число 1 через t^(n-1)и t^(n-2):

1= t^(n-1) -Q⁽ⁿ⁺¹⁾t⁽ⁿ⁾

1= t^(n-1)— Q⁽ⁿ⁺¹⁾* (t^(n-2)- Q⁽ⁿ⁾t^(n-1))

1= (1+Q⁽ⁿ⁺¹⁾ *Q⁽ⁿ⁾)*t^(n-1)— Q⁽ⁿ⁺¹⁾ *t^(n-2)

1= — Q⁽ⁿ⁺¹⁾ *t^(n-2)+ (1+Q⁽ⁿ⁺¹⁾ *Q⁽ⁿ⁾)*t^(n-1)

Как отсюда видно множитель — Q⁽ⁿ⁺¹⁾ «перешёл» из правого слагаемого (из слагаемого с большим) в левое слагаемое (с меньшим индексом). Проверим дальше. Теперь выразим 1 через t^(n-2) и t^(n-3):

1= — Q⁽ⁿ⁺¹⁾ *t^(n-2)+ (1+Q⁽ⁿ⁺¹⁾ *Q⁽ⁿ⁾)*t^(n-1)

1= — Q⁽ⁿ⁺¹⁾ *t^(n-2)+ (1+Q⁽ⁿ⁺¹⁾ *Q⁽ⁿ⁾)*( t^(n-3)— Q^(n-1)t^(n-2))

1= (1+Q⁽ⁿ⁺¹⁾ *Q⁽ⁿ⁾)*t^(n-3)+ ((1+Q⁽ⁿ⁺¹⁾ *Q⁽ⁿ⁾)*( — Q^(n-1)) — Q⁽ⁿ⁺¹⁾)t^(n-2) (1)

Как видно снова множитель из правого слагаемого перешёл в левое слагаемое. Правое слагаемое составилось из прошлого множителя правого слагаемого, умноженного на следующее частное, и прошлого левого слагаемого. То есть, если на данном шаге перед слагаемым t с меньшим индексом стоит множитель a, а перед другим слагаемым – b, то для следующего шага перед слагаемым с меньшим индексом будет стоять b, а перед другим слагаемым b*a-a.

На основании полученной закономерности составим алгоритм нахождения НОД по алгоритму Евклида. Для хранения Q⁽ⁱ⁾проще всего использовать стек, так как в данном случае на каждом шаге будет необходим Q⁽ⁱ⁾, который был сохранён последним.

Графическая схема алгоритма, осуществляющего нахождение НОД с помощью алгоритма Евклида:

Этот алгоритм при использовании для нахождения обратных элементов в качестве числа t должен получать модуль в котором производить вычисления, а в качестве числа s элемент, для которого необходимо найти обратный элемент. Тогда в выходной переменной s2 будет получаться обратный элемент для числа s. Естественно при получении входных данных модуль t должен быть таким, что полученная структура была бы полем. То есть число t должно быть простым. (когда t – простое, то НОД[t, s]=1 и в полученном выражении слагаемое с t сокращается).

Составление программы на BORLANDC++3.1

Для хранения модуля и введённого числа подходит тип long (для того, чтобы программа могла работать с более длинными числами).

Для реализации стека был составлен специальный модуль, в котором были реализованы стандартные процедуры работы со стеком (PUSH (добавление элемента в стек), POP (извлечение элемента из стека), EMPTY (проверка стека на пустоту)).

С использованием стека была разработана процедура, вычисляющая с помощью алгоритма Евклида НОД двух чисел и возвращающая также полученное уравнение.

Для реализации интерфейса, понятного пользователю в данном случае не обязательно использовать графический режим, так как программа не работает с графическими объектами. Для работы с текстовым экраном был выбран стандартный модуль <CONIO.H>, поскольку в нём содержатся все необходимые процедуры: для вывода текстовой информации на экран, изменения цвета, для создания текстового окна и считывания информации, вводимой пользователем

ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ

Для проверки работоспособности программы достаточно вычисленный обратный элемент умножить на данный элемент и взять остаток от деления полученного числа на модуль, по которому производились вычисления. Если получится единица, то обратный элемент вычислен верно. Для сравнения были произведены вычисления с использованием малой теоремы Ферма и калькулятора.

Как видно в таблице весь последний столбец занят единицами, кроме той строки, для которой не существует обратного элемента. Следовательно, программа работает верно.

ВЫВОДЫ ПО ВСЕЙ КУРСОВОЙ РАБОТЕ

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. — М.: ИНФРА-М; Новосибирск: НГТУ, 2003. — 280 с. — (Серия «Высшее образование»).

1. Блейхут, Ричард Э. Быстрые алгоритмы цифровой обработки сигналов Р. Блейхут; Пер. с англ. И.И. Грушко

1. Теория и практика кодов, контролирующих ошибки Р. Блейхут; Пер. с англ. И. И. Грушко, В. М. Блиновского; Под ред. К. Ш. Зигангиров

ПРИЛОЖЕНИЕ

Листинг программы:

Модуль «STEK.CPP»:

Распечатка главной программы «REVKLID3.CPP»: