Eulerova funkce

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

Značí se $φ (n)$ .

Definice

φ : ℕ \to ℕ

$φ (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^{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) \cdot φ (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}} \cdot p_{2}^{k_{2}} \dots p_{m}^{k_{m}}

je hodnota Eulerovy funkce rovna

φ (n) = \prod_{i = 1}^{m} φ (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

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