Показником, або мультиплікативним порядком, цілого числа a за модулем m називається найменше додатне ціле число , таке, що
Показник визначений тільки для чисел a, взаємно простих за модулем m, тобто для елементів групи оборотних елементів кільця лишків за модулем m. При цьому, якщо показник числа a за модулем визначений, то він є дільником значення функції Ейлера (наслідок теореми Лагранжа).
Щоб показати залежність показника від a і m, його також позначають , а якщо m фіксоване, то просто .
Властивості , тому можна вважати, що показник задано на класі лишків за модулем m. . Зокрема, и , де — , а — функція Ейлера.
; якщо , то Якщо p — просте число і , то — всі розв'язки порівняння . Якщо p — просте число, то — твірна групи . Якщо — кількість класів лишків із показником , то . А для простих модулів навіть . Якщо p — просте число, то група лишків циклічна і тому, якщо , де g — твірна, , а k взаємно просте із , то . В загальному випадку для довільного модуля m можна вивести аналогічну формулу, користуючись теоремою про структуру мультиплікативної групи лишків .
Приклад Оскільки , але , , , то порядок числа 2 за модулем 15 дорівнює 4.
Обчислення Якщо відомий розклад модуля m на прості множники і відомий розклад чисел на прості множники, то показник заданого числа a може бути знайдений за поліноміальний час від . Для обчислення досить знайти розклад на множники функції Кармайкла і обчислити всі для всіх . Оскільки число дільників обмежене многочленом від , а піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.
Застосування Характери Діріхле Характер Діріхле за модулем визначається обов'язковими співвідношеннями і . Щоб ці співвідношення виконувалися, необхідно, щоб дорівнював якомусь комплексному кореню із одиниці степеня .
Див. також Дискретний логарифм
Посилання