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

Алгоритм Евкліда (також називається евклідів алгоритм) — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, котрий описав його в книгах VII та X Начал.^[1]

Найбільший спільний дільник двох чисел це найбільше число, що ділить обидва дані числа без остачі. Алгоритм Евкліда заснований на тому, що НСД не змінюється, якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105 (252 = 21 × 12; 105 = 21 × 5); оскільки 252 − 105 = 147, НСД 147 та 105 також 21. Оскільки більше з двох чисел постійно зменшується, повторне виконання цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне з чисел дорівнюватиме нулю, те, що залишилось, і є НСД. Обертаючи кроки алгоритму Евкліда у зворотний порядок, НСД можна виразити як лінійну комбінацію даних чисел помножених на цілі коефіцієнти, наприклад 21 = 5 × 105 + (−2) × 252. Ця важлива властивість відома як рівняння Безу.

Найдавніший опис алгоритму знаходиться в Началах Евкліда (біля 300 до н. е.), що робить його найдавнішим чисельним алгоритмом, яким користуються і нині. Оригінальний варіант алгоритму описував роботу лише з натуральними числами та геометричними довжинами (дійсними числами), алгоритм було узагальнено в XIX столітті на роботу з іншими типами чисел, такими як Гаусові числа та поліноми з однією змінною. Це призвело до появи сучасних алгебраїчних понять, таких як Евклідові класи. Алгоритм Евкліда було узагальнено ще далі для роботи з іншими математичними структурами, такими як вузли та поліноми від багатьох змінних.

Алгоритм Евкліда має багато застосувань на практиці, та в теорії. З його допомогою можна згенерувати практично всі найважливіші музичні ритми різних культур у всьому світі.^[2] Алгоритм Евкліда відіграє ключову роль в алгоритмі RSA, поширеному методі криптографії з відкритим ключем. Його також використовують для пошуку розв'язків Діофантових рівнянь, наприклад, пошук чисел, що задовільняють декільком умовам (Китайська теорема про залишки) або обернені числа в скінченному полі. Алгоритм Евкліда також застосовують для побудови ланцюгових дробів в методі Штурма для пошуку дійсних коренів полінома, та в сучасних методах факторизації цілих. Нарешті, він виступає простим інструментом для доведення теорем в теорії чисел, таких, як Теорема Лагранжа про чотири квадрати та основної теореми арифметики.

Алгоритм Евкліда ефективно обчислює НСД великих чисел, оскільки виконує операцій не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі). Цю властивість було доведено Ґабріелем Ламе (англ. Gabriel Lamé) в 1844 році, що позначило початок теорії складності обчислень. Методи підвищення ефективності алгоритму були розроблені в XX столітті.

Вступ[ред. | ред. код]

Найбільший спільний дільник[ред. | ред. код]

Алгоритм Евкліда обчислює найбільший спільний дільник (НСД) двох натуральних чисел a та b. Найбільший спільний дільник g — це найбільше натуральне число яке ділить як a так і b без остачі. Найбільший спільний дільник також записують як НСД(a, b) або, простіше, (a, b)^[3] хоча останнє позначення використовують і для інших математичних понять, таких як координати двовимірних векторів.

Якщо НСД(a, b) = 1, тоді a та b називають взаємно простими.^[4] Ця властивість не залежить від того, чи прості числа a та b.^[5] Наприклад, ні 6 ні 35 не прості, оскільки їх можна розкласти на добутки 6 = 2 × 3 та 35 = 5 × 7. Однак, 6 та 35 взаємно прості. Жодне натуральне число окрім 1 не ділить водночас 6 та 35, оскільки у них нема спільних дільників.

