УказательРазделыОбозначенияАвторО проекте


§

Сложность материалов раздела — повышенная. Для их понимания неплохо было бы просмотреть материалы раздела МОДУЛЯРНАЯ АРИФМЕТИКА.


Индекс (дискретный логарифм)

Первообразный корень

Задача. Найти длину цикла последовательности \{A^j \pmod{M} \}_{j=0}^{\infty} .

Для случая простого модуля верхняя оценка для длины цикла дается теоремой Ферма:

Т

Теорема [Ферма (малая)]. Если p_{} простое и A_{} не делится на p_{}, то

A^{p-1} \equiv 1 \pmod{p} \ .

Примеры показывают, что для некоторых A_{} эта оценка достигается, а для других может быть уменьшена:

\begin{array}{ccl} \left\{3^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 3,\, 9,\,10,\, 13,\, 5,\,15,\,11,\,16,\,14,\,8,\,7,\,4,\,12,\,2,\,6,\,1,\dots ; \\ \left\{4^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 4,\,16,\, 13,\, 1,\,4,\dots ; \\ \left\{13^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\,13,\, 16,\, 4,\, 1,\, 13 , \, 16,\, 4,\, 1,\, 13,\, 16,\dots ; \\ \left\{16^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\,16,\, 1,\,16,\, 1,\, 16,\,1,\dots \end{array}
Т

Теорема 1. Если число A_{} не делится на простое p>2, то

{ . } либо A^{(p-1)/2} \equiv 1 \pmod{p} \ , \quad либо A^{(p-1)/2} \equiv -1 \pmod{p} \ .

Доказательство. Поскольку p_{} — нечетное, то (p-1)_{} — четное. Имеем

A^{p-1} -1 =\left( A^{(p-1)/2} -1 \right) \left( A^{(p-1)/2} +1 \right) \ .

По теореме Ферма левое число делится на p_{}, следовательно (по теореме 2 ЗДЕСЬ ), по крайней мере один из сомножителей справа должен делиться на простое p_{}.

П

Пример. Для p=17 имеем:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline A^{(p-1)/2}\pmod{p} & 1 & 1 & -1 & 1 & -1 & -1 & -1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & 1 & 1 \\ \hline \end{array}

Видим, что половина чисел \{ 1, 2,\dots, 16 \} при отображении A^{8} \pmod{17} переходит в 1_{}, а половина — в 16 \equiv -1 \pmod{17}. Ниже будет показано, что выявленная закономерность справедлива для любого простого p_{}.

Предыдущий результат допускает обобщение, которое предварим определением.

Чётностью целого числа A_{} называется показатель степени 2_{} в каноническом разложении этого числа1):

\operatorname{prt}(A)=r \quad \iff \quad A делится на \ 2^r, но не делится на 2^{r+1} \quad \iff \quad A=2^rA_1, где \ A_1 - нечетное \ .
П

Пример. \operatorname{prt}(A)=0 \ \iff \ A — нечетное; \operatorname{prt}(28)=2, \operatorname{prt}(128)=7, \operatorname{prt}(368)= \qquad .

Т

Теорема 2. Пусть число p>2 простое и \operatorname{prt}(p-1)=r, т.е. p-1=2^rq, где q_{}нечетное. Если число A_{} не делится на p_{}, то

{ . } либо \ A^{q} \equiv 1 \pmod{p} \ , \quad либо \ A^{2^jq} \equiv -1 \pmod{p}

для некоторого j\in \{0,1,\dots,r-1 \}.

Доказательство.

\begin{array}{rcl} A^{p-1} -1 &=&\left( A^{(p-1)/2} +1 \right)\left( A^{(p-1)/2} -1 \right) = \\ &=&\left( A^{2^{r-1}q} +1 \right)\left( A^{2^{r-1}q} -1 \right)= \\ &=&\left( A^{2^{r-1}q} +1 \right)\left( A^{2^{r-2}q} +1 \right) \left( A^{2^{r-2}q} -1 \right) =\\ &=&\dots = \left( A^{2^{r-1}q} +1 \right)\times \dots \times \left(A^{2q}+1 \right) \left(A^q+1 \right)\left(A^q-1 \right) \ . \end{array}

Завершается доказательство теми же рассуждениями, что и доказательство теоремы 1.

П

Пример. Для p=41 имеем: r=\operatorname{prt}(40)=3,\ q=5 и

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline A^{q} \pmod{p} & 1 & & & -1 & & & & & & 1 & & & \\ \hline A^{2q} \pmod{p} & & -1 & & & -1 & & & -1 & -1 & & & & \\ \hline A^{4q} \pmod{p} & & & -1 & & & -1 & -1 & & & & -1 & -1 & -1 \\ \hline \end{array}

Наименьшее k_{}\in \mathbb N, удовлетворяющее сравнению {A^k\equiv 1 \pmod{M}}, называется порядком или показателем числа A_{} по модулю M_{}. В случае, когда в контексте M_{} считается фиксированным, слова «по модулю M_{}» опускают, и тогда порядок A_{} обозначают \operatorname{ord}(A):

A^{\operatorname{ord}(A)}\equiv 1 \pmod{M},\ A^{\ell} \not\equiv 1 \pmod{M} \ npu \ \forall \ell\in \{1,\dots,\operatorname{ord}(A) -1 \} \ .
П

Пример. При M=17:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline \operatorname{ord} & 1 & 8 & 16 & 4 & 16 & 16 & 16 & 8 & 8 & 16 & 16 & 16 & 4 & 16 & 8 & 2\\ \hline \end{array}

При M=20 имеем:

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 3 & 7 & 9 & 11 & 13 & 17 & 19 \\ \hline \operatorname{ord} & 1 & 4 & 4 & 2 & 2 & 4 & 4 & 2 \\ \hline \end{array}

Т

Теорема 3. Если A^n \equiv 1 \pmod{M}, то n_{} делится на \operatorname{ord} (A). В частности, \phi(M) делится на \operatorname{ord}(A) для любого A_{} такого, что \operatorname{HOD}(A,M)=1.

Доказательство. Действительно, предположим, что не существует чисел \ell\in \mathbb N, \ell< \operatorname{ord} (A) таких, что A^{\ell}\equiv 1 \pmod{M}, но тем не менее что n_{} имеет ненулевой остаток при делении на \operatorname{ord} (A): n=\operatorname{ord} (A) \cdot q +r, \ 0<r<\operatorname{ord} (A). Тогда

1\equiv_{_M} A^{n} = \left( A^{\operatorname{ord} (A)} \right)^qA^r \equiv_{_M} A^r \ ,

и, следовательно, число \operatorname{ord} (A) не является минимальным показателем степени числа A_{}, сравнимой с единицей по модулю M_{}. Мы пришли к противоречию с определением \operatorname{ord} (A). Второе утверждение теоремы следует из первого и теоремы Эйлера.

=>

Для любого A_{} и n_{}>1 число \phi (A^n-1) делится на n_{}.

Доказательство. Число A_{} взаимно просто с числом M=A^n-1 и имеет порядок n_{} по модулю M_{} . Действительно, A^n \equiv 1 \pmod{A^n-1}, но A^k-1 не делится на A^n-1 при k<n. Применяем теорему 3.

Итак, решение задачи, поставленной в начале пункта — об оценке длины цикла последовательности \{A^j \pmod{M} \}_{j=0}^{\infty} — сводится к задаче определения \operatorname{ord} (A), последнее число следует искать среди делителей \phi(M). Для простого модуля M=p>2 одним из таких делителей числа \phi(p)=p-1 является 2_{}, и этот факт проявился в теореме 1. Очевидно, что при p>3 может существовать и делитель q\ne 2 числа p-1, что позволяет предполагать существование числа A\in \{1,2,\dots,p-1 \}, имеющего порядок равный q_{}.

Т

Теорема 4. Если число q_{} является делителем числа p-1, то среди чисел

1,2,\dots,p-1

существует ровно q_{} чисел, удовлетворяющих сравнению

A^q \equiv 1 \pmod{p} \ .

Доказательство. Теорема Ферма утверждает, что сравнение

x^{p-1}-1 \equiv 0 \pmod{p}

имеет p-1 решений: именно все числа x\in\{1,2,\dots,p-1\}. Поскольку p-1 четно, то

x^{p-1}-1=\left( x^{(p-1)/2} -1 \right) \left( x^{(p-1)/2} +1 \right) \ ,

и из теоремы 3 раздела РЕШЕНИЕ НЕЛИНЕЙНЫХ СРАВНЕНИЙ следует, что половина из чисел \{1,2,\dots,p-1\} удовлетворяет сравнению x^{(p-1)/2} \equiv 1 \pmod{p}, а половина — сравнению x^{(p-1)/2} \equiv -1 \pmod{p}. Далее, если число q>2 — произвольный делитель числа p-1, то

x^{p-1}-1=\left( x^q -1 \right) \left( x^{(p-1)/q}+x^{(p-1)/q-1} + \dots + x +1 \right) \ ,

и на основании той же теоремы сравнению x^{q} \equiv 1 \pmod{p} удовлетворяет ровно q_{} чисел множества \{1,2,\dots,p-1\}.

Выясним теперь вопрос о существовании цикла максимально возможной длины.

Число \Lambda называется первообразным корнем2) по модулю M_{}, если \operatorname{ord} (\Lambda)=\phi(M).

§

Это определение сходно по смыслу с определением первообразного комплексного корня из единицы. В самом деле, первообразный корень из единицы степени n_{} определяется как такое решение уравнения z^n-1=0, которое не является решением уравнения z^k-1 = 0 при \forall k \in \{1,\dots,n-1\}. Первообразный корень по модулю определяется как решение сравнения z^{\phi(M)}-1 \equiv 0 \pmod{M}, которое не является решением сравнения z^k-1 \equiv 0 \pmod{M} при \forall k \in \{1,\dots,\phi(M)-1\}.

Для простого модуля M=p>2 число \Lambda является первообразным корнем тогда и только тогда, когда \operatorname{ord} (\Lambda)=p-1.

П

Пример. Согласно таблице приведенного выше примера первообразными корнями по модулю 17_{} будут числа 3,\, 5,\, 6,\, 7,\, 10,\, 11, 12, 14 . Тот же пример показывает, что для модуля M=20 первообразных корней не существует.

Оказывается, что для простого модуля M=p>2 первообразный корень всегда существует. Как проверить, что число \Lambda является первообразным корнем по модулю p_{} ? На первый взгляд, кажется, что нужно проверить выполнение условия \Lambda^q \not\equiv 1 \pmod{p} для каждого делителя q_{} числа p-1. Так, при p=37 эта проверка заключается в:

\Lambda^2 \not\equiv 1 ,\ \Lambda^3 \not\equiv 1,\ \Lambda^4 \not\equiv 1,\ \Lambda^6 \not\equiv 1,\ \Lambda^{12} \not\equiv 1,\ \Lambda^{18} \not\equiv 1 \pmod{37} \ .

На самом же деле, достаточно проверить всего два из этих условий:

\Lambda^{12} \not\equiv 1,\ \Lambda^{18} \not\equiv 1 \pmod{37} \ ,

поскольку для удовлетворяющего им числа \Lambda все остальные условия также будут выполнены. Эти рассуждения обобщаются следующим утверждением.

Т

Теорема 5. Если каноническое разложение числа p-1 имеет вид:

p-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ ,

то для того чтобы число \Lambda, не делящееся на p_{}, было первообразным корнем по модулю p_{}, необходимо и достаточно, чтобы

\Lambda^{(p-1)/p_j} \not\equiv 1 \pmod{p} \quad npu \quad \forall j\in \{1,\dots, \mathfrak r\} \ .

Доказательство. Необходимость следует из определения первообразного корня.

Достаточность. Предположим, что условия теоремы выполнены, но, тем не менее, существует число k\in \{1,2,\dots,p-2 \} такое, что \Lambda^k \equiv 1 \pmod{p}. Тогда, по теореме 3, число p-1 должно делиться на k_{}; тогда приведенная ЗДЕСЬ теорема 4 гарантирует, что хотя бы одно из чисел (p-1)/p_j делится на k_{}: (p-1)/p_j=kq. Имеем

\Lambda^{(p-1)/p_j}=\left(\Lambda^{k} \right)^q \equiv 1 \pmod{p} \ ,

что противоречит условиям теоремы. Итак, \Lambda^k \not\equiv 1 \pmod{p} ни для какого показателя k_{}, меньшего p-1, и, значит, число \Lambda является первообразным корнем по модулю p_{}.

П

Пример. Является ли число: а) \Lambda=2, б) \Lambda=6, первообразным корнем по модулю 41 ?

