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

{{стиль статьи|дата=2023-11-23}}
{{нет сносок|дата=2023-11-23}}

{{Универсальная карточка}}

'''Расширенный алгоритм Евклида''' — модификация [[Алгоритм Евклида|алгоритма Евклида]], вычисляющая, кроме [[Наибольший общий делитель|наибольшего общего делителя (НОД)]] целых чисел <math>a</math> и <math>b</math>, ещё и коэффициенты [[Соотношение Безу|соотношения Безу]], то есть такие целые <math>x</math> и <math>y</math>, что <math>ax + by = \text{НОД}{\left(a, b\right)}.</math>

Алгоритм является {{нп5|Удостоверяющий алгоритм|удостоверяющим||certifying algorithm}}, то есть помимо решения задачи приводит также доказательство корректности этого решения. Это связано с тем, что НОД является единственным числом, которое одновременно удовлетворяет уравнению и делит входные числа. Алгоритм позволяет также почти без дополнительных затрат вычислять частные от деления <math>a</math> и <math>b</math> на их наибольший общий делитель.

Под {{em|расширенным алгоритмом Евклида}} также понимается {{нп5|Наибольший общий делитель многочленов|очень похожий алгоритм||Polynomial greatest common divisor}} для вычисления наибольшего общего делителя многочленов и вычисления коэффициентов соотношения Безу двух многочленов от одной переменной.

Когда <math>a</math> и <math>b</math> [[Взаимно простые числа|взаимно просты]], получаемый расширенным алгоритмом Евклида <math>x</math> является [[Обратное по модулю число|модульным обратным]] числа <math>a</math> по [[Сравнение по модулю|модулю]] <math>b</math>, а <math>y</math> является модульным обратным числа <math>b</math> по модулю <math>a</math>. Аналогично, расширенный алгоритм Евклида для многочленов позволяет вычислить [[обратное число]] в [[Алгебраическое расширение|алгебраических расширениях]] и, в частности, в [[Конечное поле|конечных полях]] непростого порядка. Поэтому оба расширенных алгоритма Евклида широко используются в [[Криптография|криптографии]]. В частности, вычисление [[Обратное по модулю число|обратного элемента по модулю]] является существенным шагом в получении пары [[Ключ (криптография)|ключей]] в методе [[RSA]] шифрования с открытым ключом.

== Описание ==
Стандартный алгоритм Евклида выполняется путём последовательных [[Деление с остатком|делений с остатком]], при этом частное не используется, и сохраняется только ''остаток''. В расширенном алгоритме используются и частные от деления. Точнее, стандартный  алгоритм Евклида для чисел <math>a</math> и <math>b</math> в качестве исходных данных состоит из вычисления последовательности <math>q_1,\ldots, q_k</math> частных и последовательности <math>r_0,\ldots, r_{k+1}</math> остатков, таких что:  
:<math>
\begin{align}
r_0 & =a \\
r_1 & =b \\
& \,\,\,\vdots \\
r_{i+1} & =r_{i-1}-q_i r_i \quad \text {и} \quad 0\leqslant r_{i+1} < |r_i| \quad\text{(это определяет }q_i)\\
& \,\,\, \vdots
\end{align}
</math>
Одним из свойств деления с остатком является то, что неравенство справа определяет единственность <math>q_i</math> и <math>r_{i+1}</math> для <math>r_{i-1}</math> и <math>r_{i}</math>.

Вычисление останавливается, когда достигaет нулевого остатка <math>r_{k+1}</math>. Наибольший общий делитель тогда равен последнему ненулевому остатку <math>r_{k}</math>.

Расширенный алгоритм Евклида вычисляет последовательности <math>q_1,\ldots, q_k</math> и <math>r_0,\ldots, r_{k+1}</math> аналогично, но добавляет ещё две последовательности <math>s_1,\ldots, s_{k+1}</math> и <math>t_0,\ldots, t_{k+1}</math>, вычисляемые следующим образом:
<center><math>
\begin{align}
r_0 & =a & r_1 & =b \\
s_0 & =1 & s_1 & =0 \\
t_0 & =0 & t_1 & =1 \\
& \,\,\,\vdots & & \,\,\,\vdots \\
r_{i+1} & =r_{i-1}-q_i r_i & \text {и } 0 & \leqslant r_{i+1} < |r_i| & \text{(это определяет } q_i \text{)}\\
s_{i+1} & =s_{i-1}-q_i s_i \\
t_{i+1} & =t_{i-1}-q_i t_i \\
& \,\,\, \vdots
\end{align}
.</math></center>

