Матеріал з Вікіпедії — вільної енциклопедії.
Показником , або мультиплікативним порядком , цілого числа a за модулем m називається найменше додатне ціле число
ℓ
{\displaystyle \ell }
a
ℓ
≡
1
(
mod
m
)
.
{\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}
Показник визначений тільки для чисел a , взаємно простих за модулем m , тобто для елементів групи оборотних елементів кільця лишків за модулем m . При цьому, якщо показник числа a за модулем визначений, то він є дільником значення функції Ейлера
φ
(
m
)
{\displaystyle \varphi (m)}
теореми Лагранжа ).
Щоб показати залежність показника
ℓ
{\displaystyle \ell }
a і m , його також позначають
P
m
(
a
)
{\displaystyle P_{m}(a)}
m фіксоване, то просто
P
(
a
)
{\displaystyle P(a)}
a
≡
b
(
mod
m
)
⇒
P
(
a
)
=
P
(
b
)
{\displaystyle a\equiv b{\pmod {m}}\Rightarrow P(a)=P(b)}
a
¯
{\displaystyle {\bar {a}}}
m .
a
n
≡
1
(
mod
m
)
⇒
P
(
a
)
∣
n
{\displaystyle a^{n}\equiv 1{\pmod {m}}\Rightarrow P(a)\mid n}
P
(
a
)
∣
λ
(
m
)
{\displaystyle P(a)\mid \lambda (m)}
P
(
a
)
∣
φ
(
m
)
{\displaystyle P(a)\mid \varphi (m)}
λ
(
m
)
{\displaystyle \lambda (m)}
функція Кармайкла [en]
φ
(
m
)
{\displaystyle \varphi (m)}
функція Ейлера .
a
t
≡
a
s
(
mod
m
)
⇔
t
≡
s
(
mod
P
(
a
)
)
.
{\displaystyle a^{t}\equiv a^{s}{\pmod {m}}\Leftrightarrow t\equiv s{\pmod {P(a)}}.}
P
(
a
s
)
∣
P
(
a
)
{\displaystyle P(a^{s})\mid P(a)}
gcd
(
s
,
P
(
a
)
)
=
1
{\displaystyle \gcd(s,P(a))=1}
P
(
a
s
)
=
P
(
a
)
.
{\displaystyle P(a^{s})=P(a).}
Якщо p — просте число і
P
(
a
)
=
k
{\displaystyle P(a)=k}
a
,
…
,
a
k
{\displaystyle a,\ldots ,a^{k}}
x
k
≡
1
(
mod
p
)
{\displaystyle x^{k}\equiv 1{\pmod {p}}}
Якщо p — просте число, то
P
(
a
)
=
p
−
1
⇔
a
{\displaystyle P(a)=p-1\Leftrightarrow a}
твірна групи
Z
p
{\displaystyle \mathbb {Z} _{p}}
Якщо
ψ
(
k
)
{\displaystyle \psi (k)}
k
{\displaystyle k}
∑
k
∣
φ
(
m
)
ψ
(
k
)
=
φ
(
m
)
{\displaystyle \sum \limits _{k\mid \varphi (m)}\psi (k)=\varphi (m)}
простих модулів навіть
ψ
(
k
)
=
φ
(
k
)
{\displaystyle \psi (k)=\varphi (k)}
Якщо p — просте число, то група лишків
Z
p
×
{\displaystyle \mathbb {Z} _{p}^{\times }}
циклічна і тому, якщо
a
=
g
d
k
{\displaystyle a=g^{dk}}
g — твірна,
d
∣
p
−
1
{\displaystyle d\mid p-1}
k взаємно просте із
p
−
1
{\displaystyle p-1}
P
(
a
)
=
p
−
1
d
{\displaystyle P(a)={\frac {p-1}{d}}}
m можна вивести аналогічну формулу, користуючись теоремою про структуру мультиплікативної групи лишків
Z
m
×
{\displaystyle \mathbb {Z} _{m}^{\times }}
Оскільки
2
4
≡
1
(
mod
15
)
{\displaystyle 2^{4}\equiv 1{\pmod {15}}}
2
1
≢
1
(
mod
15
)
{\displaystyle 2^{1}\not \equiv 1{\pmod {15}}}
2
2
≢
1
(
mod
15
)
{\displaystyle 2^{2}\not \equiv 1{\pmod {15}}}
2
3
≢
1
(
mod
15
)
{\displaystyle 2^{3}\not \equiv 1{\pmod {15}}}
Якщо відомий розклад модуля m на прості множники
p
j
{\displaystyle p_{j}}
p
j
−
1
{\displaystyle p_{j}-1}
a може бути знайдений за поліноміальний час від
ln
m
{\displaystyle \ln m}
λ
(
m
)
{\displaystyle \lambda (m)}
a
d
mod
m
{\displaystyle a^{d}\mod m}
d
∣
λ
(
m
)
{\displaystyle d\mid \lambda (m)}
ln
m
{\displaystyle \ln m}
піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.
Характер Діріхле
χ
{\displaystyle \chi }
m
{\displaystyle m}
χ
(
a
b
)
=
χ
(
a
)
χ
(
b
)
{\displaystyle \chi (ab)=\chi (a)\chi (b)}
χ
(
a
)
=
χ
(
a
+
m
)
{\displaystyle \chi (a)=\chi (a+m)}
χ
(
a
)
{\displaystyle \chi (a)}
P
m
(
a
)
{\displaystyle P_{m}(a)}
