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

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

${\ displaystyle ax + by = \ gcd (a, b).}$

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

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

Расширенный алгоритм Евклида является особенно полезным , когда и б являются взаимно простыми . С этим положением, х представляет собой модульное мультипликативное обратное из в по модулю Ь , и у является модульным мультипликативным обратным Ь по модулю . Аналогично, полиномиальный расширенный алгоритм Евклида позволяет вычислять мультипликативную обратную функцию в расширениях алгебраических полей и, в частности, в конечных полях непростого порядка. Отсюда следует, что оба расширенных алгоритма Евклида широко используются в криптографии. . В частности, вычисление модульного обратного мультипликативного числа является важным шагом в получении пар ключей в методе шифрования с открытым ключом RSA .

Описание [ править ]

Стандартный алгоритм Евклида использует последовательность евклидовых делений , частные которых не используются. Сохраняются только остатки . Для расширенного алгоритма используются последовательные частные. Точнее, стандартный алгоритм Евклида с 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{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(this defines }}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{and }}0&\leq r_{i+1}<|r_{i}|&{\text{(this defines }}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 \gcd(a,b)=r_{k}=as_{k}+bt_{k}}$
• Частные a и b по их наибольшему общему делителю равны и${\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}}$${\displaystyle t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}}$

Более того, если a и b положительны и , то ${\displaystyle \gcd(a,b)\neq \min(a,b)}$

${\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor }$

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

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

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

Пример [ править ]

В следующей таблице показано, как расширенный алгоритм Евклида работает с входными данными 240 и 46 . Наибольший общий делитель - это последняя ненулевая запись, 2 в столбце «остаток». Вычисление останавливается на строке 6, потому что остаток в ней равен 0 . Коэффициенты Безу появляются в последних двух записях предпоследней строки. Фактически, легко проверить, что −9 × 240 + 47 × 46 = 2 . Наконец, последние две записи 23 и -120 последней строки до знака являются частными входных данных 46 и 240.на наибольший общий делитель 2 .

Доказательство [ править ]

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

Поскольку наибольший общий делитель одинаков для и Это показывает, что наибольший общий делитель входных данных совпадает с делителем. Это доказывает, что это наибольший общий делитель a и b . (До этого момента доказательство такое же, как у классического алгоритма Евклида.)${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i},}$${\displaystyle (r_{i-1},r_{i})}$${\displaystyle (r_{i},r_{i+1}).}$${\displaystyle a=r_{0},b=r_{1}}$${\displaystyle r_{k},r_{k+1}=0.}$${\displaystyle r_{k}}$

Как и у нас есть для я = 0 и 1. Соотношение по индукции для всех :${\displaystyle a=r_{0}}$${\displaystyle b=r_{1},}$${\displaystyle as_{i}+bt_{i}=r_{i}}$${\displaystyle i>1}$

${\displaystyle 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_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}.}$

Таким образом, и являются коэффициентами Безу.${\displaystyle s_{k}}$${\displaystyle t_{k}}$

Рассмотрим матрицу

${\displaystyle A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.}$

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

${\displaystyle A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.}$

Матрица является единичной матрицей, а ее определитель равен единице. Определитель самой правой матрицы в предыдущей формуле равен −1. Отсюда следует , что определитель является , в частности, для нас Просмотр это как идентичности Безу, это показывает , что и являются взаимно простыми . Доказанное выше соотношение и лемма Евклида показывают, что делит b и делит a . Поскольку они взаимно просты, они до своего знака являются частными b и a по их наибольшему общему делителю.${\displaystyle A_{1}}$${\displaystyle A_{i}}$${\displaystyle (-1)^{i-1}.}$${\displaystyle i=k+1,}$${\displaystyle s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.}$${\displaystyle s_{k+1}}$${\displaystyle t_{k+1}}$${\displaystyle as_{k+1}+bt_{k+1}=0}$${\displaystyle s_{k+1}}$${\displaystyle t_{k+1}}$

