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

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

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

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

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

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

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

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

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

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

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

Пусть 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, равен r_n, последнему ненулевому члену этой последовательности.

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

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

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

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

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

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

Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД 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 > R4 > … > 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 — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Связь с цепными дробями[править | править вики-текст]

Отношение 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]

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

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

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

Пример для кольца Z[x]

Пусть cont(f) по определению — НОД коэффициентов многочлена f(x) из Z[x] — содержание многочлена. Частное от деления f(x) на cont(f) называется примитивной частью многочлена f(x) и обозначается primpart(f(x)).

эти определения понадобятся для нахождения НОД двух многочленов p1(x) и p2(x) в кольце Z[x]. Для многочленов над целыми числами верно следующее:

cont(НОД\{p1(x), p2(x)\}) = НОД\{cont(p1(x)), con(p2(x))\}, primpart(НОД\{p1(x), p2(x)\}) = НОД\{primpart(p1(x)), primpart(p2(x))\}.

Таким образом задача отыскания НОД двух произвольных многочленов сводится к задаче отыскания НОД примитивных полиномов.

Пусть есть два примитивных многочлена p1(x) и p2(x) из Z[x], для которых выполняется соотношение между их степенями: deg(p1(x)) = m и deg(p2(x)) = n, m > n. Деление многочленов с остатком предполагает точную делимость старшего коэффициента делимого на старший коэффициент делителя, в общем случае деление с остатком выполнить невозможно. Поэтому вводят алгоритм псевдоделения, который всё же позволяет получить псевдочастное и псевдоостаток (prem), которые будут сами по себе принадлежать множеству многочленов над целыми числами.

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p1(x) на (lc(p2(x)))^{m-n+1}, то есть lc(p2(x))^{m-n+1}p_1(x)=p_2(x)q(x)+r_2(x), \deg(r(x)) < \deg(p_2(x)), где q(x) и r(x) — соответственно псевдочастное и псевдоостаток.

Итак, p_1(x),p_2(x) \in Z[x] — (принадлежат кольцу многочленов над целыми числами), причём \deg(p_1) = n_1 \geq \deg(p_2) = n_2. Тогда алгоритм Евклида состоит из следующих шагов:

1. Вычисление НОД содержаний:

c:=НОД \{ cont(p_1),cont(p_2) \}.

2. Вычисление примитивных частей:

p_1'(x):=cont(p_1(x));  p_2'(x):=cont(p_2(x)).

3. Построение последовательности полиномиальных остатков:

p_1'(x),

 p_2'(x),

 p_3(x):=prem(p_1'(x),p_2'(x)),

 p_4(x):=prem(p_2'(x),p_3(x)),

 p_5(x):=prem(p_3(x),p_4(x)),

 ... ,

 p_h(x):=prem(p_{h-2}(x),p_{h-1}(x)).

4. Выход и возврат результата:

Если \deg(p_h(x)) = 0, то вернуть c, иначе вернуть c:=c* p_h(x).

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

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

См. также[править | править вики-текст]

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

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