15 maja 2019, 20:10
Algorytm Euklidesa
Algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej. Algorytm Euklidesa jest rekurencyjny.
Przykładowy algorytm
(21,18) -> (21-18,18)
(3,18) -> (3,18-3)
(3,15) -> (3,15-5)
(3,12) -> (3,12-3)
(3,9) -> (3,9-3)
(3,6) -> (3,6-3)
(3,3) -> koniec, NWD (21,18)=3
Zastosowanie algorytmu
Istnieje wiele teoretycznych i praktycznych zastosowań algorytmu. Może on zostać wykorzystany do generowania rytmów muzycznych, stosowanych jako ostinato w muzyce. Jest wykorzystywany w algorytmie RSA. Algorytm Euklidesa używany jest też do rozwiązywania równań diofantycznych, na przykład do znajdowania liczb spełniających zadany układ kongruencji (chińskie twierdzenie o resztach) czy znajdowania liczb odwrotnych w ciele skończonym. Może być także stosowany do generowania ułamków łańcuchowych w metodzie. Sturma do obliczania pierwiastków rzeczywistych wielomianu. Wykorzystywany jest również w kilku współczesnych algorytmach do faktoryzacji liczb całkowitych.