Eulerova funkce

Graf Eulerovy funkce pro hodnoty od 1 do 1000

Eulerova funkce je významná funkce v teorii čísel.

Značí se $\phi (n)$.

Definice

$\phi :\mathbb{N}\to \mathbb{N}$

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

• $\phi (1)=1$,
• $\phi (p)=p-1$ pro p prvočíslo,
• $\phi (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

$\phi (xy)=\phi (x)\cdot \phi (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

$\phi (n)=\prod _{i=1}^m\phi (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ý.

Související články

• Eulerova věta
• RSA
• Největší společný dělitel
• Malá Fermatova věta
• Carmichaelova funkce

Externí odkazy

• Šablona:Commonscat