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

Алгоритм Евкліда обчислює найбільший спільний дільник (НСД) двох натуральних чисел 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, оскільки у них нема спільних дільників.

Прямокутник з ребрами 24 одиниці на 60 покрито квадратами з ребром 12 одиниць, де 12 це НСД 24 та 60. В загальному випадку, прямокутник з ребрами a на b може бути покрито квадратами з ребром c тоді і лише тоді, коли c є НСД a та b.

Нехай 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, а потім необхідно довести, що це є найбільший спільний дільник.

З 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 ~{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]

Кількість кроків необхідних для обчислення НСД пари натуральних чисел, 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}).}$