Показник числа за модулем: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м Lxlalexlxl перейменував сторінку з Показник числа по модулю на Показник числа за модулем: Правопис |
Немає опису редагування |
||
Рядок 1:
'''Показником''', або '''мультиплікативним порядком''', [[Цілі числа|цілого числа]] ''a'' [[Модульна арифметика|за модулем]] ''m'' називається найменше додатне ціле число <math>\ell</math>, таке, що
: <math>a^\ell \equiv 1\pmod m.</math>
Рядок 10:
* <math>a^n\equiv 1\pmod m\Rightarrow P(a)\mid n</math>. Зокрема, <math>P(a)\mid\lambda(m)</math> и <math>P(a)\mid\varphi(m)</math>, де <math>\lambda(m)</math> — {{не перекладено|функція Кармайкла||en|Carmichael function}}, а <math>\varphi(m)</math> — [[функція Ейлера]].
* <math>a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.</math>
* <math>P(a^s)\mid P(a)</math>;
* Якщо ''p'' — [[просте число]] і <math>P(a)=k</math>, то <math>a,\ldots,a^k</math> — всі розв'язки порівняння <math>x^k\equiv 1\pmod p</math>.
* Якщо ''p'' — просте число, то <math>P(a)=p-1\Leftrightarrow a</math> — [[Первісний корінь|твірна]] групи <math>\mathbb{Z}_p</math>.
* Якщо <math>\psi(k)</math> — кількість класів лишків із показником <math>k</math>, то <math>\sum\limits_{k\mid\varphi(m)}\psi(k)=\varphi(m)</math>. А для простих модулів навіть <math>\psi(k)=\varphi(k)</math>.
Рядок 22:
Якщо відомий розклад модуля ''m'' на прості множники <math>p_j</math> і відомий розклад чисел <math>p_j-1</math> на прості множники, то показник заданого числа ''a'' може бути знайдений за поліноміальний час від <math>\ln m</math>. Для обчислення досить знайти розклад на множники функції Кармайкла <math>\lambda(m)</math> і обчислити всі <math>a^d \mod m</math> для всіх <math>d\mid \lambda (m)</math>. Оскільки число дільників обмежене многочленом від <math>\ln m</math>, а піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.
== Застосування ==
=== Характери Діріхле ===
{{не перекладено|Характер Діріхле||ru|Характер (теория чисел)}} <math>\chi</math> за модулем <math>m</math> визначається обов'язковими співвідношеннями <math>\chi(ab)=\chi(a)\chi(b)</math> і <math>\chi(a)=\chi(a+m)</math>. Щоб ці співвідношення виконувалися, необхідно, щоб <math>\chi(a)</math> дорівнював якомусь комплексному кореню із одиниці степеня <math>P_{m}(a)</math>.
== Див. також ==
| |||