Вычисление останавливается, когда <math>r_{k+1}=0</math>. В итоге получаются искомые величины:
*<math>r_k</math> равен наибольшему общему делителю входных значений <math>a=r_0</math> и <math>b=r_1</math>.
* [[Соотношение Безу|Коэффициенты Безу]] равны <math>s_k</math> и <math>t_k,</math>, то есть <math>\text{НОД}{\left(a, b\right)}=r_k=as_k+bt_k</math>.
* Частные от деления <math>a</math> и <math>b</math> на их наибольший общий делитель задаются величинами <math>s_{k+1}=\pm\dfrac{b}{\text{НОД}{\left(a, b\right)}}</math> и <math>t_{k+1}=\pm\dfrac{a}{\text{НОД}{\left(a, b\right)}}</math>.

Более того, если оба числа <math>a</math> и <math>b</math> положительны и <math>\text{НОД}{\left(a, b\right)}\neq\min{\left(a,b\right)}</math>, то 
:<math>|s_i| \leqslant \left\lfloor\dfrac{b}{2\text{НОД}{\left(a,b\right)}}\right\rfloor\quad \text{и} \quad |t_i| \leqslant \left\lfloor\dfrac{a}{2\text{НОД}{\left(a,b\right)}}\right\rfloor</math>
для <math>0\leqslant i \leqslant k</math>, где <math>\lfloor x\rfloor</math> означает [[Целая часть|целую часть]] числа <math>x</math>, то есть, наибольшее целое, не превосходящее <math>x</math>.

Отсюда вытекает, что пара [[Соотношение Безу|коэффициентов Безу]], которую даёт расширенный алгоритм Евклида, является ''минимальной парой'' [[Соотношение Безу|коэффициентов Безу]], поскольку она является единственной парой, удовлетворяющей обоим неравенствам выше.

Также из этого следует, что алгоритм может быть выполнен без риска [[Целочисленное переполнение|целочисленного переполнения]] [[Компьютерная программа|программой]], использующей целые числа фиксированного размера, который превосходит размер обоих чисел <math>a</math> и <math>b</math>.

=== Пример ===

Следующая таблица показывает, как расширенный алгоритм Евклида работает с входными числами {{nowrap|{{color|green|240}}}} и {{nowrap|{{color|green|46}}}}. [[Наибольший общий делитель]] — последний ненулевой элемент, {{nowrap|{{color|red|2}}}} в столбце «остаток». Вычисление завершается на строке 6, поскольку остаток в ней равен {{nowrap|{{color|red|0}}}}. Коэффициенты Безу появляются в двух последних ячейках предпоследней строки. Легко проверить, что {{nowrap|1={{color|Magenta|−9}} × {{color|green|240}} + {{color|Magenta|47}} × {{color|green|46}} = {{color|red|2}}}}. Наконец, два последних значения  {{nowrap|{{color|darkcyan|23}}}} и {{nowrap|{{color|darkcyan|−120}}}} последней строки, с точностью до знака, являются частными от деления входных значений {{nowrap|{{color|green|46}}}} и {{nowrap|{{color|green|240}}}} на наибольший общий делитель {{nowrap|{{color|red|2}}}}.

