Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 04. 06. 2015 11:52
Rozšířený euklidův algoritmus
Ahoj,
sice mi to zabralo, ale celkem celý algoritmus chápu a vyšlo mi několik příkladů. Mám jen jeden dotaz. Když budu mít nějaká velké číslo a (dejme tomu 9 cifer a víc) v modulo světě obdobně velkého čísla a budu hledat hledat inverzi tohoto velkého čísla a (ručně), tak bude mít celý výpočet klidně i desítky řádek jestli to chápu správně. Je to tak? Nic jako obecná formule do které dosadím a mám výsledek neexistuje. Že? Vždy musím dělat celý algoritmus?
Pak je to tedy především vhodné pro počítač, který si to rekurzivně vyřeší. A není to moc vhodné na ruční počítání velkých čísel. Chápu to správně?
Díky za ujištění. :-)
Offline
#2 04. 06. 2015 12:39
Re: Rozšířený euklidův algoritmus
Ahoj,
přímo to nijak nelze, Euklidův algoritmus pro nalezení inverzí se, myslím, skutečně používá v RSA algoritmu pro šifrování. Pokud si dobře pamatuju, inverz jde taky počítat pomocí Eulerovy věty, ale zřejmě to není tak efektivní.
Zde můžeš najít docela podrobnou analýzu výpočetní složitosti Euklidova algoritmu. Pokud jsem to po zběžném přečtení správně pochopil, píše se tam, že počet potřebných kroků (dělení) je až na konstantu roven počtu cifer menšího čísla, čili logaritmická složitost (což je pro počítače jako nic skoro při libovolně velkém vstupu). Zajímavá mi přišla informace, že pokud nastane nejhorší případ (co nejmenší čísla a co největší počet kroků), tak ty čísla jsou po sobě jdoucí Fibonacciho čísla.
Offline