Eulerova funkce
Z Wikipedie, otevřené encyklopedie
Eulerova funkce je významná funkce v teorii čísel. Značí se φ(n).
[editovat] Definice
kde φ(n) je počet všech celých čísel k v rozsahu 
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) = pk − pk − 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:
je hodnota Eulerovy funkce rovna
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ý.
