Формула Эйлера

Формула Эйлера

Рассмотрим число \(N\geqslant 1\) и все числа в пределах от \(0\) до \(N-1\), взаимно простые с \(N\). Договоримся далее называть такие числа приведённой системой остатков.

Рассмотрим по модулю \(N\) произведение всех остатков приведённой системы:

\[ a_1 a_2 \ldots a_m \equiv_N ??? \]

Выберем произвольный остаток приведённой системы \(a\) и для каждого \(a_i\) выберем такой остаток приведённой системы \(A_i\), для которого выполнено

\[ a_i \equiv_N a A_i \]

Упражнение: поймите, почему для каждого \(i\) такой остаток существует и единственный.

Продолжим рассматривать произведение всех остатков приведённой системы:

\[ a_1 a_2 \ldots a_m \equiv_N (aA_1)(aA_2)\ldots (aA_m) \]

Воспользуемся коммутативностью и ассоциативностью умножения:

\[ a_1 a_2 \ldots a_m \equiv_N a^m A_1 A_2 \ldots A_m \]

Заметим, что все \(A_i\) различны. Поскольку их ровно столько же, сколько и всего остатков приведённой системы, то последовательность всех \(A_i\) является перестановкой последовательности всех \(a_i\).

То есть

\[ a_1 a_2 \ldots a_m \equiv_N a^m (a_1 a_2 \ldots a_m) \]

А учитывая взаимную простоту \(a_i\) и \(N\), получаем

\[ 1 \equiv_N a^m \]

Это сравнение называется формулой Эйлера, а \(m\) — значением функции Эйлера на числе \(N\).

Далее функцию Эйлера мы будем обозначать буквой \(\varphi\).

Итого: если \(a\) и \(N\) взаимно просты, то

\[ a^{\varphi(N)} \equiv_N 1 \]

Полезные следствия

Рассмотрим сравнение

\[ x^{a} \equiv_N A \]

Пусть при этом \(a\) взаимно просто с \(\varphi(N)\) и \(A\) взаимно просто с \(N\).

Допишем к этому сравнению формулу Эйлера (взаимная простота \(x\) и \(N\) следует из таковой для \(A\) и \(N\)):

\[ x^{\varphi(N)} \equiv_N 1 \]

К подобной паре сравнений можно применить мультипликативный алгоритм Евклида. Сейчас мы покажем, как такие сравнения «делить друг на друга с остатком».

Пусть имеется пара сравнений

\[ \begin{aligned} x^{a} & \equiv_N A \\ x^{b} & \equiv_N B \end{aligned} \]

причём \(a = bk + r\). Тогда

\[ x^{a} = (x^{b})^k \cdot x^r \equiv_N A^k x^r \]

То есть мы получили

\[ A^{k-1} x^r \equiv_N 1 \]

откуда можно получить сравнение вида \(x^r \equiv_N C\).

Алгоритм Евклида закончится на сравнении

\[ x \equiv_N \mathfrak{M} \]

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

\[ ay + \varphi(N)z = 1 \]

(более того, во многих случаях это ещё и эффективнее с вычислительной точки зрения).

Тогда \(\mathfrak{M} = A^{y}\).

Осталось заметить, что

\[ (A^{y})^a = A^{ay} = A^{ay}\cdot 1 \equiv_N A^{ay}\cdot A^{\varphi(N)z} = A^1 = A \]

Поэтому найденный кандидат на звание решения действительно является решением.

PS Заметим, что именно на подобной схеме основан алгоритм RSA. В вышеиспользуемых обозначениях для двух простых различных чисел \(p\) и \(q\)

• публичным ключом является любое \(a\), взаимно простое с \(\varphi(pq)=(p-1)(q-1)\), и число \(N=pq\)
• приватным ключом является вычисленное по этому \(a\) число \(y\) и также \(N=pq\).
• что шифрование, что дешифровка — возведение в степень, равную первой компоненте пары, составляющей ключ, по модулю второй компоненты этой пары, то есть — по модулю \(N\).

Быстрое вычисление функции Эйлера

Начнём с того, что \(\varphi(1) = 1\) (среди чисел от \(0\) до \(0\) с единицей не взаимно прост этот самый ноль). Но это — бесполезный факт.

Если \(N\) — простое число, то, очевидно

\[ \varphi(N) = N-1 \]

поскольку среди чисел от \(0\) до \(N-1\) с \(N\) не взаимно прост только ноль.

Если \(N=p^k\), где \(p\) — простое число, то

\[ \varphi(N) = p^k - p^{k-1} \]

поскольку с \(p^k\) не взаимно просты числа, кратные \(p\), и только они.

Если же \(N=ab\), где \(a\) и \(b\) взаимно просты, то из КТО следует

\[ \varphi(a\cdot b) = \varphi(a)\cdot\varphi(b) \]

Чуть подробнее: сравнение \(x\equiv_{ab} m\) согласно КТО эквивалентно системе

\[ \begin{aligned} x & \equiv_a A \\ x & \equiv_b B \end{aligned} \]

Нетрудно при этом заметить, что \(m\) в таком соответствии взаимно просто с \(ab\) тогда и только тогда, когда \(A\) взаимно просто с \(a\) и \(B\) взаимно просто с \(b\).