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

Стандартный алгоритм Евклида выполняется путём последовательных делений с остатком, при этом частное не используется, только остаток сохраняется. В расширенном алгоритме используются и частные от деления. Точнее, стандартный алгоритм Евклида для чисел a и b в качестве исходных данных состоит из вычисления последовательности ${\displaystyle q_{1},\ldots ,q_{k}}$ частных и последовательности ${\displaystyle r_{0},\ldots ,r_{k+1}}$ остатков, таких что

${\displaystyle {\begin{aligned}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{aligned}}}$

Главным свойством деления с остатком является то, что неравенство справа определяет единственность ${\displaystyle q_{i}}$ и ${\displaystyle r_{i+1}}$ для ${\displaystyle r_{i-1}}$ и ${\displaystyle r_{i}.}$

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

Расширенный алгоритм Евклида работает аналогично, но добавляет две другие последовательности

${\displaystyle {\begin{aligned}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{aligned}}}$

Вычисление также останавливается, когда ${\displaystyle r_{k+1}=0}$ и в результате получаем

• ${\displaystyle r_{k}}$ равен наибольшему общему делителю входных значений ${\displaystyle a=r_{0}}$ и ${\displaystyle b=r_{1}.}$
• Коэффициенты Безу равны ${\displaystyle s_{k}}$ и ${\displaystyle t_{k},}$, то есть ${\displaystyle {\text{НОД}}(a,b)=r_{k}=as_{k}+bt_{k}}$
• Частные от деления a и b на их наибольший общий делитель задаются величинами ${\displaystyle s_{k+1}=\pm {\frac {b}{{\text{НОД}}(a,b)}}}$ и ${\displaystyle t_{k+1}=\pm {\frac {a}{{\text{НОД}}(a,b)}}}$

Более того, если оба числа a и b положительно и ${\displaystyle {\text{НОД}}(a,b)\neq \min(a,b)}$, то

${\displaystyle |s_{i}|\leqslant \left\lfloor {\frac {b}{2{\text{НОД}}(a,b)}}\right\rfloor \quad {\text{и}}\quad |t_{i}|\leqslant \left\lfloor {\frac {a}{2{\text{НОД}}(a,b)}}\right\rfloor }$

для ${\displaystyle 0\leqslant i\leqslant k,}$, где ${\displaystyle \lfloor x\rfloor }$ означает целую часть числа x, то есть, наибольшее целое, не превосходящее x.

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

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

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

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

Если a и b два ненулевых многочлена, расширенный алгоритм Евклида даёт единственную пару многочленов (s, t), таких что

${\displaystyle as+bt={\text{НОД}}(a,b)}$

и

${\displaystyle \deg s<\deg b-\deg({\text{НОД}}(a,b)),\quad \deg t<\deg a-\deg({\text{НОД}}(a,b)).}$

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

В математике обычно требуют, чтобы наибольший общий делитель был приведённым многочленом. Чтобы этого достичь, достаточно разделить все элементы результата на ведущий коэффициент ${\displaystyle r_{k}.}$ Это позволяет, если a и b взаимно просты, получить 1 в правой части неравенства Безу. В противном случае получим ненулевую константу. В компьютерной алгебре многочлены обычно имеют целые коэффициенты и этот способ нормализации наибольшего общего делителя приводит к большому числу дробей.

Другим способом нормализации наибольшего общего делителя для случая целых коэффициентов является деление выходного многочлена на НОД коэффициентов многочлена ${\displaystyle r_{k},}$, чтобы получить примитивный наибольший общий делитель. Если входные многочлены взаимно просты, нормализация даёт наибольший общий делитель, равный 1. Недостатком этого подхода является большое количество дробей, которые должны быть вычислены и упрощены.

Третий подход заключается в расширении алгоритма вычисления промежуточных последовательностей псевдоостатков (подрезультантов) аналогично расширению алгоритма Евклида до расширенного алгоритма Евклида. Это позволяет, начав с многочлена с целыми коэффициентами, получать в процессе вычислений многочлены с целыми коэффициентами. Более того, каждый вычисленный остаток ${\displaystyle r_{i}}$ остаётся подрезультантом. В частности, если многочлены взаимно просты, то соотношение Безу превращается в