Нехай g = НСД(a, b). Оскільки a та b є добутками g, їх можна записати, як a = mg та b = ng, і не існує більшого числа G > g з такою ж властивістю. Натуральні числа m та n мають бути взаємно простими, оскільки інший спільний дільник може бути виділений з m та n, що збільшить g. Таким чином, будь-яке число c, що ділить a та b має ділити і g. Найбільший спільний дільник g чисел a та b може бути визначений, як спільний дільник, який можна поділити іншим спільним дільником c.^[6]

Поняття НСД можна проілюструвати наступним чином.^[7] Розглянемо прямокутник зі сторонами a та b, та будь-який спільний дільник c, що ділить і a, і b без остачі. Ребра прямокутника можна поділити на відрізки довжиною c, які поділять прямокутник на сітку квадратів зі стороною c. Найбільший спільний дільник g дорівнює найбільшому можливому значенню c. Наприклад, прямокутник 24 на 60 може бути покрита сіткою квадратів зі стороною 1, 2, 3, 6 або 12. Таким чином, 12 є найбільшим спільним дільником 24 та 60. Прямокутник 24 на 60 можна поділити сіткою квадратами з ребром 12, два квадрати вздовж одного ребра (24/12 = 2), та п'ятеро (60/12 = 5) вздовж іншого.

Найбільший спільний дільник a та b можна визначити як добуток спільних дільників обох чисел.^[8] Наприклад, оскільки 462 можна розкласти на добуток 2 × 3 × 7 × 11 а 1071 можна розкласти на добуток 3 × 3 × 7 × 17, найбільший спільний дільник 462 та 1071 дорівнює 21 = 3 × 7, добутку їхніх спільних дільників. Якщо два числа не мають спільних дільників, їх найбільший спільних дільник 1 і вони взаємно прості. Ключовою перевагою алгоритму Евкліда є ефективне знаходження НСД без необхідності обчислення дільників.^[9][10] Розклад великих цілих чисел на дільники є криптографічно складною задачею, яка лежить в основі багатьох сучасних криптографічних систем.^[11]

НСД трьох або більшої кількості чисел дорівнює добутку дільників спільних для трьох чисел,^[12] який можна обчислити на основі НСД пар чисел.^[13] Наприклад,

НСД(a, b, c) = НСД(a, НСД(b, c)) = НСД(НСД(a, b), c) = НСД(НСД(a, c), b).

Тобто, алгоритм Евкліда обчислення найбільшого спільного дільника двох цілих підходить і для обчислення НСД довільної кількості цілих.

Характеристики[ред. | ред. код]

Алгоритм[ред. | ред. код]

${\displaystyle {a}={q_{0}}{b}+{r_{0}}\qquad {\text{(0)}}}$

${\displaystyle {b}={q_{1}}{r_{0}}+{r_{1}}\qquad {\text{(1)}}}$

${\displaystyle {r_{0}}={q_{2}}{r_{1}}+{r_{2}}\qquad {\text{(2)}}}$

${\displaystyle {r_{1}}={q_{3}}{r_{2}}+{r_{3}}\qquad {\text{(3)}}}$

${\displaystyle \dots }$

${\displaystyle {r_{n-3}}={q_{n-1}}{r_{n-2}}+{r_{n-1}}\qquad {\text{(n-1)}}}$

${\displaystyle {r_{n-2}}={q_{n}}{r_{n-1}}+0\qquad {\text{(n)}}}$

Алгоритм Евкліда ітеративний, тобто, пошук розв'язку відбувається за декілька кроків. Для того щоб знайти НСД(a, b) на 0-му кроці знаходять остачу r₀ від ділення a на b. На 1-му кроці знаходять остачу від ділення b на r₀. Оскільки остачі зменшуються на кожному кроці але не можуть бути від'ємними, то цю операцію виконують n кроків до тих пір поки не отримують остачу 0. Найбільшим спільним дільником є остання не нульова остача r_n−1. Кількість кроків в алгоритмі має бути скінченною, оскільки існує лише скінченна кількість цілих чисел між початковою остачею r₀ та нулем.

Доведення алгоритму Евкліда[ред. | ред. код]

