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

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

НОД(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. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

Калькулятор, реализующий расширенный алгоритм Евклида.

На сайте уже есть калькулятор Наибольший общий делитель (НОД) двух целых чисел, который использует алгоритм Евклида. Как оказалось, помимо обычного алгоритма Евклида существует еще и его «расширенный» вариант. Отличие его в том, что, кроме нахождения НОД, он также еще и находит коэффициенты, при которых будет справедливо следующее выражение:

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

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

Алгоритм Евклида

Python

Pascal:

Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.

  • 15 ноября 2019 в 11:44 Почему стоит научиться > сайты, или как написать свой первый парсер на Python
  • 25 ноября 2019 в 15:24 Быстрее ли JavaScript, чем Python?
  • 3 декабря 2019 в 14:37 Python List Comprehension
  • 13 декабря 2019 в 17:15 Стиллер паролей на python с отправкой на почту
  • 15 декабря 2019 в 20:08 C# Entity Framework Wizard crash
Читайте также:  Dablbdmb8e0 rev e схема

Это «Песочница» — раздел, в который попадают дебютные посты пользователей, желающих стать полноправными участниками сообщества.

Если у вас есть приглашение, отправьте его автору понравившейся публикации — тогда её смогут прочитать и обсудить все остальные пользователи Хабра.

Чтобы исключить предвзятость при оценке, все публикации анонимны, псевдонимы показываются случайным образом.