Расширенный алгоритм Евклида - Extended Euclidean algorithm - Wikipedia

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

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

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

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

Описание

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

Это главное свойство Евклидово деление что неравенства справа однозначно определяют и из и

Вычисление останавливается, когда достигается остаток который равен нулю; наибольший общий делитель - это последний ненулевой остаток

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

Вычисление также останавливается, когда и дает

  • является наибольшим общим делителем входа и
  • Коэффициенты Безу равны и то есть
  • Частные а и б по их наибольшему общему делителю даются и

Более того, если а и б оба положительные и , тогда

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

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

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

Пример

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

индекс ячастное qя−1Остаток ряsятя
024010
14601
2240 ÷ 46 = 52405 × 46 = 1015 × 0 = 10 − 5 × 1 = −5
346 ÷ 10 = 4464 × 10 = 604 × 1 = −41 − 4 × −5 = 21
410 ÷ 6 = 1101 × 6 = 411 × −4 = 5−5 − 1 × 21 = −26
56 ÷ 4 = 161 × 4 = 2−41 × 5 = −921 − 1 × −26 = 47
64 ÷ 2 = 242 × 2 = 052 × −9 = 23−26 − 2 × 47 = −120

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

В качестве последовательность убывающая последовательность неотрицательных целых чисел (от я = 2 на). Таким образом, он должен остановиться на некоторых Это доказывает, что алгоритм в конечном итоге останавливается.

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

В качестве и у нас есть за я = 0 и 1. Соотношение следует по индукции для всех :

Таким образом и - коэффициенты Безу.

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

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

Матрица - единичная матрица, и ее определитель равен единице. Определитель самой правой матрицы в предыдущей формуле равен −1. Отсюда следует, что определитель является В частности, для у нас есть Если рассматривать это как личность Безу, это показывает, что и находятся совмещать. Соотношение что было доказано выше и Лемма евклида показывает, что разделяет б и разделяет а. Поскольку они взаимно просты, они до своего знака являются частными от б и а по их наибольшему общему делителю.

Для доказательства последнего утверждения предположим, что а и б оба положительные и . Потом, , и если , видно, что s и т последовательности для (а,б) в соответствии с EEA, с точностью до начальных нулей и единиц, т и s последовательности для (б,а). Затем определения показывают, что (а,б) случай сводится к (б,а) дело. Итак, предположим, что не теряя общий смысл.

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

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

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

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

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

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

и

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

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

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

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

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

Псевдокод

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

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

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

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

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

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

функция Extended_gcd (a, b) (old_r, r): = (a, b) (old_s, s): = (1, 0) (old_t, t): = (0, 1) пока г ≠ 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) выход «Коэффициенты Безу:», (old_s, old_t) выход "наибольший общий делитель:", old_r выход "частные по НОД:", (t, s)

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

Наконец, обратите внимание, что в личности Безу , можно решить для данный . Таким образом, оптимизация вышеуказанного алгоритма заключается в вычислении только последовательность (которая дает коэффициент Безу ), а затем вычислить в конце:

функция extended_gcd (a, b) s: = 0; old_s: = 1 r: = b; old_r: = a пока г ≠ 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 * а в расчете bezout_t может переполняться, ограничивая эту оптимизацию входными данными, которые могут быть представлены в менее чем половине максимального размера. При использовании целых чисел неограниченного размера время, необходимое для умножения и деления, увеличивается квадратично с размером целых чисел. Это означает, что «оптимизация» заменяет последовательность умножений / делений малых целых чисел на единичное умножение / деление, что требует больше вычислительного времени, чем операции, которые она заменяет вместе взятые.

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

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

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

Доказательство этого алгоритма основано на том, что s и т два взаимно простых целых числа такие, что в качестве + bt = 0, и поэтому . Чтобы получить каноническую упрощенную форму, достаточно переместить знак минус, чтобы знаменатель был положительным.

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

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

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

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

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

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

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

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

Чтобы адаптировать расширенный алгоритм Евклида к этой проблеме, следует отметить, что коэффициент Безу п не требуется, и, следовательно, в вычислении не требуется. Также для получения положительного результата ниже п, можно использовать тот факт, что целое число т предоставленный алгоритмом удовлетворяет |т| < п. То есть, если т < 0, нужно добавить п к нему в конце. В результате получается псевдокод, в котором ввод п целое число больше 1.

 функция обратный (a, n) t: = 0; тритон: = 1 r: = n; новее: = а пока новинка ≠ 0 делать        частное: = r div newr (t, newt): = (newt, t - частное × newr) (r, newr): = (newr, r - частное × newr) если г> 1 тогда        возвращаться "а не обратимо" если т <0 тогда        т: = т + п возвращаться т

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

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

Простое алгебраическое расширение L поля K, порожденный корнем неприводимого многочлена п степени d можно отнести к кольцо частного , а его элементы находятся в биективное соответствие с многочленами степени меньше d. Добавление в L является сложением многочленов. Умножение в L это остаток от Евклидово деление к п произведения многочленов. Таким образом, чтобы завершить арифметику в L, осталось только определить, как вычислять мультипликативные обратные. Это делается с помощью расширенного алгоритма Евклида.

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

функция inverse (a, p) t: = 0; тритон: = 1 r: = p; новее: = а пока новинка ≠ 0 делать        частное: = r div newr (r, newr): = (newr, r - частное × newr) (t, newt): = (newt, t - частное × newt) если степень (г)> 0 тогда         возвращаться «Либо p не является неприводимым, либо a кратно p» возвращаться (1 / г) × т

Пример

Например, если многочлен, используемый для определения конечного поля GF (28) является п = Икс8 + Икс4 + Икс3 + Икс + 1, и а = Икс6 + Икс4 + Икс + 1 - это элемент, для которого требуется инверсия, тогда выполнение алгоритма приводит к вычислению, описанному в следующей таблице. Напомним, что в полях порядка 2п, надо -z = z и z + z = 0 для каждого элемента z в поле). Поскольку 1 - единственный ненулевой элемент GF (2), корректировка в последней строке псевдокода не требуется.

шаг частноег, новееs, новостит, тритон
  п = Икс8 + Икс4 + Икс3 + Икс + 1 1 0
  а = Икс6 + Икс4 + Икс + 10 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 (x4+ х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) 

Таким образом, обратное Икс7 + Икс6 + Икс3 + Икс, что подтверждается умножение двух элементов вместе, а остаток на п результата.

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

Можно обрабатывать случай более двух чисел итеративно. Сначала покажем, что . Чтобы доказать это, позвольте . По определению gcd является делителем и . Таким образом для некоторых . по аналогии является делителем так для некоторых . Позволять . По нашему построению , но с тех пор является наибольшим делителем это единица измерения. И с тех пор результат доказан.

Так что если тогда есть и такой, что так что окончательное уравнение будет

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

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

Смотрите также

Рекомендации

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

внешняя ссылка