Правильність алгоритму Евкліда можна довести за два кроки.^[14] Спочатку необхідно довести, що r_n−1 дійсно є дільником a та b, а потім необхідно довести, що це є найбільший спільний дільник.

Доведення, що ${\displaystyle {r_{n-1}}}$ є дільником a та b[ред. | ред. код]

З n-го кроку випливає, що ${\displaystyle ~{r_{n-2}}\;\vdots \;{r_{n-1}}}$ (${\displaystyle {r_{n-2}}}$ ділиться на ${\displaystyle {r_{n-1}}}$). Підставимо ${\displaystyle ~{r_{n-2}}}$ в n-1-й крок. Маємо:

${\displaystyle ~{r_{n-3}}={q_{n-1}}{q_{n}}{r_{n-1}}+{r_{n-1}}}$

${\displaystyle ~{r_{n-3}}={r_{n-1}}({q_{n-1}}{q_{n}}+1)}$

Таким чином ${\displaystyle ~{r_{n-3}}\;\vdots \;{r_{n-1}}}$. Повторимо цю операцію n разів і отримаємо, що ${\displaystyle ~{a}\;\vdots \;{r_{n-1}}}$ та ${\displaystyle ~{b}\;\vdots \;{r_{n-1}}}$. Отже, ${\displaystyle ~{r_{n-1}}}$ є дільником a та b.

Доведення, що ${\displaystyle {r_{n-1}}}$ є найбільшим дільником a та b[ред. | ред. код]

За означенням число ${\displaystyle ~{d}}$ називається найбільшим спільним дільником a та b, тоді і тільки тоді, коли для будь-якого числа ${\displaystyle ~\forall {k}}$ для якого виконується: ${\displaystyle ~{a}\;\vdots \;{k}}$ та ${\displaystyle ~{b}\;\vdots \;{k}}$ має виконуватись, що ${\displaystyle ~{d}\;\vdots \;{k}}$.

Нехай k є дільником a та b, тоді ${\displaystyle ~{a}\;\vdots \;{k}}$ та ${\displaystyle ~{b}\;\vdots \;{k}}$ або можна сказати, що існують такі числа ${\displaystyle ~{a_{1}}}$ та ${\displaystyle ~{b_{1}}}$, що

${\displaystyle ~{a}={a_{1}}{k}}$

${\displaystyle ~{b}={b_{1}}{k}}$

Підставимо в 1-й крок алгоритму:

${\displaystyle ~{a_{1}}{k}={q_{0}}{b_{1}}{k}+{r_{0}}}$ і виконаємо перетворення:

${\displaystyle ~{r_{0}}={a_{1}}{k}-{q_{0}}{b_{1}}{k}}$

${\displaystyle ~{r_{0}}={k}({a_{1}}-{q_{0}}{b_{1}})}$

Отже, ${\displaystyle ~{r_{0}}\;\vdots \;{k}}$. Підставимо ${\displaystyle ~{r_{0}}}$ в 2-й крок і аналогічно продовжимо до тих пір поки з останнього кроку не отримаємо, що ${\displaystyle ~{r_{n-1}}\;\vdots \;{k}}$, що доводить те, що ${\displaystyle ~{r_{n-1}}}$ є найбільшим спільним дільником.

Реалізації[ред. | ред. код]

Реалізації алгоритму можна записати у псевдокоді. Наприклад, версію, основану на операції ділення, можна запрограмувати наступним чином:^[15]

функція нсд(a, b)     поки b ≠ 0        t := b        b := a mod b        a := t     поверни a 

На початку k-ї ітерації, змінна b має значення останньої остачі r_k−1, а змінна a має значення попередньої остачі r_k−2. Крок b := a mod b еквівалентний рекурсивній формулі r_k ≡ r_k−2 mod r_k−1. Допоміжна змінна t має значення r_k−1 поки відбувається обчислення наступної остачі r_k. В кінці циклу, змінна b має значення остачі r_k, а змінна a має значення попередньої r_k−1.

