Modulo számsorrend

A modulo egész szám kitevője vagy szorzórendje az a legkisebb pozitív egész szám , amelyre [1] [2] $a$ $m$ $\ell$

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

A kitevő csak a modulushoz képest relatív prímszámokra van definiálva , vagyis a modulo maradékgyűrű invertálható elemei csoportjának elemeire . Sőt, ha a moduloszám kitevője definiálva van , akkor az osztója az Euler-függvény értékének ( a Lagrange-tétel következménye ) és a Carmichael-függvény értékének . $a$ $m$ $m$ $a$ $m$ $\varphi(m)$ $\lambda(m)$

Az indikátor és -től való függésének bemutatására szintén jelöljük , ha pedig rögzített, akkor egyszerűen . $\ell$ $a$ $m$ $P_m(a)$ $m$ $P(a)$

Tulajdonságok

$a\equiv b\pmod m\Jobbra P(a)=P(b)$ , tehát feltételezhetjük, hogy a kitevő adott a maradékok osztályán modulo . ${\bár {a}}$ $m$
$a^n\equiv 1\pmod m\Jobbra P(a)\mid n$ . Különösen és , ahol a Carmichael függvény és az Euler függvény . $P(a)\mid\lambda(m)$ $P(a)\mid\varphi(m)$ $\lambda(m)$ $\varphi(m)$
$a^t\equiv a^s\pmod m \Baljobbra nyíl t\equiv s\pmod{P(a)}.$
$P(a^s)\mid P(a)$ ; ha , akkor $\gcd(s,P(a))=1$ $P(a^s)=P(a).$
Ha egy prímszám és , akkor az összehasonlítás összes megoldása . $p$ $P(a)=k$ ${\displaystyle a,\;\ldots ,\;a^{k))$ $x^k\equiv 1\pmod p$
Ha prímszám, akkor a csoport generátora . $p$ $P(a)=p-1\Baljobbra nyíl a$ $\mathbb {Z} _{p}$
Ha a maradékosztályok száma az indikátorral , akkor . És még egyszerű modulokhoz is . $\psi(k)$ $k$ $\sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)$ $\psi(k)=\varphi(k)$
Ha egy prímszám, akkor a maradékcsoport ciklikus , és ezért, ha , ahol egy generátor, , és koprím -val , akkor . Általános esetben egy tetszőleges modulhoz hasonló képlet származtatható a multiplikatív maradékcsoport szerkezetére vonatkozó tétel segítségével . $p$ ${\mathbb {Z}}_{p}^{{\times }}$ $a=g^{dk}$ $g$ $d\közép p-1$ $k$ $p-1$ $P(a)=\frac{p-1}{d}$ $m$ ${\mathbb {Z}}_{m}^{{\times }}$

Példa

Mivel , de , , , akkor a 2 modulo 15 sorrendje 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}$

Számítás

Ha ismert a modul prímtényezőkre való bontása, és ismert a számok prímtényezőkre való bontása, akkor egy adott szám kitevője polinomidőben megtalálható -ból . A kiszámításhoz elegendő megtalálni a Carmichael-függvény faktorizációját, és kiszámítani az összeset . Mivel az osztók számát a polinom korlátozza , és a hatványozás modulo polinomiális időben történik, a keresési algoritmus polinom lesz. $m$ $p_{j}$ $p_j-1$ $a$ $\ln m$ $\lambda(m)$ $a^{d}\mod m$ $d\mid \lambda (m)$ $\ln m$

Alkalmazások

Dirichlet karakterei

A Dirichlet-karakter modulo -t a kötelező relációk és a . Ahhoz, hogy ezek a viszonyok fennmaradjanak, egyenlőnek kell lennie az egység valamilyen összetett gyökerével . $\chi$ $m$ $\chi(ab)=\chi(a)\chi(b)$ $\chi(a)=\chi(a+m)$ $\chi(a)$ $P_{m}(a)$

Modulo számsorrend

Tulajdonságok

Példa

Számítás

Alkalmazások

Dirichlet karakterei

Lásd még

Jegyzetek

Irodalom