Algorytmy

Algorytm Euklidesa

Algorytm Euklidesa pozwala nam wyznaczyć Największy Wspólny Dzielnik ($\textrm{NWD}$) dwóch liczb, bez znajomości rozkładu tych liczb na czynniki pierwsze. Dzięki temu jesteśmy w stanie bardzo szybko wyznaczyć $\textrm{NWD}$ dla dwóch dużych liczb. Zasadę działania algorytmu przedstawimy na przykładzie liczb $693$ i $93$:

$$ \begin{array}{r l c c} 693 : 93 = 7 & \textrm{reszta } 42 & \quad & 693 = 7 \cdot 93 + 42 \\ 93 : 42 = 2 & \textrm{reszta } 9 & & 93 = 2 \cdot 42 + 9 \\ 42 : 9 = 4 & \textrm{reszta } 6 & \quad & 42 = 4 \cdot 9 + 6 \\ 9 : 6 = 1 & \textrm{reszta } 3 & & 9 = 1 \cdot 6 + 3 \\ 6 : 3 = 2 & \textrm{reszta } 0 & & 6 = 2 \cdot 3 + 0 \end{array} $$

Ostatnia niezerowa reszta wynosi $3$ i jest to $\textrm{NWD}$ liczb $693$ i $93$.

Odwrócony algorytm Euklidesa

Dzięki algorytmowi Euklidesa wiemy, że istnieją liczby całkowite $c$ oraz $d$ takie, że: $$ \textrm{NWD}(a,n) = c \cdot a + d \cdot n $$ Liczby $c$ oraz $d$ wyznaczamy za pomocą odwróconego algorytmu Euklidesa. Wyznaczamy $c$ i $d$ dla $\textrm{NWD}(693, 93)$ korzystając z wyliczeń wykonanych w algorytmie Euklidesa:

$ 693 = 7 \cdot 93 + 42 \Rightarrow $

$42 = 693 - 7 \cdot 93 $

$ 93 = 2 \cdot 42 + 9 \Rightarrow 9 = 93 - 2 \cdot 42 = 93 - 2 \cdot $

$ (693 - 7 \cdot 93) $

$=$

$15 \cdot 93 - 2 \cdot 693$

$ 42 = 4 \cdot 9 + 6 \Rightarrow 6 = 42 - 4 \cdot 9 =$

$693 - 7 \cdot 93$

$-\ 4 \cdot$

$ (15 \cdot 93 - 2 \cdot 693) $

$=$

$9 \cdot 693 - 67 \cdot 93 $

$ 9 = 1 \cdot 6 + 3 \Rightarrow 3 = 9 - 6 = $

$15 \cdot 93 - 2 \cdot 693 $

$-$

$ (9 \cdot 693 - 67 \cdot 93) $

$= 82 \cdot 93 - 11 \cdot 693 $

co kończy nasze wyliczenia $$ 3 = - 11 \cdot 693 + 82 \cdot 93 , \quad \textrm{czyli} \quad c = -11,\ d = 82.$$

Algorytm Euklidesa

Odwrócony algorytm Euklidesa

Oblicz \(\textrm{NWD}(a,n)\)

Wyznacz element odwrotny dla \(a\in\mathbb{Z}_n\)