náhled|Graf Eulerovy funkce pro hodnoty od 1 do 1000 Eulerova funkce je významná funkce v teorii čísel.
Značí se .
Definice
je počet všech přirozených čísel k takových, že a , tedy k a n jsou nesoudělná čísla. Ihned z definice jsou patrné následující vlastnosti:
, pro p prvočíslo, pro p prvočíslo a m kladný celý exponent.
Výpočet Eulerovy funkce K výpočtu hodnoty Eulerovy funkce pro obecný argument n se používá následující vlastnost (multiplikativnost): Nechť x,y jsou dvě nesoudělná celá kladná čísla, potom . Toto tvrzení se dokazuje pomocí čínské věty o zbytcích.
Je patrné, že je-li znám rozklad argumentu n na prvočísla:
je hodnota Eulerovy funkce rovna
Naproti tomu není známo, zda lze Eulerovu funkci efektivně spočítat bez znalosti rozkladu argumentu na prvočísla; efektivní algoritmus znamená v tomto případě algoritmus polynomiální.
Objev prakticky využitelného algoritmu pro výpočet Eulerovy funkce bez znalosti rozkladu argumentu by měl ničivé důsledky pro bezpečnost šifry RSA, neboť s jeho pomocí by každý byl schopen dopočítat z veřejného klíče klíč soukromý.
Související články Eulerova věta RSA Největší společný dělitel Malá Fermatova věta Carmichaelova funkce
Externí odkazy
Kategorie:Multiplikativní funkce Funkce, Eulerova