В описаній Евклідом версії алгоритму, обчислення остачі (b = a mod b) замінено повторним відніманням.^[16]

функція нсд(a, b)     якщо a = 0        поверни b     поки b ≠ 0         якщо a > b            a := a − b         інакше            b := b − a     поверни a 

Змінні a та b почергово набувають значення попередніх остач r_k−1 та r_k−2. Якщо a більше за b на початку ітерації; тоді a дорівнює r_k−2, оскільки r_k−2 > r_k−1. Протягом циклу, a зменшується на число, кратне попередній остачі b доки a не стане меншим за b. Тоді a стає наступною остачею r_k. Потім b зменшується на число, кратне a поки не стане меншим за a, даючи значення наступної остачі r_k+1, і так далі.

Рекурсивна версія ^[17] основана на рівності НСД послідовних остач та умові зупинки НСД(r_N−1, 0) = r_N−1.

функція нсд(a, b)     якщо b = 0        поверни a     інакше        поверни нсд(b, a mod b) 

Наприклад, НСД(1071, 462) обчислюють на основі еквівалентного значення НСД(462, 1071 mod 462) = НСД(462, 147). Яке, в свою чергу, обчислюють на основі НСД(147, 462 mod 147) = НСД(147, 21), а це, обчислюють від НСД(21, 147 mod 21) = НСД(21, 0) = 21.

Метод найменших абсолютних остач[ред. | ред. код]

В іншому варіанті реалізації алгоритму Евкліда на кожному кроці частку збільшують на 1 якщо отримане абсолютне значення від'ємної остачі менше за додатну остачу.^[18][19] В інших версіях, в рівнянні

r_k−2 = q_k r_k−1 + r_k

припускалось, що r_k−1 > r_k > 0. Однак, іншу від'ємну остачу e_k можна обчислити таким чином:

r_k−2 = (q_k + 1) r_k−1 + e_k

де r_k−1 вважається додатнім. Якщо |e_k| < |r_k|, тоді r_k замінюють на e_k. Як показано Леопольдом Кронекером, цей варіант витрачає найменшу кількість кроків у порівнянні з іншими варіантами алгоритму.^[18][19]

Історія[ред. | ред. код]

Алгоритм Евкліда один з найдавніших алгоритмів, що досі використовують.^[20] Він описаний в Началах Евкліда (приблизно 300 до н. е.), а саме, в книгах VII та X. В сьомій книзі алгоритм описано для цілих чисел, а в десятій — для довжин відрізків. Можна сказати, що алгоритм описано для дійсних чисел. Однак, довжина, площа та об'єм, що їх вимірюють нині в дійсних числах, вимірюють у різних одиницях та не існує універсальної природної одиниці для вимірювання довжини, площі або об'єму. Також поняття дійсних чисел в ті часи було ще не відоме. Другий алгоритм геометричний. НСД двох довжин a та b відповідає довжині найдовшого відрізку g, яким можна виміряти a та b без остачі; іншими словами, довжини відрізків a та b дорівнюють добуткові довжини g на ціле число.

Можливо, алгоритм було відкрито не Евклідом, а він лише використав результати, отримані попередниками в Началах.^[21][22] Математик та історик Ван дер Варден вважає, що книгу VII написано на основі підручника з теорії чисел авторства одного з математиків школи Піфагора.^[23] Ймовірно, алгоритм був відомий ще Евдоксу Кіндському (приблизно 375 до н. е.).^[20][24] Можливо, навіть, алгоритм був відомий ще до Евдокса,^[25][26] судячи з використання поняття грец. ἀνθυφαίρεσις (антифарезис) в роботах Евкліда та Арістотеля.^[27]

Нові можливості застосування алгоритму Евкліда було знайдено в XIX столітті. В 1829 році Чарльз Штурм застосував алгоритм Евкліда в методі Штурма для пошуку дійсних коренів поліномів у заданому інтервалі.^[28]

