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

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

Этот алгоритм использует соотношения для НОД:

НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b,

Он иллюстрируется следующей программой:


Алгоритм решения уравнения ax+by = 1.

1.Определим матрицу E:

E =

2. Вычислим r — остаток от деления числа a на b, a=bq+r, 0 E *

5. Заменим пару чисел (a,b) на (b,r) и перейдем к шагу 2.


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

Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d.

Псевдокод.

Исходник на Си.

Алгоритм работает за O(log 2 n) операций.


Нахождение обратного элемента по модулю

Для начала заметим, что элемент a кольца Zn обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

Необходимо найти элемент B , обратный элементу A по модулю C .

Такой, что (A*B)%C = 1 .

Как найти B в общем виде?

2 Answers

Для начала, A и C должны быть взаимно просты. Если они не взаимно просты, то любая линейная комбинация (A * X) % C = A * X + C * Y не будет равна единице, то есть, ответа нет.

Окей, пускай числа A и C взаимно просты. Для установления этого вы должны использовать алгоритм Евклида для вычисления НОД. Если вы при этом воспользуетесь расширенным алгоритмом Евклида, вы получите не просто НОД, а и те коэффициенты alpha , beta , при которых

При этом alpha и есть ваш ответ, так как

Все остальные значения B получаются из данного прибавлением кратного числу C .

Есть два пути для решения этой задачи.

Путь первый — использование расширенного алгоритма Евклида.

Алгоритм Евклида ищет НОД двух чисел. Расширенный алгоритм Евклида одновременно с этим представляет НОД как целочисленную линейную комбинацию исходных чисел:

Как легко заметить, если A и C не являются взаимно простыми, то решения нет, а если являются — то коэффициент при A и будет искомым обратным элементом (для доказательства можно заменить в формуле выше b на C и взять обе части равенства по модулю C).

Читайте также:  Вызывают в суд в качестве привлекаемого лица

Рекурсивный алгоритм довольно прост. На очередном шаге большее из двух чисел (для определенности, a) представляется как c + k∙b , после чего алгоритм вызывается рекурсивно для (b, c) :

Отсюда имеем Ka = Kc1 и Kb = Kb1 — Kc1∙k

Получаем примерно такой алгоритм:

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

Эти матричные множители можно будет накопить:

Получается следующий алгоритм:

Теперь, когда у нас есть НОД, осталось найти НОД(A, C), проверить что он равен 1 и взять (Ka % C) в качестве искомого обратного числа.

Время работы — порядка log A по основанию φ итераций (это связано с тем, что худший случай для алгоритма Евклида — соседние числа Фибоначчи).

Путь второй — использование формулы Эйлера

Если число C заранее известно, или есть достаточно времени на подготовку, то можно воспользоваться формулой Эйлера:

Поскольку для имеющих нетривиальные общие делители A и C задача решения все равно не имеет — ограничение нам не помешает.

В соответствии с формулой, ответом будет A ^ (φ(C) — 1) % C . Быстро найти его можно при помощи алгоритма быстрого возведения в степень:

Корректность этого алгоритма легко доказывается если заметить что a ^ x * b — его инвариант.

Разумеется, после получения ответа надо будет проверить что он правильный, если он будет неверным — значит, ответа вовсе не существует (A и C имеют общие делители).

Этот алгоритм будет работать быстрее чем алгоритм Евклида, потому что тут основание логарифма больше, а сами итерации — проще. Но для применения этого алгоритма требуется заранее знать φ(C)

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

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

Читайте также:  Карта россии со сторонами света яндекс компас

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

Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .

Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.

Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.

Для того, чтобы показать это, рассмотрим следующее уравнение:

Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:

Таким образом, найденное x и будет являться обратным к a.

Ссылка на основную публикацию
Оао мобильные телесистемы зачем звонят
Давайте разберемся, что за организация Вымпел-Коммуникации. Что такое они собой представляют и зачем звонят из этой организации? Наверняка вы слышали...
Не работает представление задач в виндовс 10
Представление задач (она же временная шкала или Timeline) - одна из основных функций, созданных в версии 1803 для Windows 10...
Не удается найти конец записи главного каталога
Здравствуйте уважаемые специалисты, я знаю что данная тема доднималась уже не однократно, но к сожалению все варианты решения, которые я...
Обратный элемент по модулю python
Этот алгоритм использует соотношения для НОД: НОД(2*a, 2*b) = 2*НОД(a,b) НОД(2*a, b) = НОД(a,b) при нечетном b, Он иллюстрируется следующей...
Adblock detector