Eulerova funkce

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

Značí se \varphi(n).

Definice[editovat | editovat zdroj]

\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[editovat | editovat zdroj]

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_{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ě 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ý.