Решение. Имеем 41-1=40=2^3\cdot 5. Проверяем условия теоремы. Для \Lambda=2 одно из них не выполнено:

2^{20}=1024^2\equiv_{_{41}} 40^2 \equiv_{_{41}} (-1)^2 = 1 \ .

Для \Lambda=6:

6^{20}=2^{20}\cdot 3^{20} \equiv_{_{41}} 3^{20} =\left(3^4 \right)^5 \equiv_{_{41}} (-1)^5=-1 \ , \ 6^8 \equiv_{_{41}} 10 \ ,

т.е. оба условия выполняются.

Ответ. а) нет, б) да.

Т

Теорема 6. Для того чтобы число A_{} одновременно удовлетворяло сравнениям

A^{q_1} \equiv 1 \pmod{p}, \dots , A^{q_k} \equiv 1 \pmod{p} \ ,

необходимо и достаточно, чтобы оно удовлетворяло сравнению

A^{\operatorname{HOD}(q_1,\dots,q_k)} \equiv 1 \pmod{p} \ .

Доказательство. Достаточность очевидна:

A^{n} \equiv 1 \pmod{p} \ \Rightarrow \ A^{nt} \equiv 1 \pmod{p} \quad npu \quad \forall t \in \mathbb N \ .

Необходимоcть. Если число A_{} удовлетворяет сравнению A^{q} \equiv 1 \pmod{p}, то, по теореме 3, число q_{} делится на \operatorname{ord}(A). Если A_{} удовлетворяет сравнениям из теоремы, то \operatorname{ord}(A) будет делителем всех q_1,\dots,q_k, и, следовательно, делителем \operatorname{HOD}(q_1,\dots,q_k).

