Eulerova funkce

Technology

12 hours ago

Author

Albert Flores

Graf Eulerovy funkce pro hodnoty od 1 do 1000 Eulerova funkce je významná funkce v teorii čísel.

Značí se \varphi(n).

Definice

:\varphi: \mathbb{N} \to \mathbb{N}

\varphi(n) je počet všech přirozených čísel k takových, že 1\leq k \leq n a NSD(k,n)=1, tedy k a n jsou nesoudělná čísla. Ihned z definice jsou patrné následující vlastnosti:

* \varphi(1) = 1, * \varphi(p) = p-1 pro p prvočíslo, * \varphi(p^m) = (p-1)\cdot p^{m-1} 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 :\varphi(xy) = \varphi(x)\cdot\varphi(y). Toto tvrzení se dokazuje pomocí čínské věty o zbytcích.

Je patrné, že je-li znám rozklad argumentu n na prvočísla:

:n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}

je hodnota Eulerovy funkce rovna

:\varphi(n) = \prod_{i=1}^{m} \varphi(p_i^{k_i}) = \prod_{i=1}^{m} ((p_i - 1)p_i^{k_i-1}).

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ý.