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

• ${\displaystyle a\equiv b{\pmod {m}}\Rightarrow P(a)=P(b)}$, тому можна вважати, що показник задано на класі лишків ${\displaystyle {\bar {a}}}$ за модулем m.
• ${\displaystyle a^{n}\equiv 1{\pmod {m}}\Rightarrow P(a)\mid n}$. Зокрема, ${\displaystyle P(a)\mid \lambda (m)}$ и ${\displaystyle P(a)\mid \varphi (m)}$, де ${\displaystyle \lambda (m)}$ — функція Кармайкла, а ${\displaystyle \varphi (m)}$ — функція Ейлера.
• ${\displaystyle a^{t}\equiv a^{s}{\pmod {m}}\Leftrightarrow t\equiv s{\pmod {P(a)}}.}$
• ${\displaystyle P(a^{s})\mid P(a)}$; якщо ${\displaystyle \gcd(s,P(a))=1}$, то ${\displaystyle P(a^{s})=P(a).}$
• Якщо p — просте число і ${\displaystyle P(a)=k}$, то ${\displaystyle a,\ldots ,a^{k}}$ — всі розв'язки порівняння ${\displaystyle x^{k}\equiv 1{\pmod {p}}}$.
• Якщо p — просте число, то ${\displaystyle P(a)=p-1\Leftrightarrow a}$ — твірна групи ${\displaystyle \mathbb {Z} _{p}}$.
• Якщо ${\displaystyle \psi (k)}$ — кількість класів лишків із показником ${\displaystyle k}$, то ${\displaystyle \sum \limits _{k\mid \varphi (m)}\psi (k)=\varphi (m)}$. А для простих модулів навіть ${\displaystyle \psi (k)=\varphi (k)}$.
• Якщо p — просте число, то група лишків ${\displaystyle \mathbb {Z} _{p}^{\times }}$ циклічна і тому, якщо ${\displaystyle a=g^{dk}}$, де g — твірна, ${\displaystyle d\mid p-1}$, а k взаємно просте із ${\displaystyle p-1}$, то ${\displaystyle P(a)={\frac {p-1}{d}}}$. В загальному випадку для довільного модуля m можна вивести аналогічну формулу, користуючись теоремою про структуру мультиплікативної групи лишків ${\displaystyle \mathbb {Z} _{m}^{\times }}$.

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

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

• Дискретний логарифм
• Функція Кармайкла

• Weisstein, Eric W. Multiplicative Order(англ.) на сайті Wolfram MathWorld.