Eulerova funkce

Z Wikipedie, otevřené encyklopedie

Eulerova funkce je významná funkce v teorii čísel. Značí se φ(n).

[editovat] Definice

\varphi(n): \mathbb Z_+ \mapsto \mathbb Z_+

kde φ(n) je počet všech celých čísel k v rozsahu 1\leq k \leq n takových, že NSD(k,n)=1. Ihned z definice jsou patrné následující vlastnosti:

  • φ(1) = 1,
  • φ(p) = p-1 pro p prvočíslo,
  • φ(pk) = pkpk − 1 pro p prvočíslo a k kladný celý exponent.

[editovat] Výpočet Eulerovy funkce

K výpočtu hodnoty Eulerovy funkce pro obecný argument n se používá následující tvrzení: nechť x,y jsou dvě kladná celá čísla taková, že NSD(x,y)=1. Pak

  • φ(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} (p_i^{k_i}-p_i^{k_i-1}) = n \prod_{1}^{m} (1 - \frac 1{p_i}).

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