{| class="wikitable" style="text-align:right;"
! индекс ''i''!! {{color|blue|частное ''q''<sub>''i''−1</sub> }}!! {{color|olive|остаток ''r''<sub>''i''</sub>}}!! {{color|brown|''s''<sub>''i''</sub> }}!! ''t''<sub>''i''</sub>
|-
| 0 || ||{{color|green|240}}||{{color|brown|1}} || 0
|-
| 1 || ||{{color|green|46}} || {{color|brown|0}} || 1
|-
| 2 ||{{color|green|240}} ÷ {{color|green|46}} = {{color|blue|5}}
||{{color|green|240}} − {{color|blue|5}} × {{color|green|46}} = {{color|olive|10}}
||{{color|brown|1}} − {{color|blue|5}} × {{color|brown|0}} = {{color|brown|1}}
|| 0 − {{color|blue|5}} × 1 = −5
|-
| 3 ||{{color|green|46}} ÷ {{color|olive|10}} = {{color|blue|4}}
||{{color|green|46}} − {{color|blue|4}} × {{color|olive|10}} = {{color|olive|6}}
||{{color|brown|0}} − {{color|blue|4}} × {{color|brown|1}} = {{color|brown|−4}}
|| 1 − {{color|blue|4}} × −5 = 21
|-
| 4 ||{{color|olive|10}} ÷ {{color|olive|6}} = {{color|blue|1}}
||{{color|olive|10}} − {{color|blue|1}} × {{color|olive|6}} = {{color|olive|4}}
||{{color|brown|1}} − {{color|blue|1}} × {{color|brown|−4}} = {{color|brown|5}}
|| −5 − {{color|blue|1}} × 21 = −26
|-
| 5 ||{{color|olive|6}} ÷ {{color|olive|4}} = {{color|blue|1}}
||{{color|olive|6}} − {{color|blue|1}} × {{color|olive|4}} = {{color|red|2}}
||{{color|brown|−4}} − {{color|blue|1}} × {{color|brown|5}} = {{color|Magenta|−9}}
|| 21 − {{color|blue|1}} × −26 = {{color|Magenta|47}}
|-
| 6 ||{{color|olive|4}} ÷ {{color|olive|2}} = {{color|blue|2}}
||{{color|olive|4}} − {{color|blue|2}} × {{color|olive|2}} = {{color|red|0}}
||{{color|brown|5}} − {{color|blue|2}} × {{color|brown|−9}} = {{color|darkcyan|23}}
|| −26 − {{color|blue|2}} × 47 = {{color|darkcyan|−120}}
|}

=== Доказательство ===
Поскольку <math>0\leqslant r_{i+1}<|r_i|,</math> последовательность <math>r_i</math> является строго убывающей последовательностью неотрицательных целых (начиная с ''i'' = 2). Тогда алгоритм должен остановиться на некотором <math> r_{k+1}=0.</math> Это доказывает, что алгоритм когда-нибудь завершится.

