Элементы теории чисел

Многие криптографические алгоритмы базируются на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел. Читатели, знакомые с теорией чисел, могут непосредственно перейти к следующему разделу.

Как мы уже указывали ранее, целое положительное число р называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы.

Пример. Числа 11, 23 — простые; числа 27, 33 — составные (27 делится на 3 и на 9, 33 делится на 3 и на 11).

Пример. $27 = 3\times3\times3$, $33 = 3\times11$.

Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы.

Пример. Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 — нет (у них есть общий делитель 3).

Определение (функция Эйлера). Пусть дано целое число $N > 1$. Значение функции Эйлера $\phi(N)$ равно количеству чисел в ряду $1,2,3,... ,N — 1$, взаимно простых с $N$.

Утверждение. Если $p$ — простое число, то $\phi(p) = p — 1$. Доказательство.В ряду $1,2,3,... ,p — 1$ все числа взаимно просты с р, так как $р$ — простое число и по определению не делится ни на какое другое число.

Утверждение. Пусть $p$ и $q$ — два различных простых числа $(р \not = q)$. Тогда $\phi (pq) = (p — 1) (q — 1)$.

Теорема (Ферма). Пусть $p$ простое число и $0<a<p$. Тогда $a^{p-1}mod\,p=1$

Теорема (Эйлер). Пусть $a$ и $b$ — взаимно простые числа. Тогда $a^{\phi\, (b)}\, mod\, b=1$. Теорема Ферма является частным случаем теоремы Эйлера, когда $b$ — простое число.

Пример. $\phi(12) = 4$, $5^4 mod \,12 = (5^2)^2 mod \,12 = (1^2)^2 mod \,12 = 1$.

Нам понадобится еще одна теорема, близкая к теореме Эйлера.

Обозначение gcd для наибольшего общего делителя происходит от английских слов greatest common divisor и принято в современной литературе.)

Пример. $gcd(10,15) = 5$; $gcd(8, 28) = 4$.

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

Алгоритм Евклида

ВХОД: Положительные целые числа $a$,$b$, $a > b$.

ВЫХОД: Наибольший общий делитель $gcd(a, b)$.

Пример. Покажем, как с помощью алгоритма Евклида вычисляется $gcd(28, 8)$:

a:	28	8	4
b:	8	4	0
r:	4	0

Здесь каждый столбец представляет собой очередную итерацию алгоритма. Процесс продолжается до тех пор, пока Ь не станет равным нулю. Тогда в значении переменной а содержится ответ (4).

Для многих криптографических систем, рассматриваемых в следующих разделах и главах, актуален так называемый обобщенный алгоритм Евклида, с которым связана следующая теорема.

Обобщенный алгоритм Евклида служит для отыскания $gcd(a, b)$ и $х$, $у$, удовлетворяющих (2). Введем три строки

$U = (u_1, u_2, u_3),$

$V = (v_1, v_2, v_3)$ и

$Т = (t_1, t_2, t_3)$

Тогда алгоритм записывается следующим образом.

Обобщенный алгоритм Евклида

ВХОД: Положительные целые числа $a$, $b$, $a > b$.

ВЫХОД: $gcd(a, b)$, $x$, $y$, удовлетворяющие (2).

Результат содержится в строке U. Операция div в алгоритме — это целочисленное деление a div b = [а/b].

Пример. Пусть $а=28$, $b=19$. Найдем числа $х$ и $у$, удовлетворяющие (2).

U				28	1	0
V	U			19	0	1
Т	V	U		9	1	-1	q = 1
	Т	V	U	1	-2	3	q = 2
		Т	V	0	19	-28	q = 9

Поясним представленную схему. Вначале в строку U записываются числа (28,1,0), а в строку V — числа (19,0,1) (это первые две строки на схеме). Вычисляется строка Т (третья строка в схеме). После этого в качестве строки U берется вторая строка в схеме, а в качестве V — третья, и опять вычисляется строка Т (четвертая строка в схеме). Этот процесс продолжается до тех пор, пока первый элемент строки V не станет равным нулю. Тогда предпоследняя строка в схеме содержит ответ.

В нашем случае $gcd(28,19) = 1$, $х = -2$, $у = 3$. Выполним проверку: $28 \cdot (—2) + 19 \cdot 3 = 1$.

Рассмотрим одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел с, m требуется находить такое число d < m, что $$cd \,mod \,m=1~~~(3)$$

Отметим, что такое d существует тогда и только тогда, когда числа с и m взаимно простые.

Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (3) в виде $сс^{-1} mod\, m = 1$. Умножение на $с^{-1}$ соответствует делению на с при вычислениях по модулю $m$. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю $m$: $$с^{-е} = (с^e)^{-1} = (с^{-1})^e (mod\, m)$$

Пример. $3\cdot4 mod 11 = 1$, поэтому число 4 — это инверсия числа 3 по модулю 11. Можно записать $З^{-1} mod 11 = 4$. Число $5^2\,mod 11$ может быть найдено двумя способами:

$5^{-2} mod\, 11 = (5^2 mod\, 11)^{-1} mod \,11 = 3_1 mod\, 11 = 4,$

$5^{-2} mod\, 11 = (5^{-1} mod\, 11)^2 mod\, 11 = 92 mod\, 11 = 4.$

При вычислениях по второму способу мы использовали равенство $5^{-1} mod 11 = 9$. Действительно, $5 \cdot 9 \,mod\, 11 = 45,\ mod\,11 = 1$.