Objednávka čísla modulu

Exponent nebo multiplikativní řád celého čísla modulo je nejmenší kladné celé číslo , takže [1] [2] $A$ $m$ $\ell$

a^{\ell }\equiv 1{\pmod {m)).

Exponent je definován pouze pro čísla relativně prvočíslá k modulu , tedy pro prvky skupiny invertibilních prvků kruhu zbytků modulo . Pokud je navíc definován exponent čísla modulo , pak je to dělitel hodnoty Eulerovy funkce (důsledek Lagrangeovy věty ) a hodnoty Carmichaelovy funkce . $A$ $m$ $m$ $A$ $m$ $\varphi(m)$ $\lambda(m)$

Pro znázornění závislosti indikátoru na a je také označen , a pokud je pevný, pak jednoduše . $\ell$ $A$ $m$ $P_m(a)$ $m$ $P(a)$

Vlastnosti

$a\equiv b\pmod m\šipka doprava P(a)=P(b)$ , takže můžeme předpokládat, že exponent je dán na třídě reziduí modulo . ${\bar {a}}$ $m$
$a^n\equiv 1\pmod m\Rightarrow P(a)\mid n$ . Zejména a , kde je Carmichaelova funkce a je Eulerova funkce . $P(a)\střed\lambda(m)$ $P(a)\mid\varphi(m)$ $\lambda(m)$ $\varphi(m)$
$a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.$
$P(a^s)\mid P(a)$ ; pokud , tak $\gcd(s,P(a))=1$ $P(a^s)=P(a).$
Jestliže je prvočíslo a , pak jsou všechna řešení srovnání . $p$ $P(a)=k$ ${\displaystyle a,\;\ldots ,\;a^{k))$ $x^k\ekviv 1\pmod str$
Jestliže je prvočíslo, pak je generátor skupiny . $p$ $P(a)=p-1\Šipka doleva a$ $\mathbb {Z} _{p}$
Jestliže je počet tříd reziduí s indikátorem , pak . A pro jednoduché moduly dokonce . $\psi(k)$ $k$ $\sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)$ $\psi(k)=\varphi(k)$
Jestliže je prvočíslo, pak skupina zbytků je cyklická , a proto, jestliže , kde je generátor, , a je společné s , pak . V obecném případě lze pro libovolný modul odvodit podobný vzorec pomocí věty o struktuře skupiny multiplikativních zbytků . $p$ ${\mathbb {Z}}_{p}^{{\times }}$ $a=g^{dk}$ $G$ $d\mid p-1$ $k$ $p-1$ $P(a)=\frac{p-1}{d}$ $m$ ${\mathbb {Z}}_{m}^{{\times }}$

Příklad

Protože , ale , , , pak řád 2 modulo 15 je 4. $2^4\ekviv 1\pmod{15}$ $2^1\not\ekviv 1\pmod{15}$ $2^2\not\ekviv 1\pmod{15}$ $2^3\ne\ekviv 1\pmod{15}$

Výpočet

Pokud je znám rozklad modulu na prvočinitele a je znám rozklad čísel na prvočinitele, pak lze exponent daného čísla nalézt v polynomiálním čase od . Pro výpočet stačí najít faktorizaci Carmichaelovy funkce a vypočítat all for all . Protože počet dělitelů je omezen polynomem , a umocňování modulo nastává v polynomiálním čase, bude vyhledávací algoritmus polynomiální. $m$ $p_{j}$ $p_j-1$ $A$ $\ln m$ $\lambda(m)$ $a^{d}\mod m$ $d\mid \lambda (m)$ $\ln m$

Aplikace

Postavy Dirichleta

Dirichletův charakter modulo je určen obligatorními vztahy a . Aby tyto vztahy vydržely, je nutné, aby se rovnaly nějakému komplexnímu kořenu jednoty . $\chi$ $m$ $\chi(ab)=\chi(a)\chi(b)$ $\chi(a)=\chi(a+m)$ $\chi(a)$ $P_{m}(a)$

Objednávka čísla modulu

Vlastnosti

Příklad

Výpočet

Aplikace

Postavy Dirichleta

Viz také

Poznámky

Literatura