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

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

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

$|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\leq i\leq k,$ где $\lfloor x\rfloor$ обозначает целую часть x , то есть наибольшее целое число , не большее x .

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

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

Пример

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

индекс я	частное q i −1	Остаток r i	и я	т я
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

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

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

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

Как $a=r_{0}$ и $b=r_{1},$ у нас есть $as_{i}+bt_{i}=r_{i}$ для i = 0 и 1. Соотношение следует по индукции для всех $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}.$$

Таким образом $s_{k}$ и $t_{k}$ – коэффициенты Безу.

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

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

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

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

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

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

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

алгоритм

См. Также: Полиномиальный наибольший общий делитель § тождество Безу и расширенный алгоритм НОД.

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

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

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

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

и

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

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

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

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

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

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

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

Псевдокод

В этом и последующих разделах 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 "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

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

Наконец, обратите внимание, что в личности Безу $ax+by=\gcd(a,b)$, можно решить для $y$ данный $a,b,x,\gcd(a,b)$. Таким образом, оптимизация приведенного выше алгоритма заключается в вычислении только $s_{k}$ последовательность (которая дает коэффициент Безу $x$), а затем вычислить $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 "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

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

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

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

if s = 0 then output "Division by zero"
if s < 0 then s := −s;  t := −t   (for avoiding negative denominators)
if s = 1 then output -t        (for avoiding denominators equal to 1)
output -t/s

Доказательство этого алгоритма основано на том факте, что s и t — два взаимно простых целых числа, такие что as + bt = 0 и, следовательно, ${\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 . В частности, если n простое число , a имеет мультипликативную обратную величину, если оно не равно нулю (по модулю n ). Таким образом, Z / n Z является полем тогда и только тогда, когда n простое.

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

$ns+at=1$

Уменьшение этого тождества по модулю n дает

$at\equiv 1\mod n.$

Таким образом , t деления t на n , является мультипликативным обратным модулем 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 ^д , поле порядка q является простым алгебраическим расширением простого поля из p элементов, порожденным корнем неприводимого многочлена степени d .

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

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

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 + 1 и a = x ⁶ + х ⁴ + x + 1 — это элемент, обратный которому требуется, затем выполнение алгоритма приводит к вычислениям, описанным в следующей таблице. Напомним, что в полях порядка 2 ^н , имеем − z = z и z + z = 0 для каждого элемента z в поле). Поскольку 1 — единственный ненулевой элемент GF(2), корректировка в последней строке псевдокода не требуется.

шаг	частное	р, сейчас	с, новости	т, Ньют
		р = х 8 + х 4 + х 3 + х + 1	1	0
		а = х 6 + х 4 + х + 1	0	1
1	х 2 + 1	х 2 = р - а ( х 2 + 1)	1	х 2 + 1 = 0 − 1 · ( х 2 + 1)
2	х 4 + х 2	х + 1 = а - х 2 ( х 4 + х 2 )	х 4 + х 2 = 0 − 1( х 4 + х 2 )	х 6 + х 2 + 1 = 1 − ( х 4 + х 2 ) ( х 2 + 1)
3	х + 1	1 = х 2 - ( х + 1) ( х + 1)	х 5 + х 4 + х 3 + х 2 +1 = 1 − ( х +1)( х 4 + х 2 )	х 7 + х 6 + х 3 + х = ( х 2 + 1) − ( х + 1) ( х 6 + х 2 + 1)
4	х + 1	0 = ( х + 1) - 1 × ( х + 1)	х 6 + х 4 + х + 1 = ( х 4 + х 2 ) − ( х +1)( х 5 + х 4 + х 3 + х 2 +1)

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

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

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

Итак, если $na+mb=\gcd(a,b)$ тогда есть $x$ и $y$ такой, что $x\gcd(a,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},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),$

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

См. также

• Евклидова область
• Теорема о линейном сравнении
• Куттака

Ссылки

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

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

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