Modulo nummerordning

Exponenten , eller multiplikativ ordning , av ett heltalsmodulo är det minsta positiva heltal så att [1] [2] $a$ $m$ $\aln$

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

Exponenten definieras endast för tal relativt primtal till modulen , det vill säga för element i gruppen av inverterbara element i ringen av rester modulo . Dessutom, om exponenten för modulotalet är definierad, är det en divisor av värdet av Euler-funktionen (en konsekvens av Lagrangesatsen ) och värdet av Carmichael-funktionen . $a$ $m$ $m$ $a$ $m$ $\varphi(m)$ $\lambda(m)$

För att visa indikatorns beroende av och , betecknas den också , och om den är fixerad, då helt enkelt . $\aln$ $a$ $m$ $P_m(a)$ $m$ $P(a)$

Egenskaper

$a\equiv b\pmod m\Högerpil P(a)=P(b)$ , så vi kan anta att exponenten är given på klassen av rester modulo . ${\bar {a}}$ $m$
$a^n\equiv 1\pmod m\Högerpil P(a)\mid n$ . I synnerhet och , var är Carmichael-funktionen och är Euler-funktionen . $P(a)\mid\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)\mitt P(a)$ ; om , då $\gcd(s,P(a))=1$ $P(a^s)=P(a).$
Om är ett primtal och , då är alla lösningar av jämförelsen . $sid$ $P(a)=k$ ${\displaystyle a,\;\ldots ,\;a^{k))$ $x^k\equiv 1\pmod sid$
Om är ett primtal, då är en generator av gruppen . $sid$ $P(a)=p-1\vänsterhögerpil a$ $\mathbb {Z} _{p}$
Om är antalet restklasser med indikatorn , då . Och även för enkla moduler . $\psi(k)$ $k$ $\sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)$ $\psi(k)=\varphi(k)$
Om är ett primtal, då restgruppen är cyklisk , och därför, om , där är en generator, , och är coprime med , då . I det allmänna fallet, för en godtycklig modul , kan en liknande formel härledas med hjälp av satsen om strukturen för den multiplikativa restgruppen . $sid$ ${\mathbb {Z}}_{p}^{{\times }}$ $a=g^{dk}$ $g$ $d\mitt p-1$ $k$ $p-1$ $P(a)=\frac{p-1}{d}$ $m$ ${\mathbb {Z}}_{m}^{{\times }}$

Exempel

Eftersom , men , , , då är ordningen för 2 modulo 15 4. $2^4\equiv 1\pmod{15}$ $2^1\not\equiv 1\pmod{15}$ $2^2\not\equiv 1\pmod{15}$ $2^3\not\equiv 1\pmod{15}$

Beräkning

Om sönderdelningen av modulen till primtalsfaktorer är känd och sönderdelningen av tal till primtalsfaktorer är känd, kan exponenten för ett givet tal hittas i polynomtid från . För att beräkna räcker det att hitta faktoriseringen av Carmichael-funktionen och beräkna alla för alla . Eftersom antalet divisorer begränsas av polynomet , och exponentieringsmodulo inträffar i polynomtid, kommer sökalgoritmen att vara polynom. $m$ $p_{j}$ $p_j-1$ $a$ $\ln m$ $\lambda(m)$ $a^{d}\mod m$ $d\mid \lambda (m)$ $\ln m$

Applikationer

Karaktärer i Dirichlet

Dirichlet-tecknet modulo bestäms av de obligatoriska relationerna och . För att dessa relationer ska hålla är det nödvändigt att det är lika med någon komplex rot till enhet . $\chi$ $m$ $\chi(ab)=\chi(a)\chi(b)$ $\chi(a)=\chi(a+m)$ $\chi(a)$ $P_{m}(a)$

Modulo nummerordning

Egenskaper

Exempel

Beräkning

Applikationer

Karaktärer i Dirichlet

Se även

Anteckningar

Litteratur