Меню Главная Случайная статья Настройки Алгоритм Евклида Материал из https://ru.wikipedia.org Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII[1] и X[2] книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время[3]. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и остатка от деления большего числа на меньшее. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида был обобщён на другие математические структуры, такие как узлы и многомерные полиномы. Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA[4], широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений[5], при построении непрерывных дробей[6], в методе Штурма[7]. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов[8] и основная теорема арифметики[9]. Содержание 1 История 2 Описание 2.1 Алгоритм Евклида для целых чисел 2.2 Геометрический алгоритм Евклида 2.3 Пример 3 Применения 3.1 Расширенный алгоритм Евклида и соотношение Безу 3.2 Цепные дроби 3.3 Линейные диофантовы уравнения 4 Вариации и обобщения 4.1 Евклидово кольцо 4.2 Обобщённый алгоритм Евклида для многочленов 4.3 Ускоренные версии алгоритма 5 Вычислительная сложность алгоритма 5.1 Количество шагов 5.2 Наихудший случай 5.2.1 Теорема Ламе 5.3 Среднее 5.4 Вычислительная сложность шага 6 Примечания 7 Литература 8 Ссылки История Древнегреческие математики называли этот алгоритм или  — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля (IV век до н. э.)[3]. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел[1] и в X книге для нахождения наибольшей общей меры двух однородных величин[2]. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков. Историками математики было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника)[10]. Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах. Описание Алгоритм Евклида для целых чисел Пусть ${\displaystyle a}$ и ${\displaystyle b}$ — целые числа, не равные одновременно нулю, и последовательность чисел ${\displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}>\dots >r_{n}}$ определена тем, что каждое ${\displaystyle r_{k}}$ — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть: ${\displaystyle a=bq_{0}+r_{1},}$ ${\displaystyle b=r_{1}q_{1}+r_{2},}$ ${\displaystyle r_{1}=r_{2}q_{2}+r_{3},}$ ${\displaystyle \cdots }$ ${\displaystyle r_{k-2}=r_{k-1}q_{k-1}+r_{k},}$ ${\displaystyle \cdots }$ ${\displaystyle r_{n-2}=r_{n-1}q_{n-1}+r_{n},}$ ${\displaystyle r_{n-1}=r_{n}q_{n}.}$ Тогда ${\displaystyle {\text{НОД}}(a,b)}$, наибольший общий делитель ${\displaystyle a}$ и ${\displaystyle b}$, равен ${\displaystyle r_{n}}$, последнему ненулевому члену этой последовательности[11]. Существование таких ${\displaystyle r_{1},r_{2},...,r_{n}}$, то есть возможность деления с остатком ${\displaystyle m}$ на ${\displaystyle n}$ для любого целого ${\displaystyle m}$ и целого ненулевого ${\displaystyle n}$, доказывается индукцией по ${\displaystyle m}$. Корректность алгоритма вытекает из следующих двух утверждений[12]: I. Пусть ${\displaystyle a=bq+r}$, тогда ${\displaystyle {\text{НОД}}(a,b)={\text{НОД}}(b,r).}$ Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда a = t1k и b = t2k, где t1 и t2 — целые числа из определения. Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а ${\displaystyle r=a-b\cdot q=(t_{1}-t_{2}\cdot q)\cdot k}$ (выражение в скобках есть целое число, следовательно, k делит r без остатка). Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b. Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот. В частности, наибольший общий делитель остаётся тем же самым, так как в предположении, что НОД (a, b) > НОД (b, r) или НОД (a, b) < НОД (b, r) получаются противоречия, следовательно, НОД (a, b) = НОД (b, r). Что и требовалось доказать. II. ${\displaystyle {\text{НОД}}(r,0)=r}$ для любого ненулевого ${\displaystyle r}$ (так как 0 делится на любое целое число). Геометрический алгоритм Евклида Пусть даны два отрезка длины ${\displaystyle a}$ и ${\displaystyle b}$. Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, вычитая из большего отрезка меньший, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан Евклидом[2] и реализуется с помощью циркуля и линейки. Пример Для иллюстрации алгоритм Евклида будет использован, чтобы найти ${\displaystyle {\text{НОД}}}$ ${\displaystyle a=1071}$ и ${\displaystyle b=462}$. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (${\displaystyle q_{0}=2}$), оставаясь с остатком 147: ${\displaystyle 1071=2\cdot 462+147.}$ Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (${\displaystyle q_{1}=3}$), оставаясь с остатком 21: ${\displaystyle 462=3\cdot 147+21.}$ Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (${\displaystyle q_{2}=7}$), оставаясь без остатка: ${\displaystyle 147=7\cdot 21+0.}$ Таким образом последовательность ${\displaystyle a>b>r_{1}>r_{2}>r_{3}>\dots >r_{n}}$ в данном конкретном случае будет выглядеть так: ${\displaystyle 1071>462>147>21.}$ Так как последний остаток равен нулю, то алгоритм заканчивается числом 21 и ${\displaystyle {\text{НОД}}(1071,462)=21.}$ В табличной форме шаги были следующие: Шаг k Равенство Частное и остаток 0 1071 = q0 462 + r0 q0 = 2 и r0 = 147 1 462 = q1 147 + r1 q1 = 3 и r1 = 21 2 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм заканчивается Если требуется найти ${\displaystyle {\text{НОД}}}$ для более чем двух чисел, алгоритм аналогичен, на каждом шаге все числа, кроме наименьшего, заменяются остатками по модулю наименьшего. Нулевые остатки, если получатся, вычёркиваются. Алгоритм завершается, когда остаётся одно ненулевое число, это и есть ${\displaystyle {\text{НОД}}}$. Применения Расширенный алгоритм Евклида и соотношение Безу Формулы для ${\displaystyle r_{i}}$ могут быть переписаны следующим образом: ${\displaystyle r_{1}=a+b(-q_{0})}$ ${\displaystyle r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})}$ ${\displaystyle ...}$ ${\displaystyle {\text{НОД}}(a,b)=r_{n}=as+bt}$ Здесь ${\displaystyle s}$ и ${\displaystyle t}$ целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа ${\displaystyle s}$ и ${\displaystyle t}$ — коэффициентами Безу[13]. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики. Цепные дроби Алгоритм Евклида достаточно тесно связан с цепными дробями[6]. Отношение ${\displaystyle {\frac {a}{b}}}$ допускает представление в виде цепной дроби: ${\displaystyle {\frac {a}{b}}=[q_{0};q_{1},q_{2},\cdots ,q_{n}]}$. При этом цепная дробь без последнего члена равна отношению коэффициентов Безу ${\displaystyle {\frac {t}{s}}}$, взятому со знаком минус ${\displaystyle [q_{0};q_{1},q_{2},\cdots ,q_{n-1}]=-{\frac {t}{s}}}$. Последовательность равенств, задающая алгоритм Евклида, может быть переписана в форме: ${\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&{}\ \vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&{}\ \vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\end{aligned}}}$ Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме: ${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}}$ Третье равенство может быть использовано, чтобы заменить знаменатель выражения ${\displaystyle {\frac {r_{1}}{r_{0}}}}$, получим: ${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}}$ Последнее отношение остатков ${\displaystyle {\frac {r_{k}}{r_{k-1}}}}$ всегда может быть заменено с использованием следующего равенства в последовательности, и так до последнего уравнения. Результатом является цепная дробь: ${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]}$ В приведённом выше примере ${\displaystyle {\text{НОД}}(1071,462)}$ был посчитан и были найдены частные ${\displaystyle q_{k}}$, равные 2, 3 и 7 соответственно. Поэтому ${\displaystyle {\frac {1071}{462}}}$ может быть записана как: ${\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3;7]}$ Линейные диофантовы уравнения Диофантово уравнение — это уравнение с целочисленными коэффициентами и с одним или несколькими переменными, причём ставится задача поиска лишь его целых корней. Такое уравнение может иметь бесконечно много решений, конечное число решений или не иметь их вовсе. Простейшее диофантово уравнение — линейное с двумя неизвестными: ${\displaystyle ax+by=c,}$ где ${\displaystyle a,b,c}$ — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типа[5]. Сначала с помощью этого алгоритма можно определить ${\displaystyle d={\text{НОД}}(a,b).}$ Затем, используя расширенный алгоритм Евклида, определяются такие ${\displaystyle k}$ и ${\displaystyle l}$, что: ${\displaystyle ak+bl=d.}$ То есть ${\displaystyle x=k}$ и ${\displaystyle y=l}$ — это частное решение уравнения при ${\displaystyle c=d}$. Получается, что если ${\displaystyle c=qd}$, то ${\displaystyle x=qk}$, ${\displaystyle y=ql}$ — частное решение исходного уравнения, так как: ${\displaystyle ax+by=a(qk)+b(ql)=q(ak+bl)=qd=c.}$ Обратно, если существует хотя бы одно решение уравнения, то ${\displaystyle c}$ кратно ${\displaystyle d}$. Это следует из того, что ${\displaystyle d}$ делит и ${\displaystyle a}$, и ${\displaystyle b}$ (а значит, и всю левую часть), поэтому должно делить и ${\displaystyle c}$ (правую часть). Таким образом, линейное диофантово уравнение имеет хотя бы одно решение тогда и только тогда, когда ${\displaystyle c}$ кратно ${\displaystyle {\text{НОД}}(a,b).}$ Вариации и обобщения Евклидово кольцо Кольца, в которых применим алгоритм Евклида, называются евклидовыми кольцами[14]. К ним относятся, в частности, кольца целых чисел и кольца многочленов. Обобщённый алгоритм Евклида для многочленов Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k[x] от одной переменной над произвольным полем k, поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел получается последовательность полиномиальных остатков (PRS)[15].