Расширенный алгоритм евклида excel
Наибольшим общим делителем (англ. greatest common divisor) целых неотрицательных чисел \(a\) и \(b\) называется наибольшее число \(x\) , которое делит одновременно и \(a\) , и \(b\) .
Когда оба числа равны нулю, результат не определён — подойдёт сколько угодно большое число. Однако в этом случае мы положим в этом случае \(\gcd\) равным тоже нулю, чтобы можно было использовать следующее правило: если одно из чисел равно нулю, то их \(\gcd\) равен второму числу.
Алгоритм Евклида находит \(\gcd\) двух чисел \(a\) и \(b\) за \(O(\log \min(a, b))\) . Он известен ещё с IV века до нашей эры, а возможно и ранее.
Алгоритм основывается на следующей несложной формуле:
\[ \gcd(a, b) = \begin a, & b = 0 \\ \gcd(b,\, a - b), & b > 0 \end \]
Здесь предполагается, что \(a > b\) .
Докажем корректность этой формулы:
Если \(g = \gcd(a, b)\) делит и \(a\) , и \(b\) , то их разность \((a-b)\) тоже будет делиться на \(g\) .
Никакой больший делитель \(d\) числа \(b\) не может делить число \((a-b)\) : если \(d > g\) , то \(d\) не может делить \(a\) , а значит и не делит \((a - b)\) .
Прямая рекурсивная реализация:
Этот алгоритм может работать долго — например, на паре \((10^9, 1)\) он сделает миллиард итераций. Идея дальнейшей оптимизации в том, чтобы вычитать из \(a\) не одно \(b\) за раз, а столько, чтобы в следующий раз \(a\) и \(b\) уже поменялись местами — чтобы новое \(b\) стало меньше нового \(a\) .
Простой способ этого достичь — просто вычесть \(b\) из \(a\) сразу максимально возможное число раз, то есть взять вместо нового \(b\) остаток от деления \(a\) на \(b\) :
\[ \gcd(a, b) = \begin a, & b = 0 \\ \gcd(b,\, a \bmod b), & b > 0 \end \]
Можно показать, что каждые две итерации меньшее число уменьшится хотя бы в два раза, а следовательно алгоритм работает за \(O(\log \min (a, b))\) .
Чуть более быстрая итеративная форма:
В компиляторе gcc для этого уже есть встроенная функция __gcd , которая, впрочем, может непредсказуемо себя вести на отрицательных числах и \((0, 0)\) .
Время работы
Оценка \(O(\log n)\) относится к худшему случаю. Асимптотика в среднем это более интересный вопрос, играющий существенную роль в некоторых алгоритмах.
Примечательно, что худшие входные данные для алгоритма — это соседние числа Фибоначчи. На графике они видны как синие точки в пропорциях золотого сечения.
Также иногда полезно знать, что нахождение \(\gcd\) группы из \(n\) чисел от \(1\) до \(A\) будет работать не за \(O(n \log A)\) , а за \(O(n + \log A)\) — это несложно доказать по индукции.
Решение диофантовых уравнений
Для обычного использования \(gcd\) не нужно даже знать, как алгоритм устроен — он есть даже в компиляторе.
Расширенный алгоритм Евклида находит, помимо \(g = \gcd(a, b)\) , такие целые коэффициенты \(x\) и \(y\) , что
\[ a \cdot x + b \cdot y = g \]
Эта модификация алгоритма интересна, потому что с помощью неё можно искать обратный элемент по модулю: такой элемент \(a^\) , что \(a \cdot a^ \equiv 1\) , что то же самое, что найти решение в целых числах:
\[ a^ \cdot a + k \cdot m = 1 \]
Заметим также, что решений бесконечно много: можно \(x\) увеличить на \(b \cdot y\) , а \(y\) уменьшить на \(a \cdot x\) , и равенство при этом не изменится.
Алгоритм будет тоже рекурсивный. Пусть мы посчитали нужные коэффициенты \(x'\) и \(y'\) , когда рекурсивно считали \(\gcd(b, a \bmod b)\) . Иными словами, у нас есть решение \((x', y')\) для пары \((b, a \bmod b)\) :
\[ b \cdot x' + (a \bmod b) \cdot y' = g \]
Чтобы получить решение для исходной пары, запишем выражение \((a \bmod b)\) как \((a - \lfloor \frac \rfloor \cdot b)\) и подставим в приведенное выше равенство:
Теперь выполним перегруппировку слагаемых (сгруппируем по исходным \(a\) и \(b\) ) и получим:
\[ a \cdot \underbrace_x + b \cdot \underbrace<(x' - \Big \lfloor \frac \Big \rfloor \cdot y')>_y = g \]
Сравнивая это с исходным выражением, получаем, что для иходных \(x\) и \(y\) подходят коэффициенты при \(a\) и \(b\) .
Эта рекурсивная функция по прежнему возвращает значение \(\gcd(a, b)\) , но помимо этого записывает в переданные по ссылке переменные \(x\) и \(y\) искомые коэффициенты.
среди них алгоритм Евклида, решение диофантовых уравнений, нахождение числа по его остаткам.
Реализовать алгоритм на известном вам алгоритмическом языке программирования;
Решить вашу задачу вручную, на листочке бумаги.
Покажем, как можно с помощью электронных таблиц решить эти задачи и получить правильный результат за считанные минуты.
1. Методы нахождения наибольшего общего делителя (НОД) набора чисел.
1.1. Алгоритм Евклида с вычитаниями
Алгоритм Евклида позволяет находить наибольший общий делитель чисел, решать линейные уравнения в целых числах. Он применяется и для быстрого сокращения дробей (найти НОД числителя и знаменателя, затем разделить числитель и знаменатель на НОД).
Алгоритм Евклида с вычитаниями основан на следующем факте: если a>b, то НОД(a,b)=НОД(a-b,b). Теперь возьмем вместо пары чисел (a,b) пару чисел (a-b,b) и применим правило еще раз. После применения правила некоторое количество раз оба числа станут равными – это и есть НОД(a,b).
Для нескольких чисел алгоритм можно сформулировать так. Из набора натуральных чисел выбираются любые два ненулевых числа и большее из них (или любое, если они равны) заменяется разностью этих чисел. Это повторяется до тех пор, пока не останется одно ненулевое число. Оно и будет НОД исходного набора.
^ Реализация в Excel:
Для реализации этого алгоритма в Excel'е необходимо создать таблицу следующего содержания.
1. Любые две соседние ячейки отведем под исходные числа. Пусть это будут ячейки A1 и B1. Например, мы хотим найти НОД чисел 10 и 5 Внесем в них для теста числа 5 и 3, соответственно.
2. С помощью конструктора формул или «вручную» для ячейки A2 зададим формулу «=ЕСЛИ(A1>=B1;A1-B1;A1)».
3. Выделим и скопируем ячейку A2 в ячейку B2.
4. Отредактируем ячейку B2. Заменим в формуле знак больше или равно на больше, ячейку B1 - на A1, а A1 - на B1. Тогда получится: «=ЕСЛИ(B1>A1;B1-A1;B1)».
5. Выделим ячейки A2:B2. И будем копировать их несколько раз, каждый раз спускаясь на одну строку вниз, пока одно из чисел в очередной строке не станет нулем. Ненулевое число в последней строке и будет являться НОД.
1.2. Алгоритм Евклида с делением
Алгоритм Евклида с делением работает быстрее алгоритма с вычитанием. Единственный его недостаток – применение более "сложной" операции деления с остатком вместо вычитания.
Возьмем два ненулевых числа из набора, и большее из них (или любое в случае равенства) заменим остатком от деления на меньшее. Далее будем действовать так же, как и в случае 1.1.
Реализация в Excel:
1. Опять отведем любые две соседние ячейки под исходные числа. Пусть это будут ячейки D1 и E1. Внесем в них для теста числа 123 и 23, соответственно.
2. Введем в ячейку D2 формулу «=ОСТАТ(D1;E1)».
3. Выделим и скопируем ячейку D2 в ячейку E2.
4. Отредактируем ячейку E2. Поменяем местами в формуле ячейки E1 и D1. Получится «=ОСТАТ(E1;D1)».
5. Выделим D2:E2 и будем копировать до тех пор, пока в одной из ячеек не получится ноль, ненулевой элемент будет являться решением.
^ 2. Расширенный алгоритм Евклида
В качестве примера задачи решаемой при помощи расширенного алгоритма Евклида можно привести следующую. Есть несколько ведер с различными емкостями. Разрешается этими ведрами добавлять или вычерпывать воду из бочки. Сначала бочка пуста. Необходимо налить в бочку 1 литр воды, имея в распоряжении ведра емкостью 17 и 45 литров. Как это можно сделать? Как это сделать поскорее (за возможно меньшее количество переливаний)?
Идея алгоритма – в «координатном» представлении целых чисел, с которыми выполняются операции обычного алгоритма Евклида: число a представляется набором (1;0), а число b – набором (0;1). Тогда, если а при делении на b дает остаток r и частное q, то остаток в координатной форме будет вычисляться следующим образом: так как a=bq+r то r=a-bq=(1;0)-(0;1)q=(1;-q). В общем случае, если делимое имеет координаты (x1,y1), а делитель (x2,y2), то остаток будет r=(x1;y1)-q(x2;y2)=(x1-qx2;y1-qy2).
Реализация в Excel:
1. Отведем две ячейки, например A7 и A8 для коэффициентов уравнения. Столбцы B и С задействуем для решения. Например 123=1*123+0*23, следовательно B7=1, а C7=0. 23=0*123+1*23.
2. Ввести в ячейку A9 формулу «=ОСТАТ(A7;A8)».
3. Ввести в ячейку D9 формулу «=ЦЕЛОЕ(A7/A8)».
4. Ввести в ячейку B9 формулу «=B7-D9*B8».
6. Скопировать строку 9 в строку 10, затем скопировать в строку 11, и так далее, пока в первом столбце не образуется 0.
7. Смотрим в предыдущую строку, там коэффициенты 3 и -16 напротив 1. Следовательно, 1=3*123-16*23, мы получили решение.
^ 3. Нахождение числа по набору его остатков.
На практике теорема чаще всего применяется при работе с "большими" числами. Часто удобнее пользоваться не десятичным представлением "большого" числа а, так называемым, китайским кодом, который представляет из себя набор остатков от деления данного числа на числа, образующие, так называемую систему модулей. Модули должны быть взаимно просты для однозначного восстановления исходного числа по набору остатков.
При этом операция сложения "больших чисел" сводится к сложению соответствующих остатков по некоторому модулю. Операция умножения "больших чисел" – к умножению остатков по некоторому модулю. Аналогично выполняются операции вычитания и деления.
Правомерность таких операций доказывает Китайская теорема о об остатках. Она же дает метод позволяющий по получившемуся финальному набору получить ответ в привычном для нас виде.
Китайская теорема об остатках
Постановка задачи: есть набор остатков от деления неизвестного нам числа на числа из системы взаимно-простых модулей. Надо найти неизвестное число.
Для примера возьмем взаимно простые модули . Пусть остатки от деления на данные модули будут соответственно . Создадим таблицу, вид которой приведен на рис. 1:
В номере 6 за 2001 год в статье С.С.Лаврова «Цепные дроби» описаны алгоритмы работы с цепными дробями. Всех их также можно реализовать с помощью Excel. Попробуйте! Желаем удачи!
Алгоритм Евклида используются для нахождения по заданным целым числам A и B их наибольшего общего делителя С=НОД(А; B). Расширенный алгоритм Евклида используется также для нахождения целых чисел x, y таких, что выполняется условие . Используется во многих криптографических конструкциях, в том числе в методе RSA.
Основным равенством, используемым для вычисления НОД чисел А и В, является условие
НОД(А, В) = НОД( В, A mod B) (3)
где A mod B – остаток от целочисленного деления А на В. Применяя последовательно формулу (3), мы будем уменьшать числа А и В в этом алгоритме, пока A mod B не станет равным 0, тогда последнее значение аргумента В даст искомый НОД (А, В). Полное описание расширенного алгоритма мы объясним на примере. Пусть числа А и В равны 172 и 38 соответственно. Откроем рабочий лист Excel и разметим в первых строчках заголовки столбцов, а под заголовками А и В поместим числа 172 и 38, как указано на рисунке.
Рис.1. Примерный вид рабочего листа Excel для реализации расширенного алгоритма Евклида.
В столбце Amod B напишем формулу вычисления остатка от целочисленного деления А на В: =ОСТАТ(A3;B3), а в столбце A div B впишем формулу =ЦЕЛОЕ(A3/B3), обозначающую операцию нахождения целой части от деления A на В.
В следующей строке в столбах А и В поместим значения 38 и 20, взятые из двух ячеек, находящихся выше и правее (применение формулы (3)). Значения ячеек под заголовками Amod B и A div B надо вычислить как в предыдущей строке. В Excel для этого достаточно просто скопировать и вставить вышележащие клетки на строку ниже.
Повторяем эти операция несколько раз, пока не получим в столбце Amod B значение 0. Значение В в этой строке будет равно НОД(А,В) (в нашем примере он равен 2).
Далее заполняем столбцы x и y в обратном порядке снизу вверх. Поместим в столбцы x и y в последней полученной строке значения 0 и 1. Далее в каждой следующей (вышележащей) строке i поместим значения xi и yi, вычисленные по формулам:
где обозначает значение из столбца A div B, взятое из той же строки, где вычисляются значения x и y. Используя эти формулы, заполним столбцы x и y. В верхней строке получим значения x и y, которые нам нужны.
Алгоритм возведения в степень по модулю натурального числа.
Для выполнения шифрования по методу RSA приходится выполнять возведение в большую степень различных чисел, а результат приводить по модулю числа N, являющегося параметром метода и имеющего длину 512 и более бит. Уже для небольших a и e вычислить значение
выполняя сначала возведение в степень, а потом вычисляя остаток от деления на N, становится невозможным. Между тем, если применить алгоритм, описанный в этом разделе, можно вычислять выражения (1), для достаточно больших чисел a, e, N, оставаясь в рамках обычных операций с целыми числами, заложенных в компьютере.
Алгоритм быстрого возведения в степень основывается на идее замены прямого вычисления возведения в степень последовательными операциями умножения на a и возведения в квадрат. Для этого представим степень e число в двоичном исчислении
где любое ti для принадлежит , . Зная вектор разрядов , можно вычислить число e, применяя последовательные вычисления:
Например, если e = 13, то в двоичном представлении e = 11012 , и 13 можно представить как результат вычисления , .
Последнее число и есть e.
Используя формулы (3), можно процедуру возведения в степень по модулю натурального числа N, записать в виде последовательности итераций:
где . Множитель в зависимости от принимает либо значение a, если , либо 1, если . Результат вычислений можно свести в таблицу
Положить r0 ← a, r1← b, i ← 1.
Найти остаток ri+1 от деления ri-1 на ri.
Если ri+1=0, то положить d←ri. В противном случае положить i ← i + 1 и вернуться на шаг 2.
Результат: d.
Сложность алгоритма Евклида равна O(log 2 a)
Для доказательства корректности алгоритма Евклида нам понадобятся две леммы.
Лемма 1.5. Если числа а и b целые и а делится на b, то b=НОД(а, b).
Доказательство. Пусть d= НОД(а, b), тогда по теореме 1.4 существуют такие целые числа т,n, что d = ma + nb. Поскольку, а делится на b, то сумма в правой части равенства делится на b, а значит и d делится на b. В то же время b делится на d как на наибольший общий делитель. Таким образом, числа d и b ассоциированы и равны с точностью до знака. □
Лемма 1.6. Для любых целых чисел а, b, с выполняется равенство НОД(а + cb, b) = НОД(а, b).
Доказательство. Пусть d=НОД(а, b). Тогда а делится на d, b делится на d, значит, по свойству 2 делимости, и сумма а + cb делится на d, то есть d — общий делитель чисел а + cb и b.
Пусть d1 — произвольный общий делитель чисел а + cb и b. Тогда число а = (а + cb) - cb делится на d1, то есть d1 — общий делитель чисел а и b. А так как делитель d наибольший, то d делится на d1, и d— наибольший общий делитель чисел а + cb и b. □
Теорема 1.7. Для любых a, b > 0 алгоритм Евклида останавливается и выдаваемое им число d является наибольшим общим делителем чисел а и b.
Доказательство. По теореме о делении с остатком для любого i ≥ 1 имеем ri-1=qiri+ri+1, где 0≤ri+1ri. Получаем монотонно убывающую последовательность неотрицательных целых чисел r1> r2> r3>. ≥0, ограниченную снизу. Такая последовательность не может быть бесконечной, следовательно, алгоритм Евклида останавливается.
Докажем теперь, что число d — наибольший общий делитель для чисел r1, r2. rk, где rk-1 делится на rk. С учетом леммы 1.6 можем записать:
НОД(а, b) =НОД(r0, r1) = НОД(q1 r1+ r2, r1) = НОД(r1, r2) = =НОД(r2,r3) = …=НОД(rk-1, rk).
А по лемме 1.5 получаем НОД(rk-1, rk) = rk = d.
Алгоритм 1.2. Бинарный алгоритм Евклида .
Этот вариант алгоритма Евклида оказывается боле быстрым при реализации на компьютере, поскольку использует двоичное представление чисел a и b. Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0b≤a):
Если оба числа a и b четные, то НОД(a,b)=2*НОД(,);
Если число a нечетное, число b четное, то НОД(a,b)= НОД(a,);
Если оба числа a и b нечетные, a>b, то НОД(a,b)= НОД(a-b,b);
Если a=b, то НОД(a, b)=a.
Бинарный алгоритм Евклида:
Выход. d=НОД(а, b).
Положить g ←1.
Пока оба числа а и b четные, выполнять a← , b←,g←2g до
получения хотя бы одного нечетного значения а или b.
Положить u ←a,v← b.
Пока u ≠0, выполнять следующие действия.
Пока и четное, полагать и ←
Пока v четное, полагать v←
При u≥v положить u ← u-v. В противном случае положить
v ← v-u.
Положить d←gv.
Результат: d.
Сложность этого алгоритма равна O(log 2 a).
Алгоритм 1.3. Расширенный алгоритм Евклида.
Выход. d=НОД(a, b); такие целые числа х,у, что ах + by=d.
Положить r0 ←a, r1 ←b , x0 ←1, x1 ←0, y0 ←0, y1 ←1, i ←1.
Если ri+1 = 0, то положить d ← ri, x ← xi , y ← yi. В противном случае положить xi+1← xi-1-qixi, yi+1← yi-1- qiyi , i ← i+1 и вернуться на шаг 2.
Результат: d, х, у. □
Сложность этого алгоритма равна O(log 2 a).
Алгоритм 1.4. Расширенный бинарный алгоритм Евклида
Выход, d =НОД(а, b); такие целые числа х, у, что ах + by = d.
Положить g ←1.
Пока оба числа а и b четные, выполнять a← , b←,g←2g до получения хотя бы одного нечетного значения а или b.
Положить u ←a,v← b, A ←1,B← 0, C ←0,D← 1.
Пока u ≠0, выполнять следующие действия.
4.1. Пока u четное:
Положить и ←
Если оба числа А и В четные, то положить A←, B←
В противном случае положить A← , B←
4.2. Пока v четное:
4.2.1. Положить v←
4.2.2. Если оба числа С и D четные, то положить C←, D←, В противном случае положить C← , D←
4.3. При u≥v положить u ←u-v, A ←A-C, B ←B-D. В противном случае положить v←v-u, С←C-A,D←D-B.
Положить d←gv, х ← С, у ← D.
В арифметическом и компьютерном программировании , то расширенный алгоритм Евклида является расширение для алгоритма Евклида и вычисляет, в дополнении к наибольшему общему делителю (GCD) целым числа через и Ь , также коэффициенты идентичности Беза , которые являются целыми числами х и у такой, что
а Икс + б y знак равно gcd ( а , б ) .
Это сертификационный алгоритм , потому что gcd - единственное число, которое может одновременно удовлетворять этому уравнению и разделять входные данные. Это позволяет также вычислить, почти без дополнительных затрат, частное чисел a и b на их наибольший общий делитель.
Расширенный алгоритм Евклида также относится к очень похожему алгоритму для вычисления наибольшего общего делителя многочлена и коэффициентов тождества Безу двух одномерных многочленов .
Расширенный алгоритм Евклида является особенно полезным , когда и б являются взаимно простыми . С этим положением, х представляет собой модульное мультипликативное обратное из в по модулю Ь , и у является модульным мультипликативным обратным Ь по модулю . Аналогично, полиномиальный расширенный алгоритм Евклида позволяет вычислять мультипликативную обратную функцию в расширениях алгебраических полей и, в частности, в конечных полях непростого порядка. Отсюда следует, что оба расширенных алгоритма Евклида широко используются в криптографии. . В частности, вычисление модульного обратного мультипликативного числа является важным шагом в получении пар ключей в методе шифрования с открытым ключом RSA .
СОДЕРЖАНИЕ
Стандартный алгоритм Евклида использует последовательность евклидовых делений , частные которых не используются. Сохраняются только остатки . Для расширенного алгоритма используются последовательные частные. Точнее, стандартный алгоритм Евклида с a и b в качестве входных данных состоит из вычисления последовательности частных и последовательности остатков, таких что q 1 , … , q k , \ ldots, q_ > р 0 , … , р k + 1 , \ ldots, r_ >
Вычисление останавливается, когда достигается остаток, равный нулю; тогда наибольший общий делитель - это последний ненулевой остаток r k + 1 > r k . .>
Расширенный алгоритм Евклида действует аналогично, но добавляет две другие последовательности, как показано ниже.
Вычисление также останавливается, когда и дает r k + 1 = 0 =0>
Более того, если a и b положительны и , то gcd ( a , b ) ≠ min ( a , b )
для где обозначает целую часть от х , то есть наибольшее целое число , не большее , чем х . 0 ≤ i ≤ k , ⌊ x ⌋
Это означает, что пара коэффициентов Безу, предоставляемая расширенным алгоритмом Евклида, является минимальной парой коэффициентов Безу, поскольку это единственная пара, удовлетворяющая обоим вышеупомянутым неравенствам.
Кроме того, это означает , что алгоритм может быть сделано без целочисленного переполнения с помощью компьютерной программы с использованием целых чисел фиксированного размера , который больше , чем у и б .
В следующей таблице показано, как расширенный алгоритм Евклида работает с входными данными 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 и далее). Таким образом, он должен остановиться на некотором. Это доказывает, что алгоритм в конечном итоге останавливается. 0 ≤ r i + 1 < | r i | , <|r_|,> r i > r k + 1 = 0. =0.>
Поскольку наибольший общий делитель одинаков для и Это показывает, что наибольший общий делитель входных данных совпадает с делителем. Это доказывает, что это наибольший общий делитель a и b . (До этого момента доказательство такое же, как у классического алгоритма Евклида.) r i + 1 = r i − 1 − r i q i , =r_-r_q_,> ( r i − 1 , r i ) <\displaystyle (r_,r_)> ( r i , r i + 1 ) . ,r_).> a = r 0 , b = r 1 ,b=r_> r k , r k + 1 = 0. ,r_=0.> r k >
r i + 1 = r i − 1 − r i q i = ( a s i − 1 + b t i − 1 ) − ( a s i + b t i ) q i = ( a s i − 1 − a s i q i ) + ( b t i − 1 − b t i q i ) = a s i + 1 + b t i + 1 . =r_-r_q_=(as_+bt_)-(as_+bt_)q_=(as_-as_q_)+(bt_-bt_q_)=as_+bt_.>
Таким образом, и являются коэффициентами Безу. s k > t k >
Рекуррентное соотношение можно переписать в матричном виде
Матрица является единичной матрицей, а ее определитель равен единице. Определитель самой правой матрицы в предыдущей формуле равен −1. Отсюда следует , что определитель является , в частности, для нас Просмотр это как идентичности Безу, это показывает , что и являются взаимно простыми . Доказанное выше соотношение и лемма Евклида показывают, что делит b и делит a . Поскольку они взаимно просты, они до своего знака являются частными b и a по их наибольшему общему делителю. A 1 > A i > ( − 1 ) i − 1 . .> i = k + 1 , s k t k + 1 − t k s k + 1 = ( − 1 ) k . t_-t_s_=(-1)^.> s k + 1 <\displaystyle s_> t k + 1 <\displaystyle t_> a s k + 1 + b t k + 1 = 0 <\displaystyle as_+bt_=0> s k + 1 <\displaystyle s_> t k + 1 <\displaystyle t_>
Чтобы доказать последнее утверждение, предположим, что a и b положительны и . Тогда, и если , можно увидеть, что последовательности s и t для ( a , b ) в рамках EEA являются последовательностями t и s для ( b , a ) с точностью до начальных нулей и единиц . Затем определения показывают, что случай ( a , b ) сводится к случаю ( b , a ). Итак, предположим, что без потери общности. gcd ( a , b ) ≠ min ( a , b ) a ≠ b a < b a > b b>
Видно, что это 1 и (который существует ) является отрицательным целым числом. После этого знаки меняются по знаку и строго возрастают по величине, что индуктивно следует из определений и того факта, что для , случай имеет место, потому что . То же самое и после первых нескольких сроков по той же причине. Кроме того, легко увидеть, что (когда a и b положительны и ). Таким образом, s 2 > s 3 > gcd ( a , b ) ≠ min ( a , b ) s i > q i ≥ 1 \geq 1> 1 ≤ i ≤ k i = 1 a > b b> t i > q k ≥ 2 \geq 2> gcd ( a , b ) ≠ min ( a , b )
Это сопровождается тем фактом, что они больше или равны по абсолютной величине, чем любые предыдущие или, соответственно, завершенные доказательства. s k , t k ,t_> s i > t i >
Для одномерных многочленов с коэффициентами в поле все работает аналогично: евклидово деление, тождество Безу и расширенный алгоритм Евклида. Первое отличие состоит в том, что в евклидовом делении и алгоритме неравенство должно быть заменено неравенством по степеням. В противном случае все, что предшествует в этой статье, остается прежним, просто заменяя целые числа полиномами. 0 ≤ r i + 1 < | r i | <|r_|> deg r i + 1 < deg r i . .>
Второе отличие заключается в ограничении размера коэффициентов Безу, обеспечиваемом расширенным алгоритмом Евклида, который более точен в полиномиальном случае, что приводит к следующей теореме.
Если a и b - два ненулевых многочлена, то расширенный алгоритм Евклида производит уникальную пару многочленов ( s , t ) такую, что
a s + b t = gcd ( a , b )
deg s < deg b − deg ( gcd ( a , b ) ) , deg t < deg a − deg ( gcd ( a , b ) ) .
Третье отличие состоит в том, что в полиномиальном случае наибольший общий делитель определяется только с точностью до умножения на ненулевую константу. Существует несколько способов однозначного определения наибольшего общего делителя.
В математике принято требовать, чтобы наибольший общий делитель был моническим многочленом . Для того, чтобы получить это, достаточно разделить каждый элемент на выходе по ведущим коэффициентом в этом допускает , что, если и б взаимно просты, один получает 1 в правой части неравенства Безу. В противном случае можно получить любую ненулевую константу. В компьютерной алгебре многочлены обычно имеют целые коэффициенты, и этот способ нормализации наибольшего общего делителя вводит слишком много дробей, чтобы быть удобным. r k . .>
Второй способ нормализовать наибольший общий делитель в случае многочленов с коэффициентами целых чисел , чтобы разделить каждый выход на содержание из , чтобы получить примитивный наибольший общий делитель. Если входные полиномы взаимно просты, эта нормализация также обеспечивает наибольший общий делитель, равный 1. Недостатком этого подхода является то, что во время вычислений необходимо вычислять и упрощать множество дробей. r k , ,>
Третий подход заключается в расширении алгоритма подрезультатных последовательностей псевдоостаточных остатков способом, аналогичным расширению алгоритма Евклида на расширенный алгоритм Евклида. Это позволяет, начиная с полиномов с целыми коэффициентами, все вычисляемые многочлены имеют целые коэффициенты. Более того, каждый вычисленный остаток является подрезультатным многочленом . В частности, если входные многочлены взаимно просты, то тождество Безу становится r i >
где обозначает равнодействующую из и б . В этой форме тождества Безу в формуле нет знаменателя. Если все разделить на результат, получится классическая тождество Безу с явным общим знаменателем для рациональных чисел, которые в нем фигурируют. Res ( a , b ) (a,b)>
Для реализации описанного выше алгоритма следует сначала заметить, что на каждом шаге нужны только два последних значения индексированных переменных. Таким образом, для экономии памяти каждая индексированная переменная должна быть заменена всего двумя переменными.
Для простоты в следующем алгоритме (и других алгоритмах в этой статье) используются параллельные назначения . В языке программирования, не имеющем этой функции, параллельные присвоения необходимо моделировать с помощью вспомогательной переменной. Например, первый,
и аналогично для других параллельных заданий. Это приводит к следующему коду:
Наконец, обратите внимание, что в личности Безу, можно решить для данного . Таким образом, оптимизация вышеуказанного алгоритма заключается в вычислении только последовательности (которая дает коэффициент Безу ), а затем вычислении в конце: a x + b y = gcd ( a , b ) y a , b , x , gcd ( a , b ) s k > x y
Однако во многих случаях это не совсем оптимизация: в то время как первый алгоритм не подвержен переполнению при использовании с машинными целыми числами (то есть целыми числами с фиксированной верхней границей цифр), умножение old_s * a при вычислении bezout_t может переполняться, ограничивая эту оптимизацию входными данными, которые могут быть представлены в менее чем половине максимального размера. При использовании целых чисел неограниченного размера время, необходимое для умножения и деления, увеличивается квадратично с размером целых чисел. Это означает, что «оптимизация» заменяет последовательность умножений / делений малых целых чисел на одно умножение / деление, что требует больше вычислительного времени, чем операции, которые она заменяет вместе взятые.
Фракция а / б в канонической форме , если упрощенной и Ь являются взаимно простыми , и б положительна. Эту каноническую упрощенную форму можно получить, заменив три выходные строки предыдущего псевдокода на
Доказательство этого алгоритма основывается на том факте, что s и t - два взаимно простых целых числа, таких что as + bt = 0 , и, следовательно . Чтобы получить каноническую упрощенную форму, достаточно переместить знак минус, чтобы знаменатель был положительным. a b = − t s >=->>
Если b делит a равномерно, алгоритм выполняет только одну итерацию, и в конце алгоритма s = 1 . Это единственный случай, когда результат является целым числом.
Расширенный алгоритм Евклида является важным инструментом для вычисления мультипликативных инверсий в модульных структурах, обычно модульных целых числах и расширениях алгебраических полей . Ярким примером последнего случая являются конечные поля непростого порядка.
Если n - положительное целое число, кольцо Z / n Z может быть отождествлено с набором n -1> остатков евклидова деления на n , сложение и умножение, состоящее в взятии остаток на n от результата сложения и умножения целых чисел. Элемент a из Z / n Z имеет мультипликативный обратный (то есть, это единица ), если он взаимно прост с n . В частности, если п является главным , a имеет мультипликативную обратную, если она не равна нулю (по модулю n ). Таким образом, Z / n Z является полем тогда и только тогда, когда n простое.
Тождество Безу утверждает, что a и n взаимно просты тогда и только тогда, когда существуют целые числа s и t такие, что
Сокращение этого тождества по модулю n дает
Таким образом , т , или, точнее, остаток от деления т на п , является мультипликативным обратным к модулю п .
Чтобы адаптировать расширенный алгоритм Евклида к этой проблеме, следует отметить, что коэффициент Безу для n не требуется и, следовательно, его не нужно вычислять. Кроме того, для получения положительного результата, меньшего чем n , можно использовать тот факт, что целое число t, предоставленное алгоритмом, удовлетворяет | т | < п . То есть, если t n . Это приводит к псевдокоду, в котором входное n является целым числом больше 1.
Расширенный алгоритм Евклида также является основным инструментом для вычисления мультипликативных инверсий в простых расширениях алгебраических полей . Важным случаем, широко используемым в криптографии и теории кодирования , является случай конечных полей непростого порядка. Фактически, если p - простое число и q = p d , поле порядка q является простым алгебраическим расширением простого поля из p элементов, порожденным корнем неприводимого многочлена степени d .
Простое алгебраическое расширение L поля K , порожденное корнем неприводимого многочлена p степени d, можно отождествить с фактор-кольцом , и его элементы находятся в биективном соответствии с многочленами степени меньше d . Сложение в L - это сложение многочленов. Умножение в L - это остаток от евклидова деления произведения многочленов на p . Таким образом, чтобы завершить арифметику в L K [ X ] / ⟨ p ⟩ , , осталось только определить, как вычислять мультипликативные обратные. Это делается с помощью расширенного алгоритма Евклида.
Алгоритм очень похож на приведенный выше для вычисления модульного мультипликативного обратного. Есть два основных отличия: во-первых, предпоследняя линия не нужна, потому что коэффициент Безу, который предоставляется, всегда имеет степень меньше d . Во-вторых, наибольший общий делитель, который предоставляется, когда входные многочлены взаимно просты, может быть любыми ненулевыми элементами K ; этот коэффициент Безу (полином как правило , положительной степени) имеет , таким образом , необходимо умножить на величину , обратную этому элементу K . В следующем псевдокоде p - многочлен степени больше единицы, а a - многочлен. Кроме того, div - вспомогательная функция, вычисляющая частное евклидова деления.
Например, если многочлен, используемый для определения конечного поля 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), корректировка в последней строке псевдокода не требуется.
Таким образом, обратное значение равно x 7 + x 6 + x 3 + x , что может быть подтверждено умножением двух элементов вместе и взятием остатка на p результата.
x ( n a + m b ) + y c = ( x n ) a + ( x m ) b + y c = gcd ( a , b , c ) .
Читайте также: