Archiwum 15 maja 2019


Algorytm Euklidesa
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.