Чтобы доказать последнее утверждение, предположим, что a и b положительны и . Тогда, и если , можно увидеть, что последовательности s и t для ( a , b ) в рамках EEA являются последовательностями t и s для ( b , a ) с точностью до начальных нулей и единиц . Затем определения показывают, что случай ( a , b ) сводится к случаю ( b , a ). Итак, предположим, что без потери общности.${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle a\neq b}$${\displaystyle a<b}$${\displaystyle a>b}$

Видно, что это 1 и (который существует ) является отрицательным целым числом. После этого знаки меняются по знаку и строго возрастают по величине, что индуктивно следует из определений и того факта, что для , случай имеет место, потому что . То же самое и после первых нескольких сроков по той же причине. Кроме того, легко увидеть, что (когда a и b положительны и ). Таким образом,${\displaystyle s_{2}}$${\displaystyle s_{3}}$${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle s_{i}}$${\displaystyle q_{i}\geq 1}$${\displaystyle 1\leq i\leq k}$${\displaystyle i=1}$${\displaystyle a>b}$${\displaystyle t_{i}}$${\displaystyle q_{k}\geq 2}$${\displaystyle \gcd(a,b)\neq \min(a,b)}$

${\displaystyle |s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.}$

Это сопровождается тем фактом, что они больше или равны по абсолютной величине, чем любые предыдущие или, соответственно, завершенные доказательства.${\displaystyle s_{k},t_{k}}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$

Полиномиальный расширенный алгоритм Евклида [ править ]

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

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

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

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

и

${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}$

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

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

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

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

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

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

Псевдокод [ править ]

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

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

(old_r, r): = (r, old_r - частное * r)

эквивалентно

пров: = г;r: = old_r - частное × пров;old_r: = prov;

и аналогично для других параллельных заданий. Это приводит к следующему коду:

функция extended_gcd (a, b) (old_r, r): = (a, b) (старые_с, с): = (1, 0) (old_t, t): = (0, 1)  в то время как r ≠ 0 сделать частное: = old_r div r (old_r, r): = (r, old_r - частное × r) (old_s, s): = (s, old_s - частное × s) (old_t, t): = (t, old_t - частное × t)  output "Коэффициенты Безу:", (old_s, old_t) output "Наибольший общий делитель:", old_r output "частные по НОД:", (t, s)

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

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

функция extended_gcd (a, b) s: = 0; old_s: = 1 r: = b; old_r: = а  в то время как r ≠ 0 сделать частное: = old_r div r (old_r, r): = (r, old_r - частное × r) (old_s, s): = (s, old_s - частное × s)  если b ≠ 0, то bezout_t: = частное (old_r - old_s × a, b) еще bezout_t: = 0  вывод "Коэффициенты Безу:", (old_s, bezout_t) вывод "Наибольший общий делитель:", old_r

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

Упрощение дробей [ править ]

Фракция а/бв канонической форме , если упрощенной и Ь являются взаимно простыми , и б положительна. Эту каноническую упрощенную форму можно получить, заменив три выходные строки предыдущего псевдокода на

если  s = 0,  то вывести «Деление на ноль», если  s <0,  то  s  : = - s ; t  : = - t ( чтобы избежать отрицательных знаменателей ), если  s = 1,  то output  - t ( чтобы избежать знаменателей, равных 1) output - т/s

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

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

Вычисление мультипликативных инверсий в модульных структурах [ править ]

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

Модульные целые числа [ править ]

Если n - положительное целое число, кольцо Z / n Z может быть отождествлено с набором {0, 1, ..., n -1} остатков евклидова деления на n , сложение и умножение, состоящее в взятии остаток на n от результата сложения и умножения целых чисел. Элемент a из Z / n Z имеет мультипликативный обратный (то есть, это единица ), если он взаимно прост с n . В частности, если п является главным, a имеет мультипликативную обратную, если она не равна нулю (по модулю n ). Таким образом, Z / n Z является полем тогда и только тогда, когда n простое.

Тождество Безу утверждает, что a и n взаимно просты тогда и только тогда, когда существуют целые числа s и t такие, что

