Первообразные корни и индексы

$\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) в общем случае.