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

редактировать

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

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

ax + by = \ gcd (a, b).

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

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

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

Содержание

1 Описание
- 1.1 Пример
- 1.2 Доказательство
2 Полиномиальный расширенный алгоритм Евклида
3 Псевдокод
4 Упрощение дробей
5 Вычисление мультипликативных обратных в модульных структурах
- 5.1 Модульные целые числа
- 5.2 Простые расширения алгебраических полей
  - 5.2.1 Пример
6 Случай более двух чисел
7 См. Также
8 Ссылки
9 Внешние ссылки

Описание

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

r 0 = ar 1 = b ⋮ ri + 1 = ri - 1 - qiri и 0 ≤ ri + 1 < | r i | (this defines q i) ⋮ {\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 {\ begin {align} 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 {(это определяет}} q_ {i}) \\ \, \, \, \ vdots \ end {align}}}

Основным свойством евклидова деления является то, что неравенства справа однозначно определяют $qi { \ displaystyle q_ {i}}$ $q_ {i}$ и $ri + 1 {\ displaystyle r_ {i + 1}}$ $r _ {{i + 1}}$ из $ri - 1 {\ displaystyle r_ {i- 1}}$ $r _ {{i- 1}}$ и $ri. {\ displaystyle r_ {i}.}$ $r _ {{ i}}.$

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

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

r 0 = ar 1 = bs 0 = 1 s 1 = 0 t 0 = 0 t 1 = 1 ⋮ ⋮ ri + 1 = ri - 1 - qiri и 0 ≤ ri + 1 < | r i | (this defines q i) s i + 1 = s i − 1 − q i s i t i + 1 = t i − 1 − q i t i ⋮ {\displaystyle {\begin{aligned}r_{0}=ar_{1}=b\\s_{0}=1s_{1}=0\\t_{0}=0t_{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}}}

{\begin{aligned}r_{0}=ar_{1}=b\\s_{0}=1s_{1 }=0\\t_{0}=0t_{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}}

Вычисление также останавливается, когда $rk + 1 = 0 {\ displaystyle r_ {k + 1} = 0}$ $r _ {{k + 1}} = 0$ и дает

$rk {\ displaystyle r_ {k}}$ $r_ {k}$ - наибольший общий делитель входных данных $a = r 0 {\ displaystyle a = r_ {0}}$ $a = r_ {0}$ и $b = r 1. {\ displaystyle b = r_ {1}.}$ ${\ displaystyle b = r_ {1}.}$
Коэффициенты Безу равны $sk {\ displaystyle s_ {k}}$ $s_ {k}$ и $tk, {\ displaystyle t_ {k}, }$ ${\ dis playstyle t_ {k},}$ то есть $gcd (a, b) = rk = ask + btk {\ displaystyle \ gcd (a, b) = r_ {k} = as_ {k} + bt_ {k}}$ ${\ displaystyle \ gcd (a, b) = r_ {k} = as_ {k} + bt_ {k}}$
Частные a и b по их наибольшему общему делителю даются по формуле $sk + 1 = ± b gcd (a, b) {\ displaystyle s_ {k + 1} = \ pm {\ frac {b} {\ gcd (a, b)}}}$ $s _ {{k + 1}} = \ pm {\ frac {b} {\ gcd (a, b)}}$ и $tk + 1 = ± a gcd (a, b) {\ displaystyle t_ {k + 1} = \ pm {\ frac {a } {\ gcd (a, b)}}}$ $t _ {{k + 1}} = \ pm {\ frac {a} {\ gcd (a, b)}}$

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

| s i | ≤ ⌊ b 2 gcd (a, b) ⌋ и | т я | ≤ ⌊ a 2 НОД (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 | 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}

для $0 ≤ я ≤ К, {\ displaystyle 0 \ leq i \ leq k,}$ ${\ displaystyle 0 \ leq i \ leq k,}$ где $⌊ x ⌋ {\ displaystyle \ lfloor x \ rfloor}$ $\ lfloor x \ rfloor$ обозначает неотъемлемая часть числа x, то есть наибольшее целое число, не превышающее x.

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

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

Пример

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

индекс i	частное q i − 1	остаток r i	si	ti
0		240	1	0
1		46	0	1
2	240 ÷ 46 = 5	240-5 × 46 = 10	1 - 5 × 0 = 1	0 - 5 × 1 = −5
3	46 ÷ 10 = 4	46 - 4 × 10 = 6	0 - 4 × 1 = −4	1 - 4 × −5 = 21
4	10 ÷ 6 = 1	10 - 1 × 6 = 4	1-1 × −4 = 5	−5-1 × 21 = −26
5	6 ÷ 4 = 1	6-1 × 4 = 2	−4-1 × 5 = −9	21-1 × −26 = 47
6	4 ÷ 2 = 2	4-2 × 2 = 0	5-2 × −9 = 23	−26-2 × 47 = -120

Доказательство

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

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

As $a = r 0 {\ displaystyle a = r_ {0}}$ $a = r_ {0}$ и $b = r 1, {\ displaystyle b = r_ {1},}$ $b = r_ {1},$ мы имеем $asi + bti = ri {\ displaystyle as_ {i} + bt_ {i} = r_ { i}}$ $as_ {i} + bt_ {i} = r_ {i}$ для i = 0 и 1. Отношение следует по индукции для всех $i>1 {\ displaystyle i>1}$ $i>1$ :