Т

Теорема 7 [Гаусс]. По любому простому модулю p>2 существует ровно \phi(p-1) первообразных корней во множестве \{1,\dots,p-1\}.

Доказательство. Если каноническое разложение числа p-1 задается формулой

p-1=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ ,

то по теореме 5 первообразными корнями по модулю p_{} среди чисел множества \{1,\dots,p-1\} будут те и только те, что не удовлетворяют ни одному из сравнений

A^{(p-1)/p_1} \equiv 1 \pmod{p} \, , \dots , \ A^{(p-1)/p_{\mathfrak r}} \equiv 1 \pmod{p} \ .

Обозначим через:

  • N_j — количество чисел множества \{1,\dots,p-1\}, удовлетворяющих j_{}-му сравнению;
  • N_{j_1j_2} — количество чисел множества \{1,\dots,p-1\}, удовлетворяющих одновременно j_1-му и j_2-му сравнениям;
  • и т.д.;
  • N_{1,2,\dots,\mathfrak r} — количество чисел множества \{1,\dots,p-1\}, удовлетворяющих одновременно всем сравнениям.

На основании теорем 4 и 6 имеем

N_j=\frac{p-1}{p_j},\ N_{j_1j_2}=\operatorname{HOD} \left( \frac{p-1}{p_{j_1}} \, , \, \frac{p-1}{p_{j_2}} \right) =\frac{p-1}{p_{j_1}p_{j_2}} \ , \, \dots ,
N_{1,2,\dots,{\mathfrak r}}= \frac{p-1}{p_1p_2\times \dots \times p_{\mathfrak r}} \ .

