Показник числа за модулем: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 25:
Якщо відомо розкладання модуля ''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>, а зведення в ступінь по модулю відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.
== Додатки ==
== Характери Діріхле ==
[[Характер (теория чисел)|Характер Діріхле]] <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>.
| |||