Поскольку <math>r_{i+1}= r_{i-1} - r_i q_i,</math> наибольшие общие делители пар <math>(r_{i-1}, r_i)</math> и <math>(r_{i}, r_{i+1})</math> одинаковы. По [[математическая индукция|индукции]] можно показать, что наибольший общий делитель входных <math>a=r_0, b=r_1 </math> будет тем же самым, что и для <math> r_k, r_{k+1}=0</math>, и таким образом доказать, что <math>r_k</math> является наибольшим общим делителем ''a'' и ''b''. (До этого момента доказательство то же самое, что и для [[Алгоритм Евклида#Алгоритм Евклида для целых чисел|классического алгоритма Евклида]].)

Поскольку <math>a=r_0</math> и <math>b=r_1</math>, при ''i'' = 0 и 1 <math>as_i+bt_i=r_i</math>. Далее отношение доказывается по индукции для всех <math>i>1</math>:

:<math>r_{i+1} = r_{i-1} - r_i q_i = (as_{i-1}+bt_{i-1}) - (as_i+bt_i)q_i = (as_{i-1}-as_iq_i) + (bt_{i-1}-bt_iq_i) = as_{i+1}+bt_{i+1}.</math>

Тогда <math>s_k</math> и <math>t_k</math> являются коэффициентами Безу.

Рекуррентные соотношения можно переписать в матричном виде:

:<math>A_i=\begin{pmatrix} s_{i-1} & s_i\\ t_{i-1} & t_i \end{pmatrix},\  A_{i+1} = A_i \cdot \begin{pmatrix} 0 & 1\\ 1 & -q_i \end{pmatrix}.</math>

Матрица <math>A_1</math> является единичной матрицей и её определитель равен единице. Определитель самой правой матрицы здесь равен −1. Отсюда следует, что определитель <math>A_i</math> равен <math>(-1)^{i-1}.</math> В частности, для <math>i=k+1</math> определитель <math>A_{k+1}</math> равен <math>s_k t_{k+1}-t_k s_{k+1} = (-1)^k.</math> Если рассматривать это как соотношение Безу, получится, что <math>s_{k+1}</math> и <math>t_{k+1}</math> [[Взаимно простые числа|взаимно просты]]. Соотношение <math>as_{k+1}+bt_{k+1}=0</math>, доказанное выше, и [[лемма Евклида]] показывают, что <math>s_{k+1}</math> делит {{mvar|b}}, то есть <math>b=ds_{k+1}</math> для некоторого целого {{mvar|d}}. При делении на <math>s_{k+1}</math> соотношения <math>as_{k+1}+bt_{k+1}=0</math> получается <math>a=-dt_{k+1}.</math> Таким образом, <math>s_{k+1}</math> и <math>-t_{k+1}</math> являются взаимно простыми целыми, которые являются частными от деления {{mvar|a}} и {{mvar|b}} на общий делитель, который является их наибольшим общим делителем или ему  [[Противоположное число|противоположным]].

Последнее утверждение может быть доказано следующим образом: пусть ''a'' и ''b'' положительны и <math>\text{НОД}(a,b)\neq\min(a,b)</math>. Тогда <math>a\neq b </math>, и если  <math>a<b</math>, то последовательности ''s'' и ''t'' для (''a'',''b'') в расширенном алгоритме являются, с точностью до начальных нулей и единиц, последовательностями ''t'' и ''s'' для (''b'',''a''). Определения затем показывают, что случай (''a'',''b'') сводится к случаю (''b'',''a''). Таким образом, без потери общности, можно предположить, что  <math>a>b</math>.

<math>s_2</math> равно 1, а <math>s_3</math> (которое существует ввиду <math>\text{НОД}(a,b)\neq\min(a,b)</math>) отрицательно. Таким образом,  <math>s_i</math> меняет знак и строго возрастает по абсолютной величине, что следует по индукции из определения и факта, что <math>q_i\geqslant 1</math> для <math>1\leqslant i \leqslant k</math>. Случай для <math>i=1</math> выполняется, поскольку <math>a>b</math>. То же самое верно для <math>t_i</math> после нескольких первых членов по тем же причинам. Более того, <math>q_k \geqslant 2</math> (если ''a'' и ''b'' положительны и <math>\text{НОД}(a,b)\neq\min(a,b)</math>). Тогда:

:<math>|s_{k+1}|=\left |\frac{b}{\text{НОД}(a,b)} \right | \geqslant 2|s_k| \qquad \text{и} \qquad |t_{k+1}|= \left |\frac{a}{\text{НОД}(a,b)} \right | \geqslant 2|t_k|.</math>

Это, и тот факт, что <math>s_k,t_k</math> не меньше по абсолютному значению любого предыдущего <math>s_i</math> или <math>t_i</math> соответственно, завершает доказательство.

== Расширение алгоритма Евклида для многочленов ==
{{see also|Наибольший общий делитель многочленов#Соотношение Безу и расширенный алгоритм НОД}}

Для многочленов от одной переменной с коэффициентами в [[Поле (алгебра)|поле]] всё работает аналогичным образом, включая деление Евклида, соотношение Безу и расширенный алгоритм Евклида. Первое отличие в том, что в делении Евклида и в алгоритме неравенство <math>0\leqslant r_{i+1}<|r_i|</math> следует заменить на неравенство степеней <math>\deg r_{i+1}<\deg r_i.</math> Остальное остаётся тем же самым, просто заменяем целые числа многочленами.

Второе отличие лежит в границах размера коэффициентов Безу, даваемых расширенным алгоритмом Евклида, которые более точны в случае многочленов, что приводит к следующей теореме.

''Если  a и b два ненулевых многочлена, расширенный алгоритм Евклида даёт единственную пару многочленов'' (''s'', ''t''), ''таких что''
:<math>as+bt=\text{НОД}(a,b)</math>
''и''
:<math>\deg s < \deg b - \deg (\text{НОД}(a,b)), \quad \deg t < \deg a - \deg (\text{НОД}(a,b)).</math>

Третье отличие в том, что для многочленов наибольший общий делитель определён с точностью до умножения на ненулевую константу. Есть несколько путей определить наибольший общий делитель однозначно.

В математике обычно требуют, чтобы наибольший общий делитель был [[Приведённый многочлен|приведённым многочленом]]. Чтобы этого достичь, достаточно разделить все элементы результата на ведущий коэффициент <math>r_{k}.</math> Это позволяет, если  ''a'' и ''b'' взаимно простые, получить 1 в правой части неравенства Безу. В противном случае получим ненулевую константу. В [[Символьные вычисления|компьютерной алгебре]] многочлены обычно имеют целые коэффициенты и этот способ нормализации наибольшего общего делителя приводит к большому числу дробей.

Другим способом нормализации наибольшего общего делителя для случая целых коэффициентов является деление выходного многочлена на НОД коэффициентов многочлена <math>r_{k},</math>, чтобы получить [[Примитивный многочлен (алгебра)|примитивный]] наибольший общий делитель. Если входные многочлены взаимно просты, нормализация даёт наибольший общий делитель, равный 1. Недостатком  этого подхода является большое количество дробей, которые должны быть вычислены и упрощены.

Третий подход заключается в расширении алгоритма вычисления {{нп5|Наибольший общий делитель многочленов|промежуточных последовательностей псевдоостатков ||Polynomial greatest common divisor}} ([[Результант|подрезультантов]]) аналогично расширению алгоритма Евклида до расширенного алгоритма Евклида. Это позволяет, начав с многочлена с целыми коэффициентами, получать в процессе вычислений многочлены с целыми коэффициентами. Более того, каждый вычисленный остаток <math>r_i</math> остаётся  подрезультантом. В частности, если многочлены взаимно просты,  то  соотношение Безу превращается в  
:<math>as+bt=\operatorname{Res}(a,b),</math>
где <math>\operatorname{Res}(a,b)</math> означает [[результант]] для ''a'' и ''b''. В таком виде соотношения Безу нет в формуле знаменателя. Если разделить всё на результант, получим классическое соотношение Безу с явным общим знаменателем для рациональных чисел которые при этом появляются.

== Псевдокод ==
{{hatnote|В этой и следующей секциях '''''div''''' является вспомогательной функцией, вычисляющей частное от [[Деление с остатком|деления с остатком]] её левого аргумент на правый аргумент.}} 
Для реализации вышеописанного алгоритма следует заметить, что только два последних значения индексированных переменных нужны на каждом шаге. Таким образом, для экономии памяти, каждая индексированная переменная должна быть заменена просто двумя переменными.

Для простоты следующий алгоритм (и другие алгоритмы в этой статье) используют [[Присваивание|параллельные присваивания]]. В языках программирования, не поддерживающих данную возможность параллельное присвоение необходимо  осуществлять с использованием дополнительной переменной. Например, первое присвоение
 (old_r, r) := (r, old_r - quotient * r)
эквивалентно
 prov := r;
 r := old_r - quotient × prov;
 old_r := prov;
и аналогично для других параллельных присвоений. Это приводит к следующему коду:

 '''function''' extended_gcd(a, b)
     (old_r, r) := (a, b)
     (old_s, s) := (1, 0)
     (old_t, t) := (0, 1)
     
     '''while''' r ≠ 0 '''do'''
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r − quotient × r)
         (old_s, s) := (s, old_s − quotient × s)
         (old_t, t) := (t, old_t − quotient × t)
     
     '''output''' "коэффициенты Безу:", (old_s, old_t)
     '''output''' "наибольший общий делитель:", old_r
     '''output''' "частные от деления на НОД:", (t, s)

Частные от деления ''a'' и ''b'' на их наибольший общий делитель, который тоже есть в выводе, могут иметь неверный знак. Это легко исправить в конце вычислений, но не сделано здесь для упрощения кода. Аналогично, если ''a'' или ''b'' равно нулю, а второе число отрицательно, наибольший общий делитель в выводе отрицателен, так что все знаки в выводе нужно изменить.

Наконец заметим, что соотношение Безу <math>ax + by = \text{НОД}(a, b)</math> мoжно решить относительно <math>y</math> при заданных <math>a, b, x, \text{НОД}(a, b)</math>. Тогда оптимизацией для алгоритма выше будет вычислять только последовательность <math>s_k</math> (которая приводит к коэффициенту Безу <math>x</math>), а значение <math>y</math> вычислить в конце алгоритма:

 '''function''' extended_gcd(a, b)
     s := 0;    old_s := 1
     r := b;    old_r := a
          
     '''while''' r ≠ 0 '''do'''
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r − quotient × r)
         (old_s, s) := (s, old_s − quotient × s)
     
     '''if''' b ≠ 0 '''then'''
         bezout_t := (old_r − old_s × a) '''div''' b
     '''else'''
         bezout_t := 0
     
     '''output''' "коэффициенты Безу:", (old_s, bezout_t)
     '''output''' "наибольший общий делитель:", old_r

Однако, во многих случаях это не будет реальной оптимизацией — прежний алгоритм  нечувствителен к переполнению при использовании целых чисел в машине (то есть целых чисел с фиксированной верхней границей представления), умножение ''old_s * a'' при вычислении ''bezout_t'' может вызвать переполнение, что ограничивает оптимизацию только на входные данные, которые не превосходят половины максимального размера целых чисел. Если используются целые числа неограниченного размера, время, необходимое для умножения и деления растёт квадратично от размера целых чисел. Из этого следует, что «оптимизация» заменяет последовательность умножений/делений малых чисел на одно умножение/деление, которое требует большего времени выполнения, чем операции, которые оно заменяет, взятые вместе.

== Упрощение деления ==
Деление {{math|{{sfrac|''a''|''b''}}}} находится в канонической упрощённой форме, если {{math|''a''}} и {{math|''b''}} [[Взаимно простые числа|взаимно просты]] и {{math|''b''}} положительно. Эта каноническая упрощённая форма может быть получена путём замены трёх строк вывода на псеводокод 
 '''if''' {{math|1=''s'' = 0}} '''then output''' "Деление на ноль"
 '''if''' {{math|1=''s'' < 0}} '''then''' {{math|1=''s'' := −''s''}};  {{math|1=''t'' := −''t''}}   (''во избежание нулевых делителей'')
 '''if''' {{math|1=''s'' = 1}} '''then output''' {{math|-''t''}}        (''во избежание делителей, равных '' 1)
 '''output''' {{math|{{sfrac|-''t''|''s''}}}}

Доказательство этого алгоритма полагается на факт, что {{math|''s''}} и {{math|''t''}} являются двумя взаимно простыми целыми, такими что <math>as+bt=0</math>, а тогда <math>\frac{a}{b} = -\frac{t}{s}</math>. Для получения канонически упрощённой формы достаточно изменить знак для получения положительного делителя.

Если {{math|''b''}} делит {{math|''a''}} нацело, алгоритм выполняет только одну итерацию, и мы имеем {{math|1=''s'' = 1}} в конце алгоритма. Это единственный случай, когда вывод является целым числом.

== Вычисление обратного в модулярных структурах ==

Расширенный алгоритм Евклида является важным средством вычисления [[Обратное число|обратных чисел]] в модулярных структурах, обычно в [[Сравнение по модулю|модулярных целых]] и [[Алгебраическое расширение|алгебраических расширениях полей]]. Важным примером последнего случая являются конечные поля непростого порядка.

=== Целые по модулю ===
{{main|Сравнение по модулю}}
Если {{math|''n''}} является положительным целым, кольцо [[Сравнение по модулю|'''Z'''/''n'''''Z''']] может быть отождествлено со множеством {{math|{0, 1, ..., ''n''-1}{{void}}}} остатков от [[Деление с остатком|деления с остатком]] на {{math|''n''}}, сложение и умножение заключается во взятии остатка от деления на {{math|''n''}} результатов сложения и умножения целых чисел. Элемент {{math|''a''}}  {{math|'''Z'''/''n'''''Z'''}} имеет обратный элемент (то есть элемент [[Обратимый элемент|обратимый]]), если он [[Взаимно простые числа|взаимно прост]] с {{math|''n''}}. В частности, если {{math|''n''}} является [[Простое число|простым]], {{math|''a''}} имеет обратное, если оно не нулевое (по модулю  {{math|''n''}}). То есть, {{math|'''Z'''/''n'''''Z'''}} будет полем тогда и только тогда, когда {{math|''n''}} просто.

Соотношение Безу утверждает, что {{math|''a''}} и {{math|''n''}} взаимно просты тогда и только тогда, когда существуют целые {{math|''s''}}и {{math|''t''}}, такие что 
:<math>ns+at=1</math>
Сравнение по модулю {{math|''n''}} даёт 
:<math>at \equiv 1 \mod n.</math>
Тогда {{math|''t''}}, или точнее, остаток от деления {{math|''t''}} на {{math|''n''}}, равен  обратному числу {{math|''a''}} по модулю {{math|''n''}}.

Чтобы приспособить расширенный алгоритм Евклида для этой задачи, следует заметить, что коэффициент Безу при {{math|''n''}} не нужен, а потому нет необходимости его и вычислять. Также, для получения результата в виде положительного числа, меньшего ''n'', можно использовать факт что целое {{math|''t''}}, предоставляемое алгоритмом, удовлетворяет соотношению <math>|t| < n</math>. То есть, если <math>t<0</math>, можно добавить {{math|''n''}} в конце. Это приводит к псевдокоду, в котором входное значение ''n'' является целым, большим 1.
 <code> '''function''' inverse(a, n)
     t := 0;     newt := 1
     r := n;     newr := a
 
     '''while''' newr ≠ 0 '''do'''
         quotient := r '''div''' newr
         (t, newt) := (newt, t − quotient × newt) 
         (r, newr) := (newr, r − quotient × newr)
 
     '''if''' r > 1 '''then'''
         '''return''' "не обратимо"
     '''if''' t < 0 '''then'''
         t := t + n
 
     '''return''' t</code>

=== Алгебраические расширения полей ===

Расширенный алгоритм Евклида является также главным средством для вычисления [[Обратное число|обратных элементов]] в [[Расширение поля|алгебраических расширениях полей]]. Важный случай, широко используемый в [[Криптография|криптографии]] и [[Теория кодирования|теории кодирования]], это случай [[Конечное поле|конечных полей]] непростого порядка. Фактически, если {{math|''p''}} просто и {{math|1=''q'' = ''p''<sup>''d''</sup>}}, поле порядка {{math|''q''}} является алгебраическим расширением [[Характеристика (алгебра)|простого поля]] с {{math|''p''}} элементами, образованного корнем [[Неприводимый многочлен|неприводимого многочлена]] степени {{math|''d''}}.

Алгебраическое расширение {{math|''L''}} поля {{math|''K''}}, генерируемое корнем неприводимого многочлена {{math|''p''}} степени {{math|''d''}} можно отождествить с [[факторкольцо]]м <math>K[X]/\langle p\rangle,</math>, а его элементы находятся в [[Биекция|биективном соотношении]] с многочленами степени, меньшей {{math|''d''}}.Сложениев {{math|''L''}} есть сложение многочленов. Умножение в {{math|''L''}} есть остаток от {{нп5|Наибольший общий делитель многочленов|деления с остатком||Euclidean division of polynomials}}на {{math|''p''}} произведения многочленов. Таким образом, для завершения арифметики в {{math|''L''}} остаётся только определить, каким образом вычислять обратные элементы. Делается это с расширенным алгоритмом Евклида.

Алгоритм очень похож на приведённый выше для вычисления модульного обратного. Есть два главных отличия — во-первых, предпоследняя строка не нужна, поскольку получаемые коэффициенты Безу имеют всегда степень меньшую, чем {{math|''d''}}. Во-вторых, Наибольший общий делитель, который получается, если входные данные являются взаимно простыми многочленами, может быть любым ненулевым элементом {{math|''K''}}. Этот коэффициент Безу (многочлен обычно имеет положительную степень), следует умножить на обратный этому элементу в {{math|''K''}}. В псевдокоде (ниже) {{math|''p''}} является многочленом степени, большим единицы, а {{math|''a''}} является многочленом.

 <code>'''function''' inverse(a, p)
     t := 0;     newt := 1
     r := p;     newr := a
 
     '''while''' newr ≠ 0 '''do'''
         quotient := r '''div''' newr
         (r, newr) := (newr, r − quotient × newr)
         (t, newt) := (newt, t − quotient × newt)
 
     '''if''' degree(r) > 0 '''then''' 
         '''return''' "Either p is not irreducible or a is a multiple of p"
 
     '''return''' (1/r) × t</code>

==== Пример ====

Например, пусть многочлен <math>p=x^8+x^4+x^3+x+1</math> определяет конечное поле <math>GF(2^8)</math>  , а <math>a=x^6+x^4+x+1</math> является элементом, обратный которому нужно найти. Тогда работа алгоритма приведена ниже в таблице. Напомни, что в поле порядка <math>2^n</math>, имеем -''z'' = ''z'' и ''z'' + ''z'' = 0 для любого или элемента ''z'' поля). Поскольку 1 является единственным ненулевым элементом GF(2), подгонка последней строки псевдокода не нужна.
{| class="wikitable"
|-
! шаг
! &nbsp;частное&nbsp;
! r, newr
!s, news
! t, newt
|-
| 
| &nbsp;
|<math>p=x^8+x^4+x^3+x+1</math>
|1
| &nbsp;0
|-
| align="center" | 
| &nbsp;
|<math>a=x^6+x^4+x+1</math>
|0
| &nbsp;1
|-
| align="center" | 1
| <math>x^2+1</math>
| <math>x^2=p-a(x^2+1)</math>
|1
| <math>x^2+1=0-1\times(x^2+1)</math>
|-
| align="center" | 2
| <math>x^4+x^2</math>
| <math>x+1=a-x^2(x^4+x^2)</math>
| <math>x^4+x^2=0-1(x^4+x^2)</math>
| <math>x^6+x^2+1=1-(x^4+x^2)(x^2+1)</math>
|-
| align="center" | 3
| &nbsp;''x'' + 1
| <math>1=x^2-(x+1)(x+1)</math>
| <math>x^5+x^4+x^3+x^2+1=1-(x +1)(x^4+x^2)</math>
| <math>x^7+x^6+x^3+x=(x^2+1)-(x+1) (x^6+x^2+1)</math>
|-
| align="center" | 4
| &nbsp;''x'' + 1
| <math>0=(x+1)-1\times(x+1)</math>
| <math>x^6+x^4+x+1=(x^4+x^2)-(x+1)(x^5+x^4+x^3+x^2+1)</math>
| &nbsp;
|}

Таким образом, обратный элемент равен <math>x^7+x^6+x^3+x</math>, что подтверждается {{нп5|Арифметика конечного поля|умножением двух элементов||finite field arithmetic}} и взятия остатка по {{math|''p''}} от результата.

== Случай более двух чисел ==
Можно обрабатывать случай более двух чисел итеративно.  Сначала покажем, что <math>\text{НОД}(a,b,c) = \text{НОД}(\text{НОД}(a,b),c)</math>.  Для доказательства положим <math>d=\text{НОД}(a,b,c)</math>. По определению НОД <math>d</math> является делителем <math>a</math> и <math>b</math>.  Тогда <math>\text{НОД}(a,b)=k d</math> для некоторого <math>k</math>.  Аналогично <math>d</math> является делителем <math>c</math>, так что <math>c=jd</math> для некоторого <math>j</math>.  Положим <math>u=\text{НОД}(k,j)</math>. По построению <math>u</math>, <math>ud | a,b,c</math>, но поскольку <math>d</math> является наибольшим делителем, <math>u</math> является [[Обратимый элемент|обратимым элементом]].  А поскольку <math>ud=\text{НОД}(\text{НОД}(a,b),c)</math>, результат доказан.

Таким образом, если <math>na + mb = \text{НОД}(a,b)</math>, то есть <math>x</math> и <math>y</math>, такие что <math>x\text{НОД}(a,b) + yc = \text{НОД}(a,b,c)</math>, так что конечным уравнением будет

: <math>x(na + mb) + yc = (xn)a + (xm)b + yc =  \text{НОД}(a,b,c).\,</math>

Для перехода к ''n'' числам используем индукцию

:<math>\text{НОД}(a_1,a_2,\dots,a_n) =\text{НОД}(a_1,\, \text{НОД}(a_2,\, \text{НОД}(a_3,\dots, \text{НОД}(a_{n-1}\,,a_n))),\dots),</math>

== См. также ==
* [[Евклидово кольцо]]
* [[Китайская теорема об остатках]]
* {{нп5|Куттака|||Kuṭṭaka}}

==Примечания== 
{{примечания|2}}
==Литература==
{{refbegin|colwidth=30em}}
* {{книга
|заглавие=[[The Art of Computer Programming]]
|автор=Donald Knuth
|ref=Knuth
|издательство=Addison-Wesley
|том=2
|часть=Chapter 4
}}.
** Перевод {{книга
|автор=Дональд Кнут
|заглавие=Искусство программирования
|год=1998 
|Издательство=Диалектика-Вильямс 
|том=2. Получисленные алгоритмы
}}
*{{книга
|автор=[[Кормен, Томас|Thomas H. Cormen]], [[Лейзерсон, Чарльз Эрик|Charles E. Leiserson]], [[Ривест, Рональд Линн|Ronald L. Rivest]], [[Штайн, Клиффорд|Clifford Stein]]
|заглавие=[[Introduction to Algorithms]]
|издание=Second Edition
|издательство=MIT Press and McGraw-Hill
|год=2001
|часть=section 31.2: Greatest common divisor.
|страницы=859–861 
|ISBN=0-262-03293-7
}}
**{{книга
|заглавие = [[Алгоритмы: построение и анализ]],  3-е издание 
|оригинал = Introduction to Algorithms, Third Edition 
|автор = Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн 
|страниц = 1328 
|isbn = 978-5-8459-1794-2 
|год = 2013 
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]] 
}}
{{refend}}

== Ссылки ==
{{wikibooks|Реализации алгоритмов/Расширенный алгоритм Евклида|Расширенный алгоритм Евклида}}
* [http://mathforum.org/library/drmath/view/51675.html Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)]

{{Теоретико-числовые алгоритмы|state=collapsed}}

{{rq|checktranslate|style|grammar}}

[[Категория:Теоретико-числовые алгоритмы]]
[[Категория:Евклид]]