Тогда теорема включений-исключений утверждает, что количество чисел множества \{1,\dots,p-1\}, не удовлетворяющих ни одному из сравнений, равно

(p-1) - \sum_{1\le j\le{\mathfrak r}} \frac{p-1}{p_j} +\sum_{1\le j_1 < j_2 \le {\mathfrak r}} \frac{p-1}{p_{j_1}p_{j_2}} - \dots +
+(-1)^{\mathfrak r} \frac{p-1}{p_1p_2\times \dots \times p_{\mathfrak r}} =
=(p-1)\left(1-\frac{1}{p_1} \right)\left(1-\frac{1}{p_2} \right) \times \dots \times \left(1-\frac{1}{p_{\mathfrak r}} \right) \ = \ \phi(p-1) \ .

Примеры показывают, что для простых модулей относительная плотность первообразных корней достаточно велика:

\begin{array}{|c|c|c|} \hline p & \phi(p-1)/(p-1) \approx & \Lambda_{\min} \\ \hline 9275976597265732276527865457 & 0.41 & 3 \\ \hline 573549798028708743039820820873497 & 0.32 & 5 \\ \hline 634626763287685763453724586384584746438653493 & 0.48 & 2 \\ \hline 19366902134839432153298400937646552542165422356457691 & 0.26 & 2 \\ \hline \end{array}