ri + 1 = ri - 1 - riqi = (asi - 1 + bti - 1) - (asi + bti) qi = (asi - 1 - asiqi) + (bti - 1 - btiqi) = asi + 1 + bti + 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}.}

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}}.

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

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

A i = (s i - 1 s i t i - 1 t i). {\ displaystyle A_ {i} = {\ begin {pmatrix} s_ {i-1} s_ {i} \\ t_ {i-1} t_ {i} \ end {pmatrix}}.}

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

Повторяющееся отношение можно переписать в матричной форме

A i + 1 = A i ⋅ (0 1 1 - qi). {\ displaystyle A_ {i + 1} = A_ {i} \ cdot {\ begin {pmatrix} 0 1 \\ 1 -q_ {i} \ end {pmatrix}}.}

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

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

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

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

| с к + 1 | = | b gcd (a, b) | ≥ 2 | s k | и | т к + 1 | = | a gcd (a, b) | ≥ 2 | т к |. {\ displaystyle | s_ {k + 1} | = \ left | {\ frac {b} {\ gcd (a, b)}} \ right | \ geq 2 | s_ {k} | \ qquad {\ text {и }} \ qquad | t_ {k + 1} | = \ left | {\ frac {a} {\ gcd (a, b)}} \ right | \ geq 2 | t_ {k} |.}

{\ 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} |.}

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

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

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

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

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

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

as + bt = \ gcd (a, b)

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

\ deg s <\ deg b- \ deg (\ gcd (a, b)), \ quad \ deg t <\ deg a- \ deg (\ gcd (a, b)).

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

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

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

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

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

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

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

Псевдокод

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

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

(old_r, r): = (r, old_r - quotient * r)

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

prov: = r; r: = old_r - частное × prov; old_r: = prov;

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

function extended_gcd (a, b) (old_r, r): = (a, b) (old_s, s): = (1, 0) (old_t, t): = (0, 1) в то время как r ≠ 0 do частное: = 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 равны нулю, а другое отрицательное, наибольший общий делитель, который выводится, отрицателен, и все знаки вывода должны быть изменены.

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

function extended_gcd (a, b) s: = 0; old_s: = 1 r: = b; old_r: = a в то время как r ≠ 0 do частное: = 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) else bezout_t: = 0 вывод «Коэффициенты Безу:», (old_s, bezout_t) вывод «наибольший общий делитель:», old_r

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

Упрощение дробей

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

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

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

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

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

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

Модульные целые числа

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

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

ns + at = 1 {\ displaystyle ns + at = 1}

ns + at = 1

Уменьшение этой идентичности по модулю n дает

при 1 mod n. {\ displaystyle at \ Equiv 1 \ mod n.}

{\ displaystyle at \ Equiv 1 \ mod n.}

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

Чтобы адаптировать расширенный алгоритм Евклида к этой проблеме, следует отметить, что коэффициент Безу для n не требуется, и, следовательно, его не нужно вычислять. Кроме того, для получения положительного результата, меньшего n, можно использовать тот факт, что целое число t, предоставленное алгоритмом, удовлетворяет | t | < n. That is, if t < 0, one must add n to it at the end. This results in the pseudocode, in which the input n is an integer larger than 1.

функция инверсия (a, n) t: = 0; тритон: = 1 r: = n; newr: = a while newr ≠ 0 do частное: = r div newr (t, newt): = (newt, t - частное × тритон) ( r, newr): = (newr, r - частное × newr) если r>1, тогдаreturn «a не обратимо» ift < 0, затем t: = t + n return t

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

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

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

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

функция инверсия (a, p) t: = 0; тритон: = 1 r: = p; newr: = a, а newr ≠ 0 do частное: = r div newr (r, newr): = (newr, r - частное × новее) ( t, тритон): = (тритон, t - частное × тритон) если степень (r)>0, тоreturn "Либо p не является несократимым, либо кратно 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), корректировка в последней строке псевдокода не требуется.

шаг	частное	r, newr	s, news	t, newt
		p = x + x + x + x + 1	1	0
		a = x + x + x + 1	0	1
1	x + 1	x = p - a (x + 1)	1	x + 1 = 0 - 1 × (x + 1)
2	x + x	x + 1 = a - x (x + x)	x + x = 0-1 (x + x)	x + x + 1 = 1 - (x + x) (x + 1)
3	x + 1	1 = x - (x + 1) (x + 1)	х + х + х + х + 1 = 1 - (х +1) (х + х)	х + х + х + х = (х + 1) - (х + 1) (х + x + 1)
4	x + 1	0 = (x + 1) - 1 × (x + 1)	x + x + x + 1 = (x + x) - (x + 1) (x + x + x + x + 1)

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

Случай более двух чисел

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

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

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

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

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

gcd (a 1, a 2,…, an) = gcd (a 1, gcd (a 2, gcd (a 3,…, gcd (an - 1, an))),…), {\ displaystyle \ gcd (a_ {1}, a_ {2}, \ dots, a_ {n}) = \ gcd (a_ {1}, \, \ gcd (a_ {2}, \, \ gcd (a_ {3}, \ точки, \ gcd (a_ {n-1} \,, a_ {n}))), \ dots),}

{\ 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}))), \ точек),}

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

См. Также

Ссылки

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

Внешние ссылки

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

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