ax ≡b modm

98 Глава 7. ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ
Теорема Эйлера. Если	(a,m)=1, то aϕ(m) ≡1 mod m .
Из теоремы Эйлера следует малая теорема Ферма: a p−1 ≡1mod p , где						p -
простое, (a, p)=1.
Определение. Элемент (вычет) γ		называется первообразным корнем по
модулю m, если его порядок по модулю m равен ϕ(m). При m = p , где						p -
простое, первообразные корни всегда существуют.
Пусть p −1 =∏piai .	Можно	показать,	что	элемент γ	является
i
первообразным корнем по модулю		p тогда	и только тогда,		когда	i
γ (p−1) pi ≠1mod p .
Таким образом, любое число a, взаимно простое с				p , сравнимо по модулю
p с числом вида γ h .
Множество вычетов с модульными операциями по простому модулю						p
является т.н. простым полем Галуа из p элементов. Обозначение: GF(p).

При составном модуле m соответствующее множество вычетов полем не является, т.к. не все элементы обратимы, однако оно образует коммутативное кольцо с единицей ZmZ . Естественно, кольцо Z pZ - конечное поле из p

элементов.

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

Сравнения вида могут иметь несколько решений, иметь единственное решение или не иметь решений вовсе. Если (a,m)=1, то решение единственно: x ≡ a−1b .

Решения существуют тогда и только тогда, когда d =(a,m) делит b.

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

В этом случае, кроме исходного сравнения, разрешимо сравнение вида

a

x ≡

b

mod

m

с

единственным

решением

x .

Очевидно,

все решения

d

d

d

o

исходного

сравнения в диапазоне 0 ≤ x ≤ m −1

являются

числами

вида

xo + j

m

mod m ,

j = 0,1,K,d −1. В частности, если m простое, то сравнение

d

ax ≡b modm при a ≠ 0 всегда однозначно разрешимо.

Кроме того, можно показать, что для многочлена от одной переменной с

коэффициентами

из GF(p) количество корней, лежащих в

GF(p),

не

превосходит степени многочлена.

7.3.1. Китайская теорема об остатках

Следующее утверждение называется китайской теоремой об остатках.

Пусть числа

m1,m2 ,K,mk попарно взаимно просты и M = m1m2 Kmk .

Тогда среди наименьших неотрицательных вычетов по модулю M существует

единственное решение системы сравнений x ≡ ci modmi , i =1,K,k .

k

При

этом,

x ≡ ∑ci Mi Ni

mod M , где

Mi = m1m2 Kmi−1mi+1Kmk ,

i=1

Ni = Mi−1 mod mi .

Действительно, в указанном выражении для x одно слагаемое сравнимо с ci по модулю mi , а все прочие сравнимы с нулем.

Заметим, что коэффициенты Mi Ni mod M можно вычислить заранее и решать несколько систем, подставляя их правые части в линейную форму.

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

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

Напомним, что поле является множеством с двумя внутренними

коммутативными		операциями,	подчиненными		ассоциативному	и
дистрибутивному законам. Операции называются сложением и умножением.
По отношению к каждой из операций в поле существует нейтральный
элемент	(ноль и	единица). Уравнение вида		ax =b	при a ≠ 0 имеет
единственное решение. Уравнение a + x =b всегда однозначно разрешимо.
Привычным примером бесконечного поля является множество
рациональных дробей. Простое поле GF(p) является конечным множеством.
Очевидно, что в поле GF(p) результат сложения любого элемента самого
с собой	p раз равен нулю. Таким		образом,	умножение любого элемента

GF(p) на p дает ноль. Число p называется характеристикой поля GF(p).

Оказывается, количество элементов конечного поля всегда является степенью простого числа вида q = pa .

Если a>1, то поле GF(pa ) содержит простое поле GF(p) и называется

его расширением. Характеристика поля GF(pa )равна p . Важно помнить, что

операции в этом поле не являются операциями по модулю q = pa .

Известно, что в каждом конечном поле существует т.н. первообразный элемент (генератор поля). Степени g, g2 = g g,K первообразного элемента g

представляют все ненулевые элементы поля. Поэтому gq−1 =1. Поскольку gh(q−1) =1, то любой элемент поля b ≠ 0 удовлетворяет соотношению bq−1 =1.

Операции в полях «учитывают» свойства характеристики поля автоматически. Поэтому обычные сравнения по модулю p являются равенствами в соответствующем простом поле.

x = g y

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

Важной задачей, имеющей приложения в криптографии, является решение степенных сравнений вида xk ≡ a mod p .

Пусть g - первообразный элемент простого поля. Тогда существуют числа

y и b, такие что	x = g y , a = gb , поэтому	gky = gb . Число	b называется
дискретным логарифмом числа a по модулю		p при основании	g . Поскольку
ord p g = p −1, то	ky ≡b mod(p −1). Свойства последнего сравнения

полностью характеризуют разрешимость исходного. Любое его решение y

приводит к решению сравнения xk ≡ a mod p .

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

В общем случае, задача нахождения b является вычислительно нереализуемой (проблема дискретного логарифмирования). Дискретные логарифмы часто обозначаются как ind или D lg .

Известен следующий результат: пусть p - простое, (a, p)=1, h = ord pa ,

тогда сравнение xh ≡1mod p имеет ϕ(h) решений.
Следствие.	При	h =ϕ(p) получаем,		что число первообразных корней
равно ϕ(p −1).
Покажем,	что	разрешимость сравнения			xn ≡ a(p) эквивалентна
выполнению условия a(p−1) d			≡1mod p , где d =(n, p −1).
Переход	к индексам		показывает,	что	n indx ≡inda mod(p −1).

Необходимое и достаточное условие разрешимости последнего сравнения заключается в том, чтобы ind a делился на d = (n, p −1), т.е.

ind a ≡ 0 mod d .

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

Умножая модуль и обе части последнего сравнения на		p −1		, получим
		d
p −1	inda ≡ 0 mod(p −1), откуда следует, что условие ind a ≡			0 mod d
d

эквивалентно условию a(p−1)d ≡1mod p .

Следствие. Разрешимость сравнения x2 ≡ a(mod p) эквивалентна выполнению условия a(p−1)2 ≡1mod p .

Рассмотрим пример на решение степенных сравнений.

Пример. Решить сравнение 39x21 ≡53(73).

Таблица дискретных логарифмов считается известной. (Конкретные значения рассчитаны при p = 73 и g = 5).

Логарифмируя обе части сравнения, получаем:

ind39 + 21indx ≡ind53(72) 21indx ≡ind53 −ind39(72)

21indx ≡53 −65(72) 21indx ≡ −12(72).

Поскольку наибольший общий делитель модуля и коэффициента при

неизвестном	равен 3 (больше единицы)		и делит правую часть, то сравнение
разрешимо, однако имеет несколько решений.
Деля коэффициенты и модуль на 3, получаем 7indx ≡ −4(24). Умножая
на 7 обе	части сравнения,	находим	indx ≡ −4(24)= 20(24). Поэтому
indx ≡ 20 + j24 mod72 , где		j = 0,1,2 .	То есть indx ≡ 20,44,68 mod72 .

Поэтому x ≡ g20 , g44 , g68 mod73 .

Подставляя g = 5, окончательно получаем: x ≡18,71,57 mod 73 .