в третьем столбце приведены значения минимальных первообразных корней.

Теперь вернемся к общему случаю составного модуля M_{} и выясним, почему при некоторых его значениях не существует первообразных корней. Объяснение кроется в том, что в теореме Эйлера значение функции Эйлера \phi(M) часто можно заменить на меньшее — именно, на значение обобщенной функции Эйлера L(M). Как правило \phi(M) > L(M), так что значение L(M) дает более точную оценку длины цикла последовательности остатков \{ A^j \pmod{M} \}_{j=0}^{\infty}. Тем не менее, первообразный корень может существовать и для некоторых классов составных модулей.

Т

Теорема 8. Первообразные корни по модулю M_{} существуют тогда и только тогда, когда:

  1. M=p^{n} при p>2 простом и n \in \mathbb N;
  2. M=2p^n при p>2 простом и n \in \mathbb N;
  3. M\in \{1,2,4\}.
П

Пример. Для M=27 имеем \phi(M) =L(M)=18 и числа 2,5,11,14,20,23 являются первообразными. Если обозначить любое из них через \Lambda, то последовательность \{ \Lambda^j \pmod{M} \}_{j=0}^{17} пробегает все числа множества \{1,2,\dots,26\} некратные 3_{}.

Критерий простоты числа

Т

Теорема. Пусть p>2 и каноническое разложение числа p-1 имеет вид:

p-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ .

Для того чтобы число p_{} являлось простым, необходимо и достаточно, чтобы существовало число A_{} \in \mathbb Z такое, что для него выполнялись условия:

A^{p-1} \equiv 1 \pmod{p} \quad u \quad A^{(p-1)/p_j} \not\equiv 1 \pmod{p} \quad npu \ \forall j\in \{1,\dots, \mathfrak r\} \ .

Доказательство. Необходимость. Если p_{} — простое, то в качестве A_{} можно взять любой первообразный корень по модулю p_{}.