${\displaystyle as+bt=\operatorname {Res} (a,b),}$

где ${\displaystyle \operatorname {Res} (a,b)}$ означает результант для a и b. В таком виде соотношения Безу нет в формуле знаменателя. Если разделить всё на результант, получим классическое соотношение Безу с явным общим знаменателем для рациональных чисел которые при этом появляются.

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

Для простоты следующий алгоритм (и другие алгоритмы в этой статье) используют параллельные присваивания. В языках программирования, не поддерживающих данную возможность параллельное присвоение необходимо осуществлять с использованием дополнительной переменной. Например, первое присвоение

(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 равно нулю, а второе число отрицательно, наибольший общий делитель в выводе отрицателен, так что все знаки в выводе нужно изменить.

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

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 может вызвать переполнение, что ограничивает оптимизацию только на входные данные, которые не превосходят половины максимального размера целых чисел. Если используются целые числа неограниченного размера, время, необходимое для умножения и деления растёт квадратично от размера целых чисел. Из этого следует, что «оптимизация» заменяет последовательность умножений/делений малых чисел на одно умножение/деление, которое требует большего времени выполнения, чем операции, которые оно заменяет, взятые вместе.

Деление ab находится в канонической упрощённой форме, если a и b взаимно просты и b положительно. Эта каноническая упрощённая форма может быть получена путём замены трёх строк вывода на псеводокод

if s = 0 then output "Деление на ноль"
if s < 0 then s := −s;  t := −t   (во избежание нулевых делителей)
if s = 1 then output -t        (во избежание делителей, равных  1)
output -ts

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

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

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

 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

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

Пример

Например, пусть многочлен ${\displaystyle p=x^{8}+x^{4}+x^{3}+x+1}$ определяет конечное поле ${\displaystyle GF(2^{8})}$ , а ${\displaystyle a=x^{6}+x^{4}+x+1}$ является элементом, обратный которому нужно найти. Тогда работа алгоритма приведена ниже в таблице. Напомни, что в поле порядка ${\displaystyle 2^{n}}$, имеем -z = z и z + z = 0 для любого or элемента z поля). Поскольку 1 является единственным ненулевым элементом GF(2), подгонка последней строки псевдокода не нужна.

шаг	частное	r, newr	s, news	t, newt
		${\displaystyle p=x^{8}+x^{4}+x^{3}+x+1}$	1	0
		${\displaystyle a=x^{6}+x^{4}+x+1}$	0	1
1	${\displaystyle x^{2}+1}$	${\displaystyle x^{2}=p-a(x^{2}+1)}$	1	${\displaystyle x^{2}+1=0-1\times (x^{2}+1)}$
2	${\displaystyle x^{4}+x^{2}}$	${\displaystyle x+1=a-x^{2}(x^{4}+x^{2})}$	${\displaystyle x^{4}+x^{2}=0-1(x^{4}+x^{2})}$	${\displaystyle x^{6}+x^{2}+1=1-(x^{4}+x^{2})(x^{2}+1)}$
3	x + 1	${\displaystyle 1=x^{2}-(x+1)(x+1)}$	${\displaystyle x^{5}+x^{4}+x^{3}+x^{2}+1=1-(x+1)(x^{4}+x^{2})}$	${\displaystyle x^{7}+x^{6}+x^{3}+x=(x^{2}+1)-(x+1)(x^{6}+x^{2}+1)}$
4	x + 1	${\displaystyle 0=(x+1)-1\times (x+1)}$	${\displaystyle x^{6}+x^{4}+x+1=(x^{4}+x^{2})-(x+1)(x^{5}+x^{4}+x^{3}+x^{2}+1)}$

Таким образом, обратный элемент равен ${\displaystyle x^{7}+x^{6}+x^{3}+x}$, что подтверждается умножением двух элементов и взятия остатка по p от результата.

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

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

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc={\text{НОД}}(a,b,c).\,}$

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

${\displaystyle {\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 ),}$

• Евклидово кольцо
• Китайская теорема об остатках
• Куттака

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)