обратный элемент в поле

14.10.202314.08.2023 admin 0 Comments

Обратный по модулю в кольце

Обратный по модулю

Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.

Использование:

Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.

Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».

Если установлена галочка «подробнее», то калькулятор помимо обратного элемента по модулю выдает некоторые этапы вычисления.

Ограничения:

Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.

Что значит по модулю?

Синонимом к данному выражению является выражение «остаток от деления«. То есть выражение «5 по модулю 3» эквивалентно выражению «остаток от деления 5 на 3». И в том и в другом случае подразумевается в ответе число 2, так как остаток от деления 5 на 3 = 2.

Стоить отметить тот факт, что по модулю m мы имеем числа от 0 до m — 1. Действительно, остаток от деления на m никогда не превысит m — 1.

Что такое обратное?

Напомним, что число, умноженное на его обратное, равно 1. Из базовой арифметики мы знаем, что:

Число, обратное к числу A, равно 1 / A, поскольку A * (1 / A) = 1 (например, значение, обратное к 5, равно 1/5).
Все действительные числа, кроме 0, имеют обратную
Умножение числа на обратное к A эквивалентно делению на A (например, 10/5 соответствует 10 * 1/5)

Что такое обратное по модулю?

В модульной арифметике у нас нет операции деления. Тем не менее, у нас есть модульные инверсии.

Как найти модульный обратный

Наивный метод нахождения модульного обратного a ( по модулю m) является:
Шаг 1. Рассчитать a * b mod m для значений b от 0 до m — 1
Шаг 2. Модульная инверсия a mod m — это значение b, при котором a * b mod m = 1

Обратите внимание, что термин b mod m может иметь только целочисленное значение от 0 до m — 1, поэтому тестирование больших значений чем (m-1) для b является излишним.

Вы наверно уже догадались, что наивный метод является очень медленным. Перебор всех чисел от 0 до m-1 для большого модуля довольно-таки трудоемкая задача. Существует гораздо более быстрый метод нахождения инверсии a (mod m). Таковым является расширенный алгоритм Евклида, который реализован в данном калькуляторе.

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

Представим наибольший общий делитель числа a и модуля m в виде ax + my. То есть НОД(a, m) = ax + my. Помним, что обратный элемент существует только тогда, когда a и m взаимно просты, то есть их НОД(a, m) = 1. Отсюда: ax + my = 1 — линейное диофантово уравнение второго порядка. Необходимо решить данное уравнение в целых числах и найти x, y.

Найденный коэффициент x будет являться обратным элементом к a по модулю m. Это следует оттуда, что, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим: ax = 1 (m).

Расширенный алгоритм Евклида, в отличие от классического, помимо наибольшего общего делителя позволяет найти также коэффициенты x, y.

Алгоритм:

Выход : d, x, y, такие что d = gcd(a, m) = ax + my

3. [Выход] Вернуть (d, x, y) = (a₀, x₀, y₀)

Непонятен алгоритм? Ничего страшного, примеры ниже именно для этого и предназначены.

Пример для наивного метода.

Пусть a = 3, m = 7. То есть нам необходимо найти обратный элемент к 3 по модулю 7.

3 * 0 ≡ 0 (mod 7) — не подходит
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) Пример на расширенный алгоритм Евклида.

Пусть аналогично предыдущему примеру имеем a = 3, m = 7. Также, требуется найти обратный элемент к 3 по модулю 7. Согласно алгоритму начинаем заполнять таблицу на каждом этапе цикла.

Итерация	q	a0	a1	x0	x1	y0	y1
0	—	3	7	1	0	0	1
1	0	7	3	0	1	1	0
2	2	3	1	1	-2	0	1
3	3	1	0	-2	0	1	-3

После 3-ей итерации получили a1 = 0, строго по алгоритму из раздела «Теория» заканчиваем работу алгоритма.

Делаем проверку:

3 * (-2) + 7 * 1 = 1
-6 + 7 = 1
1 = 1 — верно!

Источник

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

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

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

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

СОДЕРЖАНИЕ

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

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

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

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

0	1	2	3	0	1	2	3
0	0	1	2	3	0	0	0	0	0
1	1	0	3	2	1	0	1	2	3
2	2	3	0	1	2	0	2	3	1
3	3	2	1	0	3	0	3	1	2

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

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

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

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

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

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

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

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

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

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

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

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

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

Следствие 2:

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

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

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

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

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

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

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

ВЫВОДЫ

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

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

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

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

Выбор метода

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

9 21 =109418989131512359209.

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

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

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

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

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

1= t (n-1) — Q (n+1) * (t (n-2)- Q (n) t (n-1) )

1= (1+Q (n+1) *Q (n) )*t (n-1) — Q (n+1) *t (n-2)

1= — Q (n+1) *t (n-2) + (1+Q (n+1) *Q (n) )*t (n-1)

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

1= — Q (n+1) *t (n-2) + (1+Q (n+1) *Q (n) )*t (n-1)

1= — Q (n+1) *t (n-2) + (1+Q (n+1) *Q (n) )*( t (n-3) — Q (n-1) t (n-2) )

1= (1+Q (n+1) *Q (n) )*t (n-3) + ((1+Q (n+1) *Q (n) )*( — Q (n-1) ) — Q (n+1) )t (n-2) (1)

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

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

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

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

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

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

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

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

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

(элемент, для которого находится обратный эдемент)m

(модуль, по которому производятся вычисления)a m-2a ( m-2) (mod(m))

92310941898913151235920918181258331561011,176561609770433870981098575571e+1739292199910013,6806348825922326789470084006052e+2996720500для вычисленного вручную:

для вычисленного с помощью программы:

1111130001не удалось вычислитьне удалось вычислить22494177777100001не удалось вычислитьне удалось вычислить35714145557653765не удалось вычислитьне удалось вычислитьне существует обратного элемента—34453310000001не удалось вычислитьне удалось вычислить1644429144256323843553333не удалось вычислитьне удалось вычислить7591774391

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

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

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

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

Источник