Достаточность. Если условия теоремы выполняются для некоторого A_{}, то по модулю p_{} будет: \operatorname{ord}(A)=p-1, на основании определения порядка и теоремы 3 из предыдущего пункта. По той же теореме число \phi(p) должно делиться на p-1. Однако последнее возможно только при условии \phi(p)=p-1, что и означает простоту p_{}.

П

Пример. Является ли число 9721 простым?

Решение. Попытаемся подобрать число A_{}, которое удовлетворило бы условиям теоремы. Имеем 9721-1=2^3\cdot 3^5 \cdot 5 и с помощью алгоритма "квадрирования-умножения" вычислим

A=2 \ \Rightarrow \ 2^{9720} \equiv 1 \pmod{9721} \ , \ 2^{4860} \equiv 1 \pmod{9721} \ .

Число A=2 условию теоремы не удовлетворяет.

A=3 \ \Rightarrow \ 3^{9720} \equiv 1 \pmod{9721} \ , \ 3^{4860} \equiv 1 \pmod{9721} \ .

Число A=3 условию теоремы не удовлетворяет.

A=7 \ \Rightarrow \ 7^{9720} \equiv 1 \pmod{9721} \ , \ 7^{4860} \equiv 9720 \pmod{9721} \ , 7^{3240} \equiv 7796 \pmod{9721} \ ,
7^{1944} \equiv 4264 \pmod{9721} \ .

Число A=7 удовлетворяет условию теоремы.

Ответ. Да.

Длина периода десятичной дроби

Задача. Обратим обыкновенную дробь \displaystyle \frac{1}{p} в десятичную, получим бесконечную десятичную дробь. Как связана длина периода этой дроби с числом p_{}?

Т

Теорема. Длина периода десятичной дроби для \displaystyle \frac{1}{p} является делителем числа p-1.

Доказательство. По теореме Ферма при p \not\in \{2,5\} число 10^{p-1}-1 делится на p_{}; таким образом 10^{p-1}=Qp+1 при Q \in \mathbb Z. Следовательно

\frac{10^{p-1}}{p}=Q+\frac{1}{p} \ ,

и числа 1/p и 10^{p-1}/p имеют одинаковые дробные части. Но это и означает, что если в записи периодической дроби для 1/p переместить точку на p-1 позицию вправо, то дробная часть сохранит свой вид. Для p \in \{2,5\} справедливость утверждения теоремы проверяется непосредственной проверкой.

П

Пример.

\frac{1}{3}=0.(3); \ \frac{1}{7}=0.(142857); \ \frac{1}{11}=0.(09) \ .

=>

Длина периода десятичной дроби для \displaystyle \frac{1}{p} при p \not\in \{2,5\} равна порядку числа 10_{} по модулю p_{}, т.е. \operatorname{ord}(10).

П

Пример.

\frac{1}{103}= 0.\underbrace{0097087378640776699029126213592233}_{34}00970874\dots \ ,

и действительно, по модулю 103 имеем \operatorname{ord}(10)=34.

Индекс

Итак, для любого первообразного корня \Lambda последовательность остатков от деления его степеней на p_{}

\Lambda^0=1,\ \Lambda^1 \pmod{p},\dots , \Lambda^{p-2} \pmod{p}

представляет переставленные числа 1,2,\dots,p-1.

Для первообразного корня \Lambda и произвольного целого числа A\in \{1,2,\dots,p-1\}, число, обозначаемое \operatorname{ind}_{_{\Lambda}} A, называется индексом A_{} по модулю p_{} и основанию \Lambda, если

\Lambda^{\operatorname{ind}_{_{\Lambda}} A} \equiv A \pmod{p} \ .
§