${\displaystyle ns+at=1}$

Сокращение этого тождества по модулю n дает

${\displaystyle at\equiv 1\mod n.}$

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

Чтобы адаптировать расширенный алгоритм Евклида к этой проблеме, следует отметить, что коэффициент Безу для n не требуется и, следовательно, его не нужно вычислять. Кроме того, для получения положительного результата, меньшего чем n , можно использовать тот факт, что целое число t, предоставленное алгоритмом, удовлетворяет | т | < п . То есть, если t <0 , нужно в конце добавить к нему n . Это приводит к псевдокоду, в котором входное n является целым числом больше 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 "a is not invertible" if t < 0 then t := t + n return t

Простые расширения алгебраических полей [ править ]

Расширенный алгоритм Евклида также является основным инструментом для вычисления мультипликативных инверсий в простых расширениях алгебраических полей . Важным случаем, широко используемым в криптографии и теории кодирования , является случай конечных полей непростого порядка. Фактически, если p - простое число и q = p ^d , поле порядка q является простым алгебраическим расширением простого поля из p элементов, порожденным корнем неприводимого многочлена степени d .

Простое алгебраическое расширение L поля K , порожденное корнем неприводимого многочлена p степени d, можно отождествить с фактор-кольцом , и его элементы находятся в биективном соответствии с многочленами степени меньше d . Сложение в L - это сложение многочленов. Умножение в L - это остаток от евклидова деления произведения многочленов на p . Таким образом, чтобы завершить арифметику в L${\displaystyle K[X]/\langle p\rangle ,}$, осталось только определить, как вычислять мультипликативные обратные. Это делается с помощью расширенного алгоритма Евклида.

Алгоритм очень похож на приведенный выше для вычисления модульного мультипликативного обратного. Есть два основных отличия: во-первых, предпоследняя линия не нужна, потому что коэффициент Безу, который предоставляется, всегда имеет степень меньше d . Во-вторых, наибольший общий делитель, который предоставляется, когда входные многочлены взаимно просты, может быть любыми ненулевыми элементами K ; этот коэффициент Безу (полином как правило , положительной степени) имеет , таким образом , необходимо умножить на величину , обратную этому элементу K . В следующем псевдокоде p - многочлен степени больше единицы, а a - многочлен. Кроме того, div - вспомогательная функция, вычисляющая частное евклидова деления.

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

Пример [ править ]

Например, если многочлен, используемый для определения конечного поля GF (2 ⁸ ), равен p = x ⁸  +  x ⁴  +  x ³  +  x  + 1, а a = x ⁶  +  x ⁴  +  x  + 1 - это элемент, обратный желательно, то выполнение алгоритма приводит к вычислению, описанному в следующей таблице. Напомним, что в полях порядка 2 ⁿ - z = z и z + z = 0 для каждого элемента zв поле). Поскольку 1 - единственный ненулевой элемент GF (2), корректировка в последней строке псевдокода не требуется.

Таким образом, обратное значение равно x ⁷  +  x ⁶  +  x ³  +  x , что может быть подтверждено умножением двух элементов вместе и взятием остатка на p результата.

Случай более двух чисел [ править ]

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

Итак, если есть и такие, что итоговое уравнение будет${\displaystyle na+mb=\gcd(a,b)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}$

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

Итак, чтобы применить к n числам, мы используем индукцию

${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),}$

с уравнениями, следующими непосредственно.

См. Также [ править ]

• Евклидова область
• Линейная теорема сравнения
• Kuṭṭaka

Ссылки [ править ]

• Кнут, Дональд . Искусство программирования . Эддисон-Уэсли. Том 2, Глава 4.
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Страницы 859–861 раздела 31.2: Наибольший общий делитель. 

Внешние ссылки [ править ]

В разделе " Реализация алгоритма Викибука" есть страница по теме: Расширенный алгоритм Евклида.

• Источник формы алгоритма, используемого для определения мультипликативного обратного в GF (2 ^ 8)