Показник числа за модулем

Показником, або мультиплікативним порядком, цілого числа a за модулем m називається найменше додатне ціле число $\ell$, таке, що

$a^{\ell }\equiv 1(\mathrm{mod}m).$

Показник визначений тільки для чисел a, взаємно простих за модулем m, тобто для елементів групи оборотних елементів кільця лишків за модулем m. При цьому, якщо показник числа a за модулем визначений, то він є дільником значення функції Ейлера $\phi (m)$ (наслідок теореми Лагранжа).

Щоб показати залежність показника $\ell$ від a і m, його також позначають $P_m(a)$, а якщо m фіксоване, то просто $P(a)$.

Властивості

• $a\equiv b(\mathrm{mod}m)\Rightarrow P(a)=P(b)$, тому можна вважати, що показник задано на класі лишків $\overline{a}$ за модулем m.
• $a^n\equiv 1(\mathrm{mod}m)\Rightarrow P(a)\mid n$. Зокрема, $P(a)\mid \lambda (m)$ и $P(a)\mid \phi (m)$, де $\lambda (m)$ — Шаблон:Не перекладено, а $\phi (m)$ — функція Ейлера.
• $a^t\equiv a^s(\mathrm{mod}m)\iff t\equiv s(\mathrm{mod}P(a)).$
• $P(a^s)\mid P(a)$; якщо $\gcd (s,P(a))=1$, то $P(a^s)=P(a).$
• Якщо p — просте число і $P(a)=k$, то $a,\dots ,a^k$ — всі розв'язки порівняння $x^k\equiv 1(\mathrm{mod}p)$.
• Якщо p — просте число, то $P(a)=p-1\iff a$ — твірна групи ${\mathbb{Z}}_p$.
• Якщо $\psi (k)$ — кількість класів лишків із показником $k$, то $\sum _{k\mid \phi (m)}\psi (k)=\phi (m)$. А для простих модулів навіть $\psi (k)=\phi (k)$.
• Якщо 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 }$.

Приклад

Оскільки $2^4\equiv 1(\mathrm{mod}15)$, але $2^1\equiv ̸1(\mathrm{mod}15)$, $2^2\equiv ̸1(\mathrm{mod}15)$, $2^3\equiv ̸1(\mathrm{mod}15)$, то порядок числа 2 за модулем 15 дорівнює 4.

Обчислення

Якщо відомий розклад модуля m на прості множники $p_j$ і відомий розклад чисел $p_j-1$ на прості множники, то показник заданого числа a може бути знайдений за поліноміальний час від $\ln m$. Для обчислення досить знайти розклад на множники функції Кармайкла $\lambda (m)$ і обчислити всі $a^{d}modm$ для всіх $d\mid \lambda (m)$. Оскільки число дільників обмежене многочленом від $\ln m$, а піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.

Застосування

Характери Діріхле

Характер Діріхле $\chi$ за модулем $m$ визначається обов'язковими співвідношеннями $\chi (ab)=\chi (a)\chi (b)$ і $\chi (a)=\chi (a+m)$. Щоб ці співвідношення виконувалися, необхідно, щоб $\chi (a)$ дорівнював якомусь комплексному кореню із одиниці степеня $P_m(a)$.

Див. також

• Дискретний логарифм
• Шаблон:Не перекладено

Посилання

• Шаблон:MathWorld