Первообразные корни и индексы
$\newcommand\ind{\mathop{\rm ind}\nolimits}$Теорема (Эйлер). $\forall m\in \mathbb {N}\ \forall a, (a, m) = 1\colon a^{\varphi (m)} \equiv 1\pmod m$.
Определение. Показатель числа $a$ по модулю $m$ ($(a, m) = 1$) — наименьшее число $\delta \colon $ $a^\delta \equiv 1\pmod m$.
Утверждение: Показатель числа является делителем числа $\varphi (m)$.
Определение. Первообразный корень по модулю $m$ — такое число $g$, что $\delta (g) = \varphi (m)$.
Допустим, мы знаем, что по mod $m = p$ (простое) $\exists g$. Тогда $g^0, g^1, g^2, \ldots , g^{p-2}$ — различны mod $p$.
Действительно, пусть $x > y$. Тогда $g^ x\equiv g^ y\ (p) \Rightarrow g^{x-y} \equiv 1\ (p)$, но $0 < x-y \leqslant p-2$.
Можно, стало быть, определить "логарифм" произвольного числа $a \in \{ 1, 2, \ldots , p-1\} $ по основанию $g$ и mod $p$.
Т.е. $\ind _ g a := x\colon g^ x \equiv a\ (p)$ (индекс, дискретное логарифмирование).
Факты:
1) Легко найти просто число $\approx 10^{1000}$.
2) Не сложно найти первообразный корень $g$ mod $p$.
3) $\ind _ g a$ "не ищется".
Шифрование (алгоритм Диффи – Хеллмана):
$p\approx 10^{1000}, g$ — открыты. A задумала $x$, B задумал $y$.
A публикует $g^ x$, B публикует $g^ y$.
A и B знают $g^{xy}$, кроме них никто его не знает.
Теорема. Первообразные корни существуют $\iff $ $n\in \{ 2, 4, p^\alpha , 2p^\alpha \} $, где $p$ — нечётное простое, $\alpha \geqslant 1$.
Доказательство:
1) Пусть $n \in \{ 2, 4\} $. $\varphi (2) = 1, \varphi (4) = 2$. Очевидно.
2) Пусть $m = p$ — нечётное простое число.
Рассмотрим все числа $1, 2, \ldots , p-1$. Для каждого из них найдём показатель $\text {mod }p$ $\delta _1, \ldots , \delta _{p-1}$.
$\tau := \mbox{НОК} [\delta _1, \ldots , \delta _{p-1}]$. Рассмотрим каноническое разложение $\tau $ по простым множителям
$\tau = q_1^{\alpha _1}\cdot \ldots \cdot q_ k^{\alpha _ k}$.
Для каждого $i \in \{ 1, 2, \ldots , k\} $ найдём такое число $\delta \in \{ \delta _1, \ldots ,\delta _{p-1}\} \colon $ $\delta = a q_ i^{\alpha _ i}$, $(a, q_ i) = 1$. По $\delta $ найдём такой $x \in \{ 1, 2, \ldots , p-1\}$, что показатель $x$ равен $\delta $.
Утверждение. Показатель числа $x^ a$ равен $q_ i^{\alpha _ i}$ (т.к. $x^\delta \equiv 1\ (p)$).
Обозначим $x$ через $x_ i$, а число $a$ через $a_ i$. Тогда показатель $x_ i^{a_ i}$ равен $q_ i^{\alpha _ i}$.
Утверждение. Число $g := x_1^{a_1}\cdot \ldots \cdot x_ k^{a_ k}$ имеет показатель, равный $q_1^{\alpha _1}\cdot \ldots \cdot q_ k^{\alpha _ k} = \tau $.
Если мы докажем, что $\tau = p-1$, то теорема будет доказана.
С одной стороны, $\tau$ — НОК чисел, каждое из которых является делителем числа $p-1$. Значит, $\tau \mid p-1 \Rightarrow \tau \leqslant p-1$. С другой стороны, рассмотрим сравнение $x^\tau \equiv 1\ (p)$. Этому сравнению заведомо удовлетворяют числа $1, 2, \ldots , p-1 \Rightarrow $ $\tau \geqslant p-1$ (т.к. сравнение имеет $p-1$ корень) $\Rightarrow $ $\tau = p-1$.
3) Пусть $m = p^\alpha , p$ — нечётное простое, $\alpha \geqslant 2$.
Пусть $g$ — первообразный корень по mod $p$.
Лемма. $\exists t\colon (g + pt)^{p-1} = 1 + pu$, где $(u, p) = 1$ (тут равенство!).
$\blacktriangle$ $(g + pt)^{p-1} = g^{p-1} + C_{p-1}^1 g^{p-2} pt + C_{p-1}^2 g^{p-3} p^2 t^2 + \ldots =$
(слагаемые, начиная с третьего, делятся на $p^2$, то есть представимы в виде $p^2r$)
$= (1 + ps) + (p-1)g^{p-2} pt + p^2r =$ $1 + p(s + (p-1)g^{p-2}t + pr)$
$(w, p) = 1.$ $s + (p-1)g^{p-2}t + pr = s + wt + pr \stackrel{?}{=} u$, где $(u,p) = 1$.
Если $p\mid s$, то берём $t = 1$.
Если $p\not\mid s$, то берём $t = p$. $\blacksquare $
Докажем, что $g + pt$ — это и есть первообразный корень mod $p^\alpha $.
$\varphi (p^\alpha ) = (p-1)p^{\alpha -1}$, т.е. нам нужно доказать, что если $(g+pt)^ x \equiv 1\ (p)$, то $x \geqslant (p-1)p^{\alpha -1}$.
$(g + pt)^{p-1} = 1 + pu, (u, p) = 1$.
$(g + pt)^{(p-1)p} = (1 + pu)^ p = 1 + ppu + C_{p}^2 (pu)^2 + \ldots =$ $1 + p^2u_1, (u_1, p) = 1$.
$(g + pt)^{(p-1)p^2} = (1 + p^2u_1)^ p = 1 + p^3u_2, (u_2, p) = 1$.
…
$(g + pt)^{(p-1)p^ k} = 1 + p^{k+1}u_ k, (u_ k, p) = 1$.
Пусть $\tau$ — показатель числа $g+pt$ mod $p^\alpha $.
$\newcommand{\divby}{\mathop{\smash{\vdots}}}$
Конечно, $(g + pt)^\tau \equiv 1\ (p^\alpha ) \Rightarrow (g + pt)^\tau \equiv 1\ (p)$. Поскольку $g$ — первообразный корень mod $p$, $\tau \divby (p-1)$. С другой стороны, $\tau $ является делителем
$\varphi (p^\alpha ) = (p-1)p^{\alpha -1} \Rightarrow $
$\tau = (p-1)p^ k \Rightarrow $
$(g + pt)^\tau = 1 + p^{k+1}u_ k, (u_ k, p) = 1\ (p^\alpha ) \Rightarrow $ $k = \alpha - 1 \Rightarrow $
$\tau = (p-1)p^{\alpha -1}$.
4) Пусть $m = 2p^\alpha , \varphi (m) = \varphi (p^\alpha ) = (p-1)p^{\alpha -1}$.
$g$ — первообразный корень mod $p$. Либо $g$, либо $g + p^\alpha$ — нечётное число, оно и будет искомым первообразным.
5) Пусть $m = 2^\alpha , \alpha \geqslant 3$, тогда $\nexists $ первообразных корней.
$\varphi (m) = 2^{\alpha - 1}$. Рассмотрим $\forall a\colon a$ — нечётное $a^{2^{\alpha -2}}, a = 1+2k$.
$a^2 = 1 + 4k + 4k^2 = 1 + 4k(1+k) = 1 + 8t$.
$a^{2^2} = (1 + 8t)^2 = 1 + 16t + 64t^2 = 1 + 16t_1$.
$a^{2^3} = (1 + 16t_1)^2 = 1 + 32t_2$
…
$a^{2^{\alpha -2}} = 1 + 2^{\alpha }t_{\alpha -3} \equiv 1\ (2^\alpha )$.
Значит, любое нечётное число не может быть первообразным.
6) Пусть $m = 2^{\alpha _0}p_1^{\alpha _1}\cdot \ldots \cdot p_ k^{\alpha _ k}$, либо $k\geqslant 2$ и $\alpha _0\geqslant 0$, либо $k = 1$ и $\alpha _0\geqslant 2$.
$a_0 := \varphi (2^{\alpha _0}), \alpha _0\neq 0, a_1 := \varphi (p_1^{\alpha _1}), \ldots , a_ k := \varphi (p_ k^{\alpha _ k})$.
Рассмотрим $\tau := \mbox{НОК}[a_0, a_1, \ldots , a_ k]$. Ясно что любое $a\colon (a, m) = 1$ таково, что $a^\tau \equiv 1$. Осталось доказать, что $\tau \lt \varphi (m)$.
$\varphi (m) = m\left(1 - \frac12\right)\left(1 - \frac1{p_1}\right)\cdot \ldots \cdot \left(1 - \frac1{p_ k}\right)$ (если $\alpha _0 > 0$).
Рассмотрим случай $m = p_1p_2$.
$\varphi (m) = (p_1 - 1)(p_2 - 2)$.
$\varphi (p_1) = p_1 - 1$,
$\varphi (p_2) = p_2 - 1$.
$\mbox{НОК}[\varphi(p_1)\varphi(p_2)] \lt \varphi(m).$
Задача. Завершить доказательство пункта (6) в общем случае.