Eulerova funkce

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

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

Definice

$\varphi: \mathbb{N}^{+} \mapsto \mathbb{N}^{+}$

φ(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:

• φ(1) = 1,
• φ(p) = p-1 pro p prvočíslo,
• φ($p^k$) = $(p-1).p^{k-1}$ pro p prvočíslo a k 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

φ(xy) = φ(x) · φ(y).

Toto tvrzení se dokazuje pomocí čínské věty o zbytcích.

Je patrné, že známe-li 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_{1}^{m} \varphi(p_i^{k_i}) = \prod_{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ě např. algoritmus polynomiální v $\log(n)$.

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