Eukleidův algoritmus: Porovnání verzí

Přidáno 138 bajtů ,  před 7 lety
m
Opravena poznámka o derivaci a kořenech polynomu ...
m (Editace uživatele 195.113.220.129 (diskuse) vráceny do předchozího stavu, jehož autorem je Zagothal)
m (Opravena poznámka o derivaci a kořenech polynomu ...)
 
* Na základě tohoto algoritmu lze rychle spočítat [[inverzní prvek]] k násobení v [[modulární aritmetika|modulární aritmetice]]. Největší společný dělitel dvou čísel se dá vyjádřit [[Bézoutova rovnost|Bézoutovou rovností]] jako součet násobků těchto čísel. Pokud je tímto největším společným dělitelem 1, pak dostaneme součin prvku a jeho inverzního. Tedy pokud máme spočítat inverzní prvek ''x'' modulo ''n'' a vyjde nám vyjádření největšího společného dělitele Bézoutovou rovností ''ax''+''bn''=1, kde známe všechny proměnné. Máme tak vlastně přímo rovnost ''ax''=1 [[modulo]] ''n'' a nalezené ''a'' je hledaný inverzní prvek. Tento výpočet inverzního prvku je častý v aplikacích [[teorie čísel]], zejména v [[kryptografie|kryptografii]].
* Tento algoritmus lze použít nejen pro čísla, ale také pro [[polynom]]y. ZaPolynom pomocíje derivaces lzejeho takvyužitím najítmožno polynomrozdělit obsahujícína stejnésoučin polynomů oddělených dle násobnosti kořenů. Derivace snižuje násobnost každého kořene o 1 a zavádí nové kořeny. jakoNejvětší původní,společný aledělitel každýs kořenpůvodním jepolynomem zdeodstraňuje jednoduchýnové kořeny. Například lze tak zjistit kořeny polynomu (x-a)(x-a)(x-a)(x-b)(x-b), přestože neexistuje algoritmus na výpočet kořenů polynomu stupně většího než 4.
* Tento algoritmus je jeden z těch, u nichž není znám způsob paralelního zpracování, který by podstatně zvýšil výpočetní rychlost.
 
220

editací