Eulerova funkce

Graf Eulerovy funkce pro hodnoty od 1 do 1000

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

Značí se φ ( n ) {\displaystyle \varphi (n)} .

Definice

φ : N → N {\displaystyle \varphi :\mathbb {N} \to \mathbb {N} }

φ ( n ) {\displaystyle \varphi (n)} je počet všech přirozených čísel k takových, že 1 ≤ k ≤ n {\displaystyle 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 {\displaystyle \varphi (1)=1} ,
  • φ ( p ) = p − 1 {\displaystyle \varphi (p)=p-1} pro p prvočíslo,
  • φ ( p m ) = ( p − 1 ) ⋅ p m − 1 {\displaystyle \varphi (p^{m})=(p-1)\cdot p^{m-1}} pro p prvočíslo a m 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

φ ( x y ) = φ ( x ) ⋅ φ ( y ) {\displaystyle \varphi (xy)=\varphi (x)\cdot \varphi (y)} .

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

Je patrné, že je-li znám rozklad argumentu n na prvočísla:

n = p 1 k 1 ⋅ p 2 k 2 ⋯ p m k m {\displaystyle n=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdots p_{m}^{k_{m}}}

je hodnota Eulerovy funkce rovna

φ ( n ) = ∏ i = 1 m φ ( p i k i ) = ∏ i = 1 m ( ( p i − 1 ) p i k i − 1 ) . {\displaystyle \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ě algoritmus polynomiální.

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

Související články

Externí odkazy

  • Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Eulerova funkce na Wikimedia Commons