Русская Википедия:Алгоритм Евклида

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век Шаблон:Донэ), который впервые описал его в VIIШаблон:Sfn и XШаблон:Sfn книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше времяШаблон:Sfn.

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSAШаблон:Sfn, широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравненийШаблон:Sfn, при построении непрерывных дробейШаблон:Sfn, в методе ШтурмаШаблон:Sfn. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратовШаблон:Sfn и основная теорема арифметикиШаблон:Sfn.

История

Древнегреческие математики называли этот алгоритм Шаблон:Lang-grc2 или Шаблон:Lang-grc2 — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля (IV век Шаблон:Донэ)Шаблон:Sfn. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чиселШаблон:Sfn и в X книге для нахождения наибольшей общей меры двух однородных величинШаблон:Sfn. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника)Шаблон:Sfn. Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Описание

Алгоритм Евклида для целых чисел

Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел

<math> a > b > r_1 > r_2 > r_3 > r_4 >\ \dots\ > r_n</math>

определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

<math>a = bq_0 + r_1,</math>
<math>b = r_1q_1 + r_2,</math>
<math>r_1 = r_2q_2 + r_3,</math>
<math>\cdots</math>
<math>r_{k-2} = r_{k-1} q_{k-1} + r_k,</math>
<math>\cdots</math>
<math>r_{n-2} = r_{n-1}q_{n-1}+ r_n,</math>
<math>r_{n-1} = r_n q_n.</math>

Тогда НОД(a, b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательностиШаблон:Sfn.

Существование таких r1, r2, …, rn, то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утвержденийШаблон:Sfn:

I. Пусть a = b⋅q + r, тогда НОД (a, b) = НОД (b, r). Шаблон:Hider

II. НОД(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число).

Геометрический алгоритм Евклида

Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, вычитая из большего отрезка меньший, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан ЕвклидомШаблон:Sfn и реализуется с помощью циркуля и линейки.

Пример

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147:

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка:

147 = 7 × 21 + 0.

Таким образом последовательность a > b > r1 > r2 > r3 > … > rn в данном конкретном случае будет выглядеть так:

1071 > 462 > 147 > 21.


Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(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; алгоритм заканчивается

Если требуется найти НОД для более чем двух чисел, алгоритм аналогичен, на каждом шаге все числа, кроме наименьшего, заменяются остатками по модулю наименьшего. Нулевые остатки, если получатся, вычёркиваются. Алгоритм завершается, когда остаётся одно ненулевое число, это и есть НОД.

Применения

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

Шаблон:Main

Формулы для <math>r_i</math> могут быть переписаны следующим образом:

<math>r_1 = a + b(-q_0)</math>
<math>r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)</math>
<math>\vdots</math>
НОД <math> (a,b) = r_n = as + bt</math>

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

Цепные дроби

Алгоритм Евклида достаточно тесно связан с цепными дробямиШаблон:Sfn. Отношение a/b допускает представление в виде цепной дроби:

<math>\frac ab=[q_0; q_1, q_2,\cdots,q_n]</math>.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t/s, взятому со знаком минус:

<math>[q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts</math>.

Последовательность равенств, задающая алгоритм Евклида, может быть переписана в форме:

<math>

\begin{align} \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{align} </math>

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме:

<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}} </math>

Третье равенство может быть использовано, чтобы заменить знаменатель выражения r1/r0, получим:

<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}} </math>

Последнее отношение остатков rk/rk−1 всегда может быть заменено с использованием следующего равенства в последовательности, и так до последнего уравнения. Результатом является цепная дробь:

<math>\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 ] </math>

В приведённом выше примере НОД(1071, 462) был посчитан и были найдены частные qk, равные 2, 3 и 7 соответственно. Поэтому 1071/462 может быть записана как:

<math>\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3; 7]</math>

Линейные диофантовы уравнения

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

<math>a \cdot x + b \cdot y = c,</math>

где a, b, c — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типаШаблон:Sfn. Сначала с помощью этого алгоритма можно определить d = НОД(a, b). Затем, используя расширенный алгоритм Евклида, определяются такие k и l, что:

<math>a \cdot k + b \cdot l = d.</math>

То есть x = k и y = l — это частное решение уравнения при c = d. Получается, что если c = q⋅d, то x = q⋅k, y = q⋅l — частное решение исходного уравнения, так как:

<math>a \cdot x + b \cdot y = a \cdot (q \cdot k) + b \cdot (q \cdot l) = q \cdot (a \cdot k + b \cdot l) = q \cdot d = c.</math>

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

