Глава 7.

ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ

Основное в этой главе…

Расширенный алгоритм Эвклида....95

Функция Эйлера и малая теорема Ферма……………………………………97

Сравнения первой степени от одного неизвестного…………….…………….98

Степенные сравнения по простому модулю………………………………...100

(a,b)

94 Глава 7. ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ

Внедрение средств криптографической защиты информации, основанных на асимметричных криптоалгоритмах, потребовало существенного расширения диапазона средств теории чисел, используемых в криптографии.

Тем не менее, терминология, используемая в рекомендациях стандартов, а также при описании криптоалгоритмов и результатов их анализа, основана, как правило, на ряде простых понятий теории чисел, которые мы кратко рассмотрим ниже. Более полно, см. [14,15,16].

7.1. Некоторые сведения из арифметики Числа 1,2,3,… называются натуральными. Число 0, а также числа вида

± a , где a натуральное число, называются целыми числами. Отношение двух целых чисел называется рациональной дробью и является формальной записью результата деления одного числа на другое. Деление на ноль не определено.

Простым числом называется натуральное число, у которого есть в точности два неравных натуральных делителя.

Основная теорема арифметики: каждое натуральное число m единственным, с точностью до порядка сомножителей, образом представляется в виде произведения степеней простых чисел: m = p1a p2b Kpst .

Наибольшим общим делителем двух целых чисел a и b называется наибольшее целое число, которое делит как a, так и b. Обозначения:

или НОД(a,b).

Наименьшим общим кратным целых чисел a и b называется число НОК(a,b)= (aab, b), делящееся, очевидно, как на a , так и на b.

Числа a и b называются взаимно простыми, если d = (a,b)=1.

Имеет место следующее утверждение. Пусть d = (a,b). Тогда существуют целые числа x , y , являющиеся решением уравнения xa + yb = d .

Некоторые сведения из арифметики 95

7.1.1. Расширенный алгоритм Эвклида

Решение x, y , d уравнения xa + yb = d , a>b, d = (a,b), можно найти с

помощью т.н. расширенного алгоритма Эвклида. Очевидно, общий случай сводится к решению подобных уравнений, при положительных a и b.

Рассмотрим схему расширенного алгоритма Эвклида на примере числе 15 и 25. Мы будем находить остатки и (неполные) частные от деления двух чисел,

т.е. пользоваться равенствами			вида A = kB + r , где		все числа		целые и
0 ≤ r < B .
Поскольку	должно	выполняться		неравенство	a > b , то		изменим
обозначения: r0 = 25, r1 =15 .
Выпишем последовательность строк:
		r0 = 25 x0 =1 y0 = 0
		r1 =15 x1 = 0 y1 =1 ( d2 =1, r2 =10).
Пояснение.	Делим	r0 на	r1 с остатком. Получаем:			r0 = d2r1 + r2 т.е.
25 =1 15 +10 , откуда		d2 =1,	r2 =10	. Проверяем: r2 =0		? Нет –	работаем

дальше. Вычисляем x2 , y2 : x2 = x0 − x1d2 =1 y2 = y0 − y1d2 = −1. Формируем очередную строку: r2 , x2 , y2 .

Исходными данными для шага 2 будут строки r1, x1, y1 (из предыдущего шага) и r2 , x2 , y2 . С этими строками действуем аналогично.

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

r2 =10 x2 =1 y2 = −1 ( d3 =1, r3 =5 )

r3 =5 x3 = −1 y3 = 2 ( d4 = 2, r4 =0 ).