Показник числа за модулем: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 17:
* Якщо <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>.
* Якщо ''p'' — просте число, то група лишків <math>\mathbb{Z}_p^{\times}</math> [[Циклічна група|циклічна]] і тому, якщо <math>a=g^{dk}</math>, де ''g'' — твірна, <math>d\mid p-1</math>, а ''k'' взаємно просто із <math>p-1</math>, то <math>P(a)=\frac{p-1}{d}</math>. В закальному випадку для довільного модуля ''m'' можна вивести аналогічну формулу, користуючись теоремою про структуру [[мультипликативная группа кольца вычетов|мультиплікативної групи лишків]<math>\mathbb{Z}_m^{\times}</math>.
== Приклад ==
Так як <math>2^4\equiv 1\pmod{15}</math>, але <math>2^1\not\equiv 1\pmod{15}</math>, <math>2^2\not\equiv 1\pmod{15}</math>, <math>2^3\not\equiv 1\pmod{15}</math>, то порядок числа 2 по модулю 15 дорівнює 4.
== Обчислення ==
Якщо відомо розкладання модуля ''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>, а зведення в ступінь по модулю відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.
|