Eulerova funkce

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

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

Značí se .

Definice[editovat | editovat zdroj]

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

  • ,
  • pro p prvočíslo,
  • pro p prvočíslo a m 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

.

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 .

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