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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

НОД

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

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

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

.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка[16]:
где
  • Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма[16].

Вычислительная сложность алгоритма[править | править код]

"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, где Φ - золотое сечение.

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

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

Количество шагов[править | править код]

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

Рекурсивный характер алгоритма Евклида дает следующее уравнение T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1, где T(x, 0) = 0 по предположению.[17]

Наихудший случай[править | править код]

Если для алгоритма Евклида требуются N шагов для пары натуральных чисел a > b > 0, наименьшие значения a и b, для которых это выполняется - числа Фибоначчи FN+2 и FN+1 соответственно.[26] Тогда, если алгоритм Евклида требует 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 году, представляет собой начало теории сложности вычислений,[27] а также первое практическое применение чисел Фибоначчи.[26]

Среднее[править | править код]

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

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

где φ(a) функция Эйлера. Это среднее плавно растет с ростом a.[29]

Константа (константа Портера[30]) в этой формуле , а ε является бесконечно малым.

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

Вычислительная сложность шага[править | править код]

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

rk−2 = qk rk−1 + rk

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

rk = rk−2qk rk−1

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

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

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

Реализация алгоритма на C[править | править код]

1 int gcd (int a, int b) {
2     return b ? gcd(b, a % b) : a;
3 }

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

  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.
  17. 1 2 3 Knuth, 1997, с. 344.
  18. Shallit, 1994, с. 414.
  19. 1 2 Shallit, 1994, с. 401-419.
  20. Shallit, 1994, с. 413.
  21. Lame, 1844, с. 867-870.
  22. Grossman, 1924, с. 443.
  23. 1 2 Knuth, 1997, с. 257-261.
  24. Moeller, 2005, с. 1.
  25. Ore, 1948, с. 45.
  26. 1 2 Knuth, 1997, с. 343.
  27. LeVeque, 1996, с. 3.
  28. Knuth, 1997, с. 353.
  29. Tonkov, 1974, с. 47-57.
  30. Weisstein, Eric W. Porter's Constant (англ.) на сайте Wolfram MathWorld.
  31. Knuth, 1997, с. 352.
  32. Wagon, 1999, с. 335-336.
  33. Cohen, 1993, с. 14.
  34. Cohen, 1993, с. 14-15, 17-18.

Литература[править | править код]

Ссылки[править | править код]