Эта статья входит в число добротных статей

Алгоритм Евклида

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII[1] и X[2] книгах «Начал». В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.

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

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

История[править | править вики-текст]

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля[3]. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел[1] и в X книге для нахождения наибольшей общей меры двух однородных величин[2]. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

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

Описание[править | править вики-текст]

Алгоритм Евклида для целых чисел[править | править вики-текст]

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

 a > b > r_1 > r_2 > r_3 > r_4 > \cdots > r_n

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

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

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

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

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

  • Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).
  • НОД(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число, кроме нуля).

Геометрический алгоритм Евклида[править | править вики-текст]

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

Пример[править | править вики-текст]

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

Применения[править | править вики-текст]

Расширенный алгоритм Евклида и соотношение Безу[править | править вики-текст]

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

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

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

Цепные дроби[править | править вики-текст]

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

\frac ab=[q_0; q_1, q_2,\cdots,q_n].

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

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

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


\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}

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

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}}

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

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}}

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

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

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

\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3, 7]

Линейные диофантовы уравнения[править | править вики-текст]

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

a \cdot x + b \cdot y = c,

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

a \cdot k + b \cdot l = d.

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

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.

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

Вариации и обобщения[править | править вики-текст]

Евклидово кольцо[править | править вики-текст]

Кольца, в которых применим алгоритм Евклида, называются евклидовыми кольцами[14]. К ним относятся, в частности, кольца целых чисел и кольца многочленов.

Обобщённый алгоритм Евклида для многочленов[править | править вики-текст]

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

Ускоренные версии алгоритма[править | править вики-текст]

  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка[16]:
r_i \equiv r_{i-2} \pmod{r_{i-1}},
где
-\frac{r_{i-1}}{2}\leq r_i\leq\frac{r_{i-1}}{2}.
  • Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма[16].

Примечания[править | править вики-текст]

  1. 1 2 Мордухай-Болтовской, 1949, с. 11—13.
  2. 1 2 3 Мордухай-Болтовской, 1949, с. 103—105.
  3. 1 2 Кнут, 2001, с. 378.
  4. Menezes, 1996, с. 286.
  5. 1 2 Курант, 2001, с. 74—76.
  6. 1 2 Виноградов, 1952, с. 14—18.
  7. Энгелер, 1987, с. 24—31.
  8. Тихомиров, 2003, с. 11—14.
  9. Калужин, 1969, с. 6—14.
  10. Цейтен, 1932, с. 112-114.
  11. Виноградов, 1952, с. 9-10.
  12. Курант, 2001, с. 67-70.
  13. Хассе, 1953, с. 29-30.
  14. Курош, 1973, с. 91-92.
  15. Панкратьев, 2007, с. 54-58.
  16. 1 2 Gathen, 2013, с. 313-326.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]