Modulo-numerojärjestys

Kokonaisluvun modulo eksponentti eli kertova järjestys on pienin positiivinen kokonaisluku siten, että [1] [2] $a$ $m$ $\ell$

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

Eksponentti määritellään vain luvuille , jotka ovat suhteellisen alkulukuja moduuliin nähden , eli jäännösrenkaan modulo käännettävien elementtien ryhmän elementeille . Lisäksi, jos moduuliluvun eksponentti on määritelty, niin se on Euler-funktion arvon ( Lagrangen lauseen seuraus ) ja Carmichael-funktion arvon jakaja . $a$ $m$ $m$ $a$ $m$ $\varphi(m)$ $\lambda(m)$

Osoittaaksesi indikaattorin riippuvuuden ja , se on myös merkitty , ja jos se on kiinteä, niin yksinkertaisesti . $\ell$ $a$ $m$ $P_m(a)$ $m$ $P(a)$

Ominaisuudet

$a\equiv b\pmod m\Rightarrow P(a)=P(b)$ , joten voimme olettaa, että eksponentti on annettu jäännösten luokassa modulo . ${\bar {a}}$ $m$
$a^n\equiv 1\pmod m\Rightarrow P(a)\mid n$ . Erityisesti ja , missä on Carmichael-funktio ja Euler -funktio . $P(a)\mid\lambda(m)$ $P(a)\mid\varphi(m)$ $\lambda(m)$ $\varphi(m)$
$a^t\equiv a^s\pmod m \Nuoli vasemmalle oikealle t\equiv s\pmod{P(a)}.$
$P(a^s)\mid P(a)$ ; jos , niin $\gcd(s,P(a))=1$ $P(a^s)=P(a).$
Jos on alkuluku ja , niin ovat kaikki vertailun ratkaisut . $s$ $P(a)=k$ ${\displaystyle a,\;\ldots ,\;a^{k))$ $x^k\equiv 1\pmod p$
Jos on alkuluku, niin se on ryhmän generaattori . $s$ $P(a)=p-1\nuoli vasemmalle oikealle a$ $\mathbb {Z} _{p}$
Jos on jäämäluokkien lukumäärä indikaattorilla , niin . Ja jopa yksinkertaisille moduuleille . $\psi(k)$ $k$ $\sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)$ $\psi(k)=\varphi(k)$
Jos on alkuluku, niin jäännösryhmä on syklinen , ja siksi, jos , jossa on generaattori, , Ja on coprime kanssa , Sitten . Yleisessä tapauksessa mielivaltaiselle moduulille voidaan johtaa samanlainen kaava käyttämällä lausetta kerrottavan jäännösryhmän rakenteesta . $s$ ${\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 }}$

Esimerkki

Koska , mutta , , , niin 2 modulo 15:n järjestys on 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}$

Laskenta

Jos tiedetään moduulin hajoaminen alkutekijöiksi ja lukujen hajoaminen alkutekijöiksi tiedetään, niin tietyn luvun eksponentti löytyy polynomiajassa alkaen . Laskemiseen riittää löytää Carmichael-funktion tekijöihin jako ja laskea kaikki kaikille . Koska jakajien lukumäärää rajoittaa :n polynomi ja eksponentiomoduuli tapahtuu polynomiajassa, hakualgoritmi on polynomi. $m$ $p_{j}$ $p_j-1$ $a$ $\ln m$ $\lambda(m)$ $a^{d}\mod m$ $d\mid \lambda (m)$ $\ln m$

Sovellukset

Dirichletin hahmot

Dirichlet-merkin modulo määritetään pakollisilla suhteilla ja . Jotta nämä suhteet pysyisivät voimassa, sen on oltava yhtä suuri kuin jokin monimutkainen ykseyden juuri . $\chi$ $m$ $\chi(ab)=\chi(a)\chi(b)$ $\chi(a)=\chi(a+m)$ $\chi(a)$ $P_{m}(a)$

Modulo-numerojärjestys

Ominaisuudet

Esimerkki

Laskenta

Sovellukset

Dirichletin hahmot

Katso myös

Muistiinpanot

Kirjallisuus