Вариации и обобщения

Евклидово кольцо

Кольца, в которых применим алгоритм Евклида, называются евклидовыми кольцамиШаблон:Sfn. К ним относятся, в частности, кольца целых чисел и кольца многочленов.

Обобщённый алгоритм Евклида для многочленов

Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k[x] от одной переменной над произвольным полем k, поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел получается последовательность полиномиальных остатков (PRS)Шаблон:Sfn.

Шаблон:Hider

Ускоренные версии алгоритма

  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остаткаШаблон:Sfn:
<math>r_i \equiv r_{i-2} \pmod{r_{i-1}},</math>
где
<math>-\frac{r_{i-1}}{2}\leq r_i\leq\frac{r_{i-1}}{2}.</math>

Вычислительная сложность алгоритма

"A set of colored lines radiating outwards from the origin of an x-y coordinate system. Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm."
Число шагов в алгоритме Евклида для НОД(x,y). Более светлые точки (красные и жёлтые) указывают на относительно меньшее количество шагов, тогда как более тёмные точки (фиолетовые и синие) на большее количество шагов. Самая большая тёмная область следует за прямой y = Φx, где Φ — золотое сечение.

Вычислительная сложность алгоритма Евклида изучена полностью.Шаблон:Sfn Эта сложность может быть описана произведением количества шагов деления, требуемых алгоритмом, на вычислительную сложность одного шага. Первый известный анализ алгоритма Евклида был предложен Рейнаудом в 1811.Шаблон:Sfn Он показал, что число шагов алгоритма для пары чисел (u, v) ограничено v. Позже он улучшил оценку до v/2 + 2. Эмиль Леже в 1837 году изучил наихудший случай, когда для вычисления НОД подаются последовательные числа Фибоначчи.Шаблон:Sfn Затем, в 1841 году, Пьер Джосеф Финк показал,Шаблон:Sfn что количество шагов алгоритма не превышает 2 log2 v + 1. Следовательно, алгоритм работает за полиномиальное время от размера меньшего из пары чисел (u, v).Шаблон:Sfn Анализ Финка был уточнён Габриэлем Ламе в 1844 году.Шаблон:Sfn Он показал, что количество шагов, необходимых для завершения алгоритма, не более чем в пять раз превышает h — количество цифр в десятичном представлении меньшего из пары чисел (u, v).Шаблон:Sfn[1]

Когда НОД вычисляется для чисел, которые вписываются в одно машинное слово, каждый шаг алгоритма занимает постоянное время. В данном случае анализ Ламе предполагает, что вычислительная сложность оценивается как O(h). Однако в модели расчёта, подходящей для вычислений с числами больше одного машинного слова, оценка сложности вычисления одного остатка может быть O(h2).Шаблон:Sfn В этом случае общее время для всех этапов алгоритма можно проанализировать с помощью телескопического ряда, показав, что это также O(h2). Для ускорения алгоритма Евклида могут быть использованы современные алгоритмические методы, основанные на методе Шёнхаге — Штрассена для быстрого целочисленного умножения. Это приводит к квазиполиномиальному времени.Шаблон:Sfn

Количество шагов

Число шагов для вычисления НОД двух натуральных чисел a и b обозначим как T(a, b). Если g — это наибольший общий делитель a и b, тогда a = mg и b = ng для двух взаимно простых чисел m и n. Тогда Шаблон:Math, что можно заметить, если разделить уравнения, полученные при вычислении НОД для пары (a, b), на g.Шаблон:Sfn Используя тот же принцип, число шагов алгоритма остаётся неизменным, если a и b умножаются на общий множитель w, что эквивалентно равенству T(a, b) = T(wa, wb). Следовательно, количество шагов T может сильно различаться между соседними парами чисел, такими как (a, b) и (a, b+1), так как данная величина зависит от НОД.

Рекурсивный характер алгоритма Евклида даёт следующее уравнение Шаблон:Math, где T(x, 0) = 0 по предположению.Шаблон:Sfn

Наихудший случай