Алгоритмічна ефективність[ред. | ред. код]

Обчислювальну ефективність алгоритму Евкліда ретельно досліджено.^[29] Ефективність роботи можна описати як необхідну алгоритму кількість кроків помножену на обчислювальні витрати кожного кроку. Як було показано Ґабріелєм Ламі в 1844 році,^[30] кількість необхідних кроків ніколи не більша за кількість цифр h (в десятковій системі) меншого з чисел b помножена на 5.^[31][32] Оскільки обчислювальні витрати кожного кроку зазвичай порядку h, загальні витрати зростають на рівні h².

Кількість кроків[ред. | ред. код]

Кількість кроків необхідних для обчислення НСД пари натуральних чисел, a та b, можна позначити як T(a, b).^[33] Якщо g є НСД a та b, тоді a = mg та b = ng де m та n взаємно прості числа. Тоді

T(a, b) = T(m, n)

що можна отримати поділивши всі кроки алгоритму на g.^[34] Аналогічно, кількість кроків лишається незмінною якщо a та b помножити на спільний дільник w: T(a, b) = T(wa, wb). Таким чином, кількість кроків T може сильно відрізнятись для пари сусідніх чисел, наприклад T(a, b) та T(a, b + 1), в залежності від розміру обох НСД.

Рекурсивна природа алгоритму Евкліда дає наступне рівняння

T(a, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

де T(x, 0) = 0 за припущенням.^[33]

Кількість кроків у найгіршому випадку[ред. | ред. код]

Якщо алгоритму Евкліда необхідні N кроків для обчислення НСД натуральних чисел a > b > 0, то найменші числа, для яких це дійсне, є числа Фібоначчі F_N+2 та F_N+1.^[35] Цю властивість можна довести методом математичної індукції.^[36] Якщо N = 1, b ділить a без остачі; найменші натуральні числа, для яких це правильно — b = 1 та a = 2, які дорівнюють F₂ та F₃ відповідно. Припустімо, що це правильно для значень N не більших за M − 1. Першим кроком M-крокового алгоритму є a = q₀b + r₀, а другим b = q₁r₀ + r₁. Оскільки алгоритм рекурсивний, йому необхідно M − 1 кроків для знаходження НСД(b, r₀) та найменшими значеннями є F_M+1 та F_M. Таким чином, a має найменше значення коли q₀ = 1, що значить a = b + r₀ = F_M+1 + F_M = F_M+2. Це доведення, оприлюднене Ґабріелем Ламі в 1844 заклало основи теорії обчислювальної складності,^[37] а також є першим застосуванням чисел Фібоначчі на практиці.^[35]

Цього результату достатньо, аби показати, що алгоритм Евкліда виконує кроків не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі).^[38] Якщо алгоритму потрібно більше N кроків, тоді b більше або дорівнює F_N+1, що, в свою чергу. більше або дорівнює φ^N−1, де φ дорівнює золотому перетину. Оскільки b ≥ φ^N−1, тоді N − 1 ≤ log_φb. Оскільки log₁₀φ > 1/5, (N − 1)/5 < log₁₀φ log_φb = log₁₀b. Таким чином, N ≤ 5 log₁₀b. Звідси випливає, що алгоритм Евкліда потребує менше за O(h) ділень, де h дорівнює кількості цифр в меншому числі b.

Середня кількість кроків[ред. | ред. код]

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

${\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).}$

Однак, оскільки T(a, b) істотно змінюється в залежності від НСД обох чисел, усереднена функція T(a) також містить «шум».^[39]

Аби зменшити цей шум, використовують друге середнє τ(a) для взаємно простих до a чисел.

${\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{0\leq b<a,\mathrm {GCD} (a,b)=1}T(a,b).}$

