В арифметическом и компьютерном программировании , то расширенный алгоритм Евклида является расширение для алгоритма Евклида и вычисляет, в дополнении к наибольшему общему делителю (GCD) целым числа через и Ь , также коэффициенты идентичности Беза , которые являются целыми числами х и у такой, что
Это сертификационный алгоритм , потому что gcd - единственное число, которое может одновременно удовлетворять этому уравнению и разделять входные данные. Это позволяет также вычислить, почти без дополнительных затрат, частное чисел a и b на их наибольший общий делитель.
Расширенный алгоритм Евклида также относится к очень похожему алгоритму для вычисления наибольшего общего делителя многочлена и коэффициентов тождества Безу двух одномерных многочленов .
Расширенный алгоритм Евклида является особенно полезным , когда и б являются взаимно простыми . С этим положением, х представляет собой модульное мультипликативное обратное из в по модулю Ь , и у является модульным мультипликативным обратным Ь по модулю . Точно так же полиномиальный расширенный алгоритм Евклида позволяет вычислять мультипликативную обратную функцию в расширениях алгебраических полей и, в частности, в конечных полях непростого порядка. Отсюда следует, что оба расширенных алгоритма Евклида широко используются в криптографии . В частности, вычисление модульного обратного мультипликативного числа является важным шагом в получении пар ключей в методе шифрования с открытым ключом RSA .
Описание
Стандартный алгоритм Евклида использует последовательность евклидовых делений , частные которых не используются. Сохраняются только остатки . Для расширенного алгоритма используются последовательные частные. Точнее, стандартный алгоритм Евклида с a и b в качестве входных данных состоит из вычисления последовательности частных и последовательность остатков такие, что
Основное свойство евклидова деления состоит в том, что неравенства справа однозначно определяют а также из а также
Вычисление останавливается, когда достигается остаток который равен нулю; тогда наибольший общий делитель - это последний ненулевой остаток
Расширенный алгоритм Евклида действует аналогично, но добавляет две другие последовательности, как показано ниже.
Вычисление также останавливается, когда и дает
- является наибольшим общим делителем входа а также
- Коэффициенты Безу равны а также это
- Частные a и b по их наибольшему общему делителю даются как а также
Более того, если a и b положительны и, тогда
для где обозначает целую часть от х , то есть наибольшее целое число , не большее , чем х .
Это означает, что пара коэффициентов Безу, предоставляемая расширенным алгоритмом Евклида, является минимальной парой коэффициентов Безу, поскольку это единственная пара, удовлетворяющая обоим вышеупомянутым неравенствам.
Кроме того, это означает , что алгоритм может быть сделано без целочисленного переполнения с помощью компьютерной программы с использованием целых чисел фиксированного размера , который больше , чем у и б .
Пример
В следующей таблице показано, как расширенный алгоритм Евклида работает с входными данными 240 и 46 . Наибольший общий делитель - это последняя ненулевая запись, 2 в столбце «остаток». Вычисление останавливается на строке 6, потому что остаток в ней равен 0 . Коэффициенты Безу появляются в последних двух записях предпоследней строки. Фактически, легко проверить, что −9 × 240 + 47 × 46 = 2 . Наконец, последние два элемента 23 и -120 последней строки представляют собой с точностью до знака частные входных данных 46 и 240 на наибольший общий делитель 2 .
индекс i | частное 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 × 21 -5 = |
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 |
Доказательство
В виде последовательность убывающая последовательность неотрицательных целых чисел (начиная с i = 2). Таким образом, он должен остановиться на некоторых Это доказывает, что алгоритм в конечном итоге останавливается.
В виде наибольший общий делитель одинаков для а также Это показывает, что наибольший общий делитель входа такой же, как у Это доказывает, что является наибольшим общим делителем a и b . (До этого момента доказательство такое же, как у классического алгоритма Евклида.)
В виде а также у нас есть для i = 0 и 1. Соотношение следует по индукции для всех:
Таким образом а также - коэффициенты Безу.
Рассмотрим матрицу
Рекуррентное соотношение можно переписать в матричном виде
Матрица - единичная матрица, и ее определитель равен единице. Определитель самой правой матрицы в предыдущей формуле равен −1. Отсюда следует, что определитель является В частности, для у нас есть Если рассматривать это как личность Безу, это показывает, что а также являются взаимно простыми . Соотношениечто было доказано выше, и лемма Евклида показывает, чтоделит b иделит . Поскольку они взаимно просты, они до своего знака являются частными b и a по их наибольшему общему делителю.
Чтобы доказать последнее утверждение, предположим, что a и b положительны и. Потом,, и если , можно видеть, что последовательности s и t для ( a , b ) в рамках EEA с точностью до начальных нулей и единиц являются последовательностями t и s для ( b , a ). Затем определения показывают, что случай ( a , b ) сводится к случаю ( b , a ). Итак, предположим, что не теряя общий смысл.
Видно, что равно 1 и (который существует ) - отрицательное целое число. После этого чередуются по знаку и строго возрастают по величине, что индуктивно следует из определений и того факта, что для , случай держится, потому что . То же верно и дляпосле первых нескольких сроков по той же причине. Кроме того, легко видеть, что(когда a и b оба положительны и). Таким образом,
Это в сочетании с тем, что больше или равны по абсолютной величине, чем любые предыдущие или же соответственно завершили доказательство.
Полиномиальный расширенный алгоритм Евклида
Для одномерных многочленов с коэффициентами в поле все работает аналогично: евклидово деление, тождество Безу и расширенный алгоритм Евклида. Первое отличие состоит в том, что в евклидовом делении и алгоритме выполняется неравенство необходимо заменить неравенством о степенях В противном случае все, что предшествует этой статье, останется прежним, просто заменив целые числа многочленами.
Второе отличие заключается в ограничении размера коэффициентов Безу, обеспечиваемом расширенным алгоритмом Евклида, который более точен в полиномиальном случае, что приводит к следующей теореме.
Если a и b - два ненулевых многочлена, то расширенный алгоритм Евклида производит уникальную пару многочленов ( s , t ) такую, что
а также
Третье отличие состоит в том, что в полиномиальном случае наибольший общий делитель определяется только с точностью до умножения на ненулевую константу. Существует несколько способов однозначного определения наибольшего общего делителя.
В математике принято требовать, чтобы наибольший общий делитель был моническим многочленом . Для того, чтобы получить это, достаточно разделить каждый элемент на выходе по ведущему коэффициенту вЭто позволяет, если a и b взаимно просты, в правой части неравенства Безу будет 1. В противном случае можно получить любую ненулевую константу. В компьютерной алгебре многочлены обычно имеют целые коэффициенты, и этот способ нормализации наибольшего общего делителя вводит слишком много дробей, чтобы быть удобным.
Второй способ нормализовать наибольший общий делитель в случае многочленов с коэффициентами целых чисел , чтобы разделить каждый выход на содержание вполучить примитивный наибольший общий делитель. Если входные полиномы взаимно просты, эта нормализация также обеспечивает наибольший общий делитель, равный 1. Недостатком этого подхода является то, что во время вычислений необходимо вычислять и упрощать множество дробей.
Третий подход заключается в расширении алгоритма подрезультатных последовательностей псевдоостаточных остатков способом, аналогичным расширению алгоритма Евклида на расширенный алгоритм Евклида. Это позволяет, начиная с полиномов с целыми коэффициентами, все вычисляемые многочлены имеют целые коэффициенты. Более того, каждый вычисленный остатокявляется подрезультатным многочленом . В частности, если входные многочлены взаимно просты, то тождество Безу становится
где обозначает равнодействующую из и б . В этой форме тождества Безу в формуле нет знаменателя. Если все разделить на результат, получится классическая тождество Безу с явным общим знаменателем для рациональных чисел, которые в нем фигурируют.
Псевдокод
Для реализации описанного выше алгоритма следует сначала заметить, что на каждом шаге нужны только два последних значения индексированных переменных. Таким образом, для экономии памяти каждая индексированная переменная должна быть заменена всего двумя переменными.
Для простоты в следующем алгоритме (и других алгоритмах в этой статье) используются параллельные назначения . В языке программирования, который не имеет этой функции, параллельные присвоения необходимо моделировать с помощью вспомогательной переменной. Например, первый,
(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 равны нулю, а другой отрицательный, наибольший общий делитель, который выводится, отрицателен, и все знаки вывода должны быть изменены.
Наконец, обратите внимание, что в личности Безу , можно решить для дано . Таким образом, оптимизация вышеуказанного алгоритма заключается в вычислении только последовательность (что дает коэффициент Безу ), а затем вычислить в конце:
функция 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 , и, следовательно,. Чтобы получить каноническую упрощенную форму, достаточно переместить знак минус, чтобы знаменатель был положительным.
Если b делит a равномерно, алгоритм выполняет только одну итерацию, и в конце алгоритма s = 1 . Это единственный случай, когда результат является целым числом.
Вычисление мультипликативных инверсий в модульных структурах
Расширенный алгоритм Евклида является важным инструментом для вычисления мультипликативных инверсий в модульных структурах, обычно модульных целых числах и расширениях алгебраических полей . Ярким примером последнего случая являются конечные поля непростого порядка.
Модульные целые числа
Если n - положительное целое число, кольцо Z / n Z может быть отождествлено с набором {0, 1, ..., n -1} остатков евклидова деления на n , сложение и умножение, состоящее в взятии остаток на n от результата сложения и умножения целых чисел. Элемент a из Z / n Z имеет мультипликативный обратный (то есть, это единица ), если он взаимно прост с n . В частности, если п является простое , имеет мультипликативный обратный , если он не равен нулю ( по модулю п ). Таким образом, Z / n Z является полем тогда и только тогда, когда n простое.
Тождество Безу утверждает, что a и n взаимно просты тогда и только тогда, когда существуют целые числа s и t такие, что
Сокращение этого тождества по модулю 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 , остается только определить, как вычислять мультипликативные обратные. Это делается с помощью расширенного алгоритма Евклида.
Алгоритм очень похож на приведенный выше для вычисления модульного мультипликативного обратного. Есть два основных отличия: во-первых, предпоследняя линия не нужна, потому что коэффициент Безу, который предоставляется, всегда имеет степень меньше 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 8 ), равен p = x 8 + x 4 + x 3 + x + 1, а a = x 6 + x 4 + x + 1 - это элемент, обратный желательно, то выполнение алгоритма приводит к вычислению, описанному в следующей таблице. Напомним, что в полях порядка 2 n выполняется - z = z и z + z = 0 для каждого элемента z в поле). Поскольку 1 - единственный ненулевой элемент GF (2), корректировка в последней строке псевдокода не требуется.
шаг | частное | г, новее | s, новости | т, тритон |
---|---|---|---|---|
р = х 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 7 + x 6 + x 3 + x , что может быть подтверждено умножением двух элементов вместе и взятием остатка на p результата.
Случай более двух чисел
Можно обрабатывать случай более двух чисел итеративно. Сначала покажем, что. Чтобы доказать это, позвольте. По определению gcd является делителем а также . Таким образом для некоторых . по аналогии является делителем так для некоторых . Позволять. По нашему построению, но с тех пор является наибольшим делителем это единица . И с тех пор результат доказан.
Так что если тогда есть а также такой, что так что окончательное уравнение будет
Итак, чтобы применить к n числам, мы используем индукцию
с уравнениями, следующими непосредственно.
Смотрите также
- Евклидова область
- Линейная теорема сравнения
- Kuṭṭaka
Рекомендации
- Кнут, Дональд . Искусство программирования . Эддисон-Уэсли. Том 2, Глава 4.
- Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Страницы 859–861 раздела 31.2: Наибольший общий делитель.
Внешние ссылки
- Источник формы алгоритма, используемого для определения мультипликативного обратного в GF (2 ^ 8)