Определение индекса очень напоминает определение логарифма положительного вещественного числа A_{} по основанию положительного вещественного числа \Lambda; в дальнейшем, исследуя свойства \operatorname{ind}_{_{\Lambda}} A, мы установим их параллель со свойствами \log_{_{\Lambda}} A. Эта аналогия привела к тому, что в последние десятилетия в литературе вместо слова «индекс» часто используется выражение «дискретный логарифм»; единственное отличие у этих терминов заключается в том, что индекс определяется не однозначно, а как класс вычетов по модулю p-1, в то время как значение дискретного логарифма принимается равным единственному представителю этого класса во множестве \{0,1,\dots,p-2\}. Иногда в дальнейшем мы и \operatorname{ind}_{_{\Lambda}} A будем отождествлять с этим представителем.

П

Пример. Для p=17 число \Lambda=3 является первообразным корнем (см. решение примера ЗДЕСЬ ). Имеем:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \hline \operatorname{ind}_{3} A&0&14&1&12&5&15&11&10&2&3&7&13&4&9&6&8 \\ \hline \end{array}

Подобные таблицы можно построить и для других модулей или оснований — вычислением последовательности \{ \Lambda^j \}_{j=0}^{p-2} и последующей сортировкой. В общем же случае — для произвольных модулей или оснований — задача вычисления индекса или задача дискретного логарифмирования является крайне сложной, и, в настоящее время не имеет универсального алгоритма решения.

Если же величины индексов по основанию некоторого первообразного корня \Lambda известны, то это позволяет упростить анализ некоторых задач. Все применения индекса основаны на следующем очевидном факте: при \operatorname{HOD} (B,M)=1 сравнение

A\equiv B \pmod{M}

имеет место тогда и только тогда, когда

\operatorname{ind}_{_{\Lambda}} A \equiv \operatorname{ind}_{_{\Lambda}} B \pmod{\phi(M)} \ .
Т

Теорема. Если \Lambdaпервообразный корень по модулю M_{} и \operatorname{HOD} (A,M)=1,\ \operatorname{HOD} (B,M)=1, то

\operatorname{ind}_{_{\Lambda}} (A\cdot B) \equiv \operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B \pmod{\phi(M)} \ .

Доказательство.

\Lambda^{\operatorname{ind}_{_{\Lambda}} (A\cdot B)} \equiv_{_M} A\cdot B \equiv_{_M} \Lambda^{\operatorname{ind}_{_{\Lambda}} A} \cdot \Lambda^{\operatorname{ind}_{_{\Lambda}} B} = \Lambda^{\operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B} \ .

Поскольку \Lambda является первообразным корнем по модулю M_{}, то \operatorname{ord}(\Lambda)=\phi(M), и, следовательно, условие

\Lambda^{\operatorname{ind}_{_{\Lambda}} (A\cdot B)} \equiv \Lambda^{\operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B} \pmod{M}

влечет за собой

\operatorname{ind}_{_{\Lambda}} (A\cdot B)=\operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B \pmod{\phi(M)} \ .

=>

Если \Lambda — первообразный корень по модулю M_{} и \operatorname{HOD} (A_1,M)=1,\dots, \operatorname{HOD} (A_K,M)=1, то

\operatorname{ind}_{_{\Lambda}} (A_1 \times \dots \times A_K) \equiv \operatorname{ind}_{_{\Lambda}} A_1 + \dots + \operatorname{ind}_{_{\Lambda}} A_K \pmod{\phi(M)} \ .

В частности, при \operatorname{HOD} (A,M)=1 имеем:

\operatorname{ind}_{_{\Lambda}} A^K \equiv K \cdot \operatorname{ind}_{_{\Lambda}} A \pmod{\phi(M)} \ .

Источники

[1]. Бухштаб А.А. Теория чисел. М. Просвещение. 1966

[2]. Uspensky J.V., Heaslet M.A. Elementary Number Theory. New York. McGraw-Hill. 1941

1) parity (англ.) — четность.
2) В англоязычной литературе принято название primitive root.

2016/11/01 12:44 редактировал au