Всього існує φ(a) взаємно простих чисел менших за a, де φ це функція Ейлера. Значення τ поступово зростає разом з a^[40][41]

τ(a) = (12/π²) ln 2 ln a + C + O(a^{−(1/6) + ε})

з похибкою порядку a^{−(1/6) + ε}, де ε нескінченно мала. Стала C в цій формулі дорівнює

C = −(1/2) + 6 (ln 2/π²)( 4γ − 24π²ζ '(2) + 3 ln 2 − 2) ≈ 1.467

де γ це Стала Ейлера — Маскероні, а ζ' — похідна дзета-функції Рімана.^[42][43] Значення основного коефіцієнту (12/π²) ln 2 було визначено двома незалежними методами.^[44][45]

Оскільки перше середнє може бути обчислене на основі тау середнього додаванням дільників d числа a^[46]

${\displaystyle T(a)={\frac {1}{a}}\sum _{d|a}\varphi (d)\tau (d)}$

воно може бути наближене формулою^[47]

T(a) ≈ C + (12/π²) ln 2 ( ln a − Σ_d|a Λ(d)/d )

де Λ(d) — функція фон Мангольда.^[48]

Третє середнє Y(n) визначають як середню кількість кроків необхідних для обчислення НСД коли a та b випадкові числа (рівномірно розподілені) від 1 до n^[47]

${\displaystyle 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).}$

Заміна наближеною формулою для T(a) в це рівняння дає оцінку Y(n)^[49]

Y(n) ≈ (12/π²) ln 2 ln n + 0.06.

Обчислювальні витрати за крок[ред. | ред. код]

На кожному кроці k алгоритму Евкліда, обчислюють частку q_k та остачу r_k для пари цілих r_k−2 та r_k−1

r_k−2 = q_k r_k−1 + r_k.

Основні витрати за крок полягають в обчисленні q_k, оскільки остача r_k можна швидко обчислити на основі r_k−2, r_k−1 та q_k

r_k = r_k−2 − q_k r_k−1.

Обчислювальна складність ділення h-бітних чисел змінюються як O(h(ℓ+1)), де ℓ — довжина частки.^[50]

Для порівняння, оригінальний варіант алгоритму на основі віднімання може бути набагато повільнішим. Ділення цілого еквівалентне q віднімань, де q — частка. Якщо відношення a до b велике, частка буде також великою і знадобиться велика кількість віднімань. З іншого боку, було показано, що частки найімовірніше матимуть невеликі значення. Ймовірність отримати частку q приблизно ln|u/(u − 1)| де u = (q + 1)².^[51] Наприклад, ймовірність отримати частку 1, 2, 3, або 4 дорівнює приблизно 41.5%, 17.0%, 9.3%, та 5.9%, відповідно. Оскільки операція віднімання швидша за ділення, особливо для великих чисел,^[52] оснований на відніманні алгоритм Евкліда може бути на рівні з основаним на діленні.^[53] Цю властивість використано в бінарному алгоритмі Евкліда.^[54]

Поєднання оцінки кількості кроків з оцінкою обчислювальних витрат на крок показує, що витрати алгоритму Евкліда зростають квадратично (h²) в залежності від середньої кількості цифр h в заданих числах. Нехай h₀, h₁, …, h_N−1 дорівнює кількості цифр в послідовних остачах r₀, r₁, …, r_N−1. Оскільки кількість кроків N зростає пропорційно h, час роботи алгоритму обмежено

${\displaystyle 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}).}$

Приклад[ред. | ред. код]

Обчислимо НСД чисел 1071 та 1029.

У випадку невеликих чисел, можна використати послідовне ділення у стовпчик. Наприклад, нам потрібно знайти НСД (2700, 1520):

Отже, НСД (2700, 1520) = 20.

Див. також[ред. | ред. код]

• Найбільший спільний дільник
• Розкладання на прості множники
• Розширений алгоритм Евкліда

Посилання[ред. | ред. код]