Если для алгоритма Евклида требуются N шагов для пары натуральных чисел a > b > 0, наименьшие значения a и b, для которых это выполняется — числа Фибоначчи FN+2 и FN+1 соответственно.Шаблон:Sfn Тогда, если алгоритм Евклида требует N шагов для пары чисел (a,b), где a > b, выполняются следующие неравенства a ≥ FN+2 и b ≥ FN+1. Доказать это можно по математической индукции. Если N = 1, тогда a делится на b без остатка. Наименьшие натуральные числа, для которых это верно, равны b = 1 и a = 2, соответственно F2 и F3. Предположим теперь, что результат выполняется для всех значений N до M − 1. Первый шаг алгоритма Евклида с M шагами a = q0b + r0, и алгоритм Евклида для пары чисел (b,r0), где b > r0, требует M − 1 шагов. По предположению индукции имеем b ≥ FM+1 и r0 ≥ FM. Следовательно, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году, представляет собой начало теории сложности вычислений,Шаблон:Sfn а также первое практическое применение чисел Фибоначчи.Шаблон:Sfn

Теорема Ламе

Число делений с остатком в процессе применения алгоритма Евклида не превосходит упятеренного количества цифр меньшего числа <math>b</math>, записанного в десятичной системе[2].

Среднее

Существуют различные способы вычисления среднего количества шагов алгоритма. Первый способ вычисления — среднее время T(a), необходимое для вычисления НОД заданного числа a и меньшего натурального числа b, выбранного с равной вероятностью из целых чисел от 0 до a − 1.Шаблон:Sfn

<math>T(a) = \frac 1 a \sum_{0 \leq b<a} T(a, b).</math>

Однако, поскольку T(a, b) сильно колеблется в зависимости от НОД двух чисел, усреднённая функция T(a) также является «шумной».Шаблон:Sfn Для того, чтобы уменьшить этот шум, второе среднее τ(a) берётся по всем числам, взаимно простым с a.

<math>\tau(a) = \frac 1 {\varphi(a)} \sum_{\begin{smallmatrix} 0 \leq b<a \\ \gcd(a, b) = 1 \end{smallmatrix}} T(a, b)

</math> где φ(a) функция Эйлера. Это среднее плавно растёт с ростом a.Шаблон:Sfn

<math>\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon})</math>

Константа (константа Портера[3]) в этой формуле <math>C \approx 1.467</math>, а ε является бесконечно малым.

Третье среднее значение Y(n) определяется как среднее число шагов, требуемых, когда a и b выбираются случайным образом (с равномерным распределением) от 1 до n.

<math>Y(n) = \frac 1 {n^2} \sum_{a=1}^n \sum_{b=1}^n T(a, b) = \frac 1 n \sum_{a=1}^n T(a).

</math>

Вычислительная сложность шага

На каждом шаге алгоритма Евклида вычисляется коэффициент qk и остаток rk для заданной пары целых чисел rk−2 и rk−1. Эти величины связаны следующим соотношением:

Шаблон:Math

Вычислительная сложность каждого шага связана главным образом с нахождением qk, так как остаток rk можно быстро вычислить, используя rk−2, rk−1, и qk

Шаблон:Math

Вычислительная сложность операции деления чисел размером h бит оценивается как O(h(ℓ+1)), где ℓ размер частного.Шаблон:Sfn

Для сравнения, исходный алгоритм Евклида, с использованием вычитания, может быть намного медленнее. В большинстве случаев коэффициент qk является малым числом. Вероятность данного частного q примерно равна ln|u/(u − 1)|, где u = (q + 1)2.Шаблон:Sfn Для иллюстрации вероятность частного 1, 2, 3 или 4 составляет примерно 41,5 %, 17,0 %, 9,3 % и 5,9 % соответственно. Так как операция вычитания быстрее, чем деление, особенно для чисел больше одного машинного слова,Шаблон:Sfn алгоритм Евклида с использованием вычитания может быть более конкурентоспособным в сравнении с алгоритмом, использующим деление.Шаблон:Sfn Это используется в бинарном алгоритме вычисления НОД.Шаблон:Sfn

Оценка сложности алгоритма вычисляется как произведение количества шагов на время выполнения одного шага. Она показывает, что алгоритм Евклида растёт квадратично O(h2), где h — среднее число цифр в двух начальных числах a и b в десятичной записи. Пусть h0, h1, …, hN−1 представляют число цифр в последовательных остатках r0, r1, …, rN−1. Так как число шагов N растёт линейно с h, время работы ограничено следующим выражением:

<math>

O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2) \Big) \subseteq O(h(h_0+2N))\subseteq O(h^2).</math>

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:ВС

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Абрамов С. А. Математические построения и программирование. — М., Наука, 1978. — Тираж 100 000 экз. — c. 170
  2. ↑ Абрамов С. А. Математические построения и программирование. — М., Наука, 1978. — Тираж 100 000 экз. — c. 170
  3. ↑ Шаблон:Mathworld
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Евклида&oldid=8940062