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

Алгоритм Евкліда (також називається евклідів алгоритм) — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, котрий описав його в книгах VII та X Начал.Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

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

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

Алгоритм Евкліда має багато застосувань на практиці, та в теорії. З його допомогою можна згенерувати практично всі найважливіші музичні ритми різних культур у всьому світі.Godfried Toussaint, "The Euclidean algorithm generates traditional musical rhythms, " Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47—56. Алгоритм Евкліда відіграє ключову роль в алгоритмі RSA, поширеному методі криптографії з відкритим ключем. Його також використовують для пошуку розв'язків Діофантових рівнянь, наприклад, пошук чисел, що задовільняють декільком умовам (Китайська теорема про залишки) або обернені числа в скінченному полі. Алгоритм Евкліда також застосовують для побудови ланцюгових дробів в методі Штурма для пошуку дійсних коренів полінома, та в сучасних методах факторизації цілих. Нарешті, він виступає простим інструментом для доведення теорем в теорії чисел, таких, як Теорема Лагранжа про чотири квадрати та основної теореми арифметики.

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

Вступ

Найбільший спільний дільник

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

Якщо НСД(a, b) = 1, тоді a та b називають взаємно простими.Stark, ст. 21. Ця властивість не залежить від того, чи прості числа a та b.LeVeque, ст. 32. Наприклад, ні 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.Leveque, p. 31.

Поняття НСД можна проілюструвати наступним чином. Розглянемо прямокутник зі сторонами 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 можна визначити як добуток спільних дільників обох чисел.Schroeder, ст. 21-22. Наприклад, оскільки 462 можна розкласти на добуток 2 × 3 × 7 × 11 а 1071 можна розкласти на добуток 3 × 3 × 7 × 17, найбільший спільний дільник 462 та 1071 дорівнює 21 = 3 × 7, добутку їхніх спільних дільників. Якщо два числа не мають спільних дільників, їх найбільший спільних дільник 1 і вони взаємно прості. Ключовою перевагою алгоритму Евкліда є ефективне знаходження НСД без необхідності обчислення дільників.Schroeder, ст. 19. Розклад великих цілих чисел на дільники є криптографічно складною задачею, яка лежить в основі багатьох сучасних криптографічних систем.Schroeder, ст. 216—219.

НСД трьох або більшої кількості чисел дорівнює добутку дільників спільних для трьох чисел,Stark, p. 25. який можна обчислити на основі НСД пар чисел.Ore, pp. 47-48. Наприклад,

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

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

Характеристики Алгоритм

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

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

Правильність алгоритму Евкліда можна довести за два кроки.Stark, ст. 16-20. Спочатку необхідно довести, що rn−1 дійсно є дільником a та b, а потім необхідно довести, що це є найбільший спільний дільник.

Доведення, що є дільником a та b З n-го кроку випливає, що ( ділиться на ). Підставимо в n-1-й крок. Маємо:

Таким чином . Повторимо цю операцію n разів і отримаємо, що та . Отже, є дільником a та b.

Доведення, що є найбільшим дільником a та b За означенням число називається найбільшим спільним дільником a та b, тоді і тільки тоді, коли для будь-якого числа для якого виконується: та має виконуватись, що .

Нехай k є дільником a та b, тоді та або можна сказати, що існують такі числа та , що

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

і виконаємо перетворення:

Отже, . Підставимо в 2-й крок і аналогічно продовжимо до тих пір поки з останнього кроку не отримаємо, що , що доводить те, що є найбільшим спільним дільником.

Реалізації

Реалізації алгоритму можна записати у псевдокоді. Наприклад, версію, основану на операції ділення, можна запрограмувати наступним чином:Knuth, ст. 319—320.

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

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

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

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

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

Рекурсивна версія Stillwell, ст. 14. основана на рівності НСД послідовних остач та умові зупинки НСД(rN−1, 0) = rN−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 якщо отримане абсолютне значення від'ємної остачі менше за додатну остачу.Ore, p. 43. В інших версіях, в рівнянні

rk−2 = qk rk−1 + rk

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

rk−2 = (qk + 1) rk−1 + ek

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

Історія

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

Можливо, алгоритм було відкрито не Евклідом, а він лише використав результати, отримані попередниками в Началах. Математик та історик Ван дер Варден вважає, що книгу VII написано на основі підручника з теорії чисел авторства одного з математиків школи Піфагора. Ймовірно, алгоритм був відомий ще Евдоксу Кіндському (приблизно 375 до н. е.). Можливо, навіть, алгоритм був відомий ще до Евдокса, судячи з використання поняття (антифарезис) в роботах Евкліда та Арістотеля.

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

Алгоритмічна ефективність

Обчислювальну ефективність алгоритму Евкліда ретельно досліджено.Knuth, pp. 339–364. Ефективність роботи можна описати як необхідну алгоритму кількість кроків помножену на обчислювальні витрати кожного кроку. Як було показано Ґабріелєм Ламі в 1844 році, кількість необхідних кроків ніколи не більша за кількість цифр h (в десятковій системі) меншого з чисел b помножена на 5. Оскільки обчислювальні витрати кожного кроку зазвичай порядку h, загальні витрати зростають на рівні h2.