Методы и средства криптографической защиты информации. Практический курс

ВЫСШЕЕ ОБРАЗОВАНИЕ 
 
 
 
 
 
 
 
 
Д.В. МАРШАКОВ 
Д.В. ФАХТИ 
 
 
 
 
 
МЕТОДЫ И СРЕДСТВА 
КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ 
ИНФОРМАЦИИ 
 
ПРАКТИЧЕСКИЙ КУРС 
 
 
УЧЕБНОЕ ПОСОБИЕ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва 
ИНФРА-М 
2022 
 
 
 

УДК 003.26(075.8) 
ББК 16.84я73 
       М30 

ФЗ  

№ 436-ФЗ 

Издание не подлежит маркировке  

в соответствии с п. 1 ч. 2 ст. 1 

 
 
 
 
Маршаков Д.В. 
М30 
Методы и средства криптографической защиты информации. Практический курс : 
учебное пособие / Д.В. Маршаков, Д.В. Фахти. — Москва : ИНФРА-М, 2022. — 76 с. — 
(Высшее образование). 
 
ISBN 978-5-16-110842-0 (online) 
 
Учебное пособие содержит основной теоретический материал по базовым разделам 
криптографии. Рассмотренные разделы включают в себя теоретическую часть, методические 
примеры, расчетные задачи и упражнения для самостоятельного выполнения. Приведены 
схемы, формулы и справочные пояснения работы криптографических алгоритмов. Особое 
внимание уделено математическим основам, алгоритмической реализации и применению 
криптографических методов защиты информации.  
Адресовано обучающимся бакалавриата, специалитета и магистратуры по направлениям 
подготовки 
«Информационная 
безопасность» 
и 
«Информационная 
безопасность 
телекоммуникационных систем». 
 
УДК 003.26(075.8) 
ББК 16.84я73 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ISBN 978-5-16-110842-0 (online) 
© Маршаков Д.В., Фахти Д.В., 2022 

ОГЛАВЛЕНИЕ 
ВВЕДЕНИЕ ............................................................................................................................................. 4 
1. МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОГРАФИИ С ОТКРЫТЫМ КЛЮЧОМ .................... 5 
1.1. Деление с остатком. Алгоритм Евклида. Множители Безу .................................................... 5 
Задания для самостоятельной работы ....................................................................................... 8 
Контрольные вопросы ................................................................................................................... 8 
1.2. Сравнения по модулю в классах вычетов ................................................................................. 9 
Задания для самостоятельной работы ..................................................................................... 11 
Контрольные вопросы ................................................................................................................. 11 
1.3. Сравнения первой степени ....................................................................................................... 11 
Задания для самостоятельной работы ..................................................................................... 13 
Контрольные вопросы ................................................................................................................. 13 
1.4. Применение функции Эйлера .................................................................................................. 13 
Задания для самостоятельной работы ..................................................................................... 17 
Контрольные вопросы ................................................................................................................. 17 
1.5. Применение теоремы Эйлера и Ферма ................................................................................... 18 
Задания для самостоятельной работы ..................................................................................... 19 
Контрольные вопросы ................................................................................................................. 19 
1.6. Криптосистема шифрования информации на основе алгоритма RSA ................................. 20 
Задания для самостоятельной работы ..................................................................................... 24 
Контрольные вопросы ................................................................................................................. 24 
1.7. Криптосистема электронной подписи по протоколу RSA .................................................... 24 
Задания для самостоятельной работы ..................................................................................... 26 
Контрольные вопросы ................................................................................................................. 26 
2. АЛГОРИТМЫ И МЕТОДЫ КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ ИНФОРМАЦИИ............. 27 
2.1. Элементы блочного шифрования информации с закрытым ключом .................................. 27 
Задания для самостоятельной работы ..................................................................................... 29 
Контрольные вопросы ................................................................................................................. 32 
2.2. Поточное шифрование информации ....................................................................................... 33 
Задания для самостоятельной работы ..................................................................................... 36 
Контрольные вопросы ................................................................................................................. 43 
2.3. Исследование качества генераторов псевдослучайных чисел .............................................. 43 
Задания для самостоятельной работы ..................................................................................... 44 
Контрольные вопросы ................................................................................................................. 47 
2.4. Алгоритмическая реализация симметричной криптосистемы на основе шифра DES....... 47 
Задания для самостоятельной работы ..................................................................................... 52 
Контрольные вопросы ................................................................................................................. 55 
2.5. Алгоритмическая реализация асимметричной криптосистемы на основе шифра RSA..... 56 
Задания для самостоятельной работы ..................................................................................... 56 
Контрольные вопросы ................................................................................................................. 58 
2.6. Построение хэш-функций на примере алгоритма MD5 ........................................................ 59 
Задания для самостоятельной работы ..................................................................................... 61 
Контрольные вопросы ................................................................................................................. 63 
2.7. Алгоритмическая реализация криптосистемы электронной подписи по схеме  
Эль-Гамаля ........................................................................................................................................ 64 
Задания для самостоятельной работы ..................................................................................... 65 
Контрольные вопросы ................................................................................................................. 66 
ПРИЛОЖЕНИЯ .................................................................................................................................... 67 
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ................................................................................................. 76 
 

ВВЕДЕНИЕ 
 
Изначально криптография представлялась как наука о шифрах и применялась 
преимущественно для защиты государственных и военных секретов. Однако возможности 
криптографии на современном этапе её развития значительно шире и помимо шифрования 
данных и сообщений с целью обеспечения их конфиденциальности, включает в себя также 
контроль их целостности, аутентификацию данных, защиту программ от несанкционированного 
копирования и распространения, организацию парольных систем и пр. Современная 
криптография как наука представляет собой отдельное направление, сформированное на стыке 
математики и информатики, а практическое применение криптографических средств и методов 
стало неотъемлемой частью жизни современного общества, в частности в таких отраслях как 
электронная коммерция, электронный документооборот, телекоммуникации и пр.  
Все это в аспекте подготовки кадров по естественнонаучным и техническим 
направлениям в области информационной безопасности обуславливает необходимость 
изучения основных алгоритмов и методов криптографической защиты информации, базовых 
принципов построения криптографических систем. 
Под криптографической системой понимают совокупность пространства открытых 
текстов 
(нешифрованных 
данных), 
пространства 
шифротекстов, 
пространства 
криптографических ключей, алгоритмов шифрования и расшифровывания. Реализация 
криптографических систем немыслима без знания некоторых разделов теории алгоритмов, 
теории чисел и универсальной алгебры, лежащих в основе средств и методов современной 
криптографии.  
Целью данного учебного пособия является практическое освоение теоретических основ 
криптографической защиты информации, для чего приводятся расчетные задачи и 
практические упражнения по базовым разделам криптографии.  
Учебное пособие содержит два раздела.  
В первом разделе внимание уделено основам математического аппарата, с помощью 
которого реализуются используемые в настоящее время криптосистемы с открытым ключом, а 
также содержится описание широко распространенной системы RSA. Приведены теоретические 
выкладки, методические примеры, практические задачи и упражнения для самостоятельной 
работы. 
Во втором разделе рассмотрены базовые методы криптографической защиты 
информации, в том числе симметричного и асимметричного шифрования, хэширования и 
электронной подписи – приведены их теоретические обоснования, а также даны примеры и 
задания для их алгоритмической реализации с применением пакетов прикладных программ 
Mathcad и MATLAB. 
Рассмотренные в пособии примеры включают в себя как хорошо известные задачи, так и 
оригинальные, предназначенные для более глубокого понимания теории базовых средств и 
методов криптографической защиты информации, применяемых для решения задач 
профессиональной деятельности. 
 

1. МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОГРАФИИ 
С ОТКРЫТЫМ КЛЮЧОМ 
 
1.1. Деление с остатком. Алгоритм Евклида. Множители Безу 
 
Большинство криптографических систем с открытым ключом основаны на факторизации 
больших чисел, а надежность на трудности вычисления дискретных логарифмов. При этом в 
криптографии рассматриваются преимущественно целые числа и арифметические операции над 
ними, вследствие чего изучение основных механизмов криптографических преобразований не 
представляется возможным без рассмотрения основных понятий и определений из теории 
чисел. 
Введем следующие обозначения: 
ℕ = {1,2,3,…} – множество натуральных чисел; 
ℤ = {0, ±1, ±2, ±3,…} – множество целых чисел; 
ℚ – множество рациональных чисел вида 
q
p/
, где p и q – целые числа, 
0
≠
q
. 
Класс рациональных чисел включает в себя все целые числа ℤ, которые, в свою очередь, 
включают в себя все натуральные числа ℕ.  
На множестве целых чисел определены операции сложения, вычитания и умножения, 
обладающие свойствами дистрибутивности, ассоциативности и пр. Результатом суммы, 
разности и произведения двух целых чисел также является целое число. Операция деления 
выполняется не для всех пар целых чисел. Если целое число a делится на целое число 
0
≠
b
, что 
можно записать как 

q
b
a
=
/
, 
то в этом случае говорят, что «число b делит число a»1 и число b называется делителем числа a. 
Число a в этом случае называется кратное числа b, а полученное в результате деления число q – 
частное от деления a на b, q ∈ ℤ. Полученную запись можно также представить как 

bq
a =
. 
Число 0 делится на любое целое 
0
≠
b
. Если 
0
≠
a
, то множество всех делителей числа a 
является конечным. 
Рассмотрим несколько утверждений, определений и теорем, полезных при дальнейшем 
рассмотрении материала [3]. Утверждения, для наилучшего усвоения приводятся с 
доказательствами, некоторые теоремы в силу громоздкости доказательств оставляются без них, 
но с ними можно подробно ознакомиться в [11]. 
Утверждение. Если a,b,c ∈ ℤ и 
b
c/
, и 
a
b/ , то 
a
c/
. 
Доказательство. Поскольку известно, что 
b
c/
 и 
a
b /
, то для каждого случая имеются 
целые числа q1 и q2, представляющие собой частное от деления, т.е. 
1
/
q
b
c
=
 и 
2
/
q
a
b
=
, что 
можно записать в виде: 
с
q
b
1
=
 и 
b
q
a
2
=
. Отсюда путем подстановки имеем 
qc
с
q
q
a
=
=
2
1
, 
поскольку умножение двух целых чисел q1 и q2 даст в результате также некое целое число q. 
Тогда, по определению, 
a
c/
. 
Утверждение. Если a,b,c ∈ ℤ и 
c
a / , и 
c
b/ , то тогда 
c
b
a
/
±
. 
Доказательство. По аналогии с предыдущим доказательством, имеем 
c
q
a
1
=
 и 
c
q
b
2
=
. 
Тогда 
cq
q
q
c
c
q
c
q
b
a
=
±
=
±
=
±
)
(
2
1
2
1
, где q – некое целое число. Следовательно, 
b
a ±
делятся 
на c. 
Утверждение. Если a,b,k ∈ ℤ и 
b
a/ , то тогда 
b
ak /
. 
Доказательство. Имеем 
b
q
a
1
=
 при целом числе q1. Тогда 
qb
bk
q
ak
=
=
1
, где 
k
q
q
1
=
 – 
некое целое число. Следовательно, ak делятся на b. 
Утверждение. Если a,b,d ∈ ℤ и 
b
a
m
+
=
, 
m
d /
 и 
a
d /
, то 
n
a
d /
. 
Доказательство. По аналогии с предыдущим доказательством, по определению 
известно, 
что 
d
q
m
1
=
 
и 
d
q
a
2
=
. 
Тогда 
из 
равенства 
b
a
m
+
=
 
следует, 
что 

                     
1 Утверждение о том, что b делит a в теории чисел обозначается b/a. 

qd
d
q
q
d
q
d
q
b
=
−
=
−
=
)
(
2
1
2
1
, где q – некое целое число.  Отсюда получается, что если 

n
n
a
a
a
a
m
+
+
+
+
=
−1
2
1

, и число d делит числа, составляющие m, а именно 
1
1
,
,
−
n
a
a 
, то оно 
будет делить и an, т.е. 
n
a
d /
. 
Теорема о делении с остатком. Если a и b являются целыми числами и 
0
≠
b
, то 
существуют единственные целые числа q и r такие, что 
r
bq
a
+
=
 и 
b
r <
≤
0
. Число q 
называется неполным частным от деления a на b, число r – остатком от деления a на b.  
Приведем пример деления с остатком. Пусть 
12
=
b
, тогда для чисел 
110
=
a
, 
53
−
=
a
 и 

156
=
a
в записи 
r
bq
a
+
=
 имеем: 

2
9
12
110
+
⋅
=
, где 
2
=
r
, 
12
=
b
, 
b
r <
; 

7
)
5
(
12
53
+
−
⋅
=
−
, где 
7
=
r
, 
12
=
b
, 
b
r <
; 

0
13
12
156
+
⋅
=
, где 
0
=
r
. 
В последнем случае говорят, что число a делится на число b нацело. 
Определение. Общим делителем двух и более чисел называется число, являющееся 
делителем каждого из этих чисел. 
Из определения следует, что если 
n
a
a
,
,
1 
 – целые числа, и хотя бы одно из них не равно 
нулю, то множество их общих делителей конечно и среди них существует наибольшее число. 
 Определение. Наибольшим общим делителем (НОД) чисел 
n
a
a
,
,
1 
 называется  
наибольший из их общих делителей.  
Наибольший общий делитель двух целых чисел a и b является натуральное число n, 
удовлетворяющее следующим условиям: 
1) n есть общий делитель чисел a и b; 
2) каждый общий делитель чисел a и b есть делитель числа n. 
Наибольший общий делитель чисел a и b существует и единственен, если хотя бы одно 
из чисел a и b отлично от нуля. Допускаются следующие обозначения НОД: НОД(a,b), gcd(a,b) 
или просто (a,b). Последнее обозначение применяется лишь в контексте отсутствия какого-либо 
иного значения. 
Алгоритм Евклида. Известен сравнительно быстрый способ нахождения НОД для пары 
целых чисел, называемый алгоритмом Евклида. 
Пусть a и b – целые числа, при этом 
a
b <
<
0
. Поделим a на b с остатком r1, затем b 
поделим на r1 c остатком r2, затем r1 поделим на r2 c остатком r3 и т.д. Каждый последующий 
остаток является натуральным числом, строго меньшим предыдущего. Данный процесс 
является конечным и закончится только тогда, когда на каком-то шаге i+1 деление выполнится 
без остатка, т.е. 
0
1 =
+
ir
, что можно представить следующим образом: 

1
1
r
bq
a
+
=
, 
 
b
r <
<
1
0
 

2
2
1
r
q
r
b
+
=
,  
1
2
0
r
r <
<
 

3
3
2
1
r
q
r
r
+
=
,  
2
3
0
r
r <
<
 
… 

n
n
n
n
r
q
r
r
+
=
−
−
1
2
, 
1
0
−
<
<
n
n
r
r
 

1
1
+
− =
n
n
n
q
r
r
. 
Для иллюстрации алгоритма Евклида найдем НОД для пары чисел (1071,462): 

.0
21
7
147
,
21
147
3
462
,
147
462
2
1071

+
⋅
=
+
⋅
=
+
⋅
=

 

Поскольку последний остаток от деления равен нулю, то НОД(1071,462) = 21. 
Определение. Число 
1
>
n
 называется простым, если оно не имеет других общих 
делителей, кроме 1 и n. Число 
1
>
n
 называется составным, если оно имеет делитель, отличный 
1 и n. 
Примерами простых чисел являются 2, 3, 5, 7, 11 поскольку все они делятся только на 1 
и на самих себя. Примерами составных чисел являются: 4, 6, 8, 9. 

Определение. Числа, не имеющие общих делителей кроме ±1, т.е. у которых НОД равен 
единице, называются взаимно простыми. 
Например, если 
1
)
,
,
(
НОД
1
=
n
a
a 
, то числа 
n
a
a
,
,
1 
 являются взаимно простыми. 
Примеры взаимно простых чисел: 2 и 5, 3 и 11, 10 и 21. 
Утверждение. Если p – простое число, то любое целое число a либо взаимно простое с 
p, либо делится на p. 
Доказательство. НОД(a,p) может быть только делитель простого числа p, который 
принимает значение 1 или p. В случае НОД(a,p) = 1 числа a и p являются взаимно простыми, а в 
случае  НОД(a,p) = p число a делится на p, т.е. 
a
p /
. 
Теорема о линейном представлении НОД (соотношение Безу). Если d – наибольший 
общий делитель двух целых чисел a и b, одно из которых отлично от нуля, т.е. НОД(a,b) = d, то 
тогда существуют такие целые числа u и v, что 

d
bv
au
=
+
. 
Из данной теоремы вытекает следствие. Если числа a и b являются взаимно простыми, 
то поскольку НОД(a,b) = 1, предыдущее уравнение принимает 

1
=
+ bv
au
 
и имеет целочисленные решения. Числа u и v называются коэффициентами (множителями) 
Безу. 
Соотношение Безу является ключевым в основной теореме арифметики, которая будет 
рассмотрена в дальнейшем. 
Для нахождения коэффициентов Безу можно использовать расширенный алгоритм 
Евклида нахождения НОД и представить остатки в виде линейных комбинаций a и b. Алгоритм 
записывается в следующем виде: 

1
1
bq
a
r
−
=
, 

2
2
1
2
1
2
2
1
2
1
2
)
1(
)
(
aq
q
q
b
q
bq
aq
b
q
bq
a
b
q
r
b
r
−
+
=
+
−
=
−
−
=
−
=
, 

)
(
)
1(
)
)
1(
(
)
(
3
2
1
3
1
3
2
3
2
2
1
1
3
2
1
3
q
q
q
q
q
b
q
q
a
q
aq
q
q
b
bq
a
q
r
r
r
+
+
−
+
=
−
+
−
−
=
−
=
, 

… 

bv
au
q
r
r
r
n
n
n
n
+
=
=
−
=
−
−

1
2
. 
Рассмотрим числовой пример, в котором требуется найти коэффициенты Безу для чисел 
81 и 26. Прежде всего, с помощью алгоритма Евклида определяется НОД(81,26): 

.0
1
2
2
,1
2
1
3
,2
3
8
26
,3
26
3
81

+
⋅
=
+
⋅
=
+
⋅
=
+
⋅
=

 

НОД(81,26) = 1. Из полученной записи выпишем остатки: 

2
1
3
1
3
8
26
2
26
3
81
3

⋅
−
=
⋅
−
=
⋅
−
=

 

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

).
28
(
26
81
9
28
26
81
9
26
1
9
26
3
9
81
26
1
9
)
26
3
81
(
26
1
9
3
26
1
)
8
1
1(
3
3
8
1
26
1
3
)
3
8
26
(
1
3
2
1
3
1
−
⋅
+
⋅
=
⋅
−
⋅
=
⋅
−
⋅
⋅
−
⋅
=
⋅
−
⋅
⋅
−
=
⋅
−
⋅
=
=
⋅
−
⋅
+
⋅
=
⋅
⋅
+
⋅
−
=
⋅
−
⋅
−
=
⋅
−
=
 

Таким образом, коэффициенты Безу равны 9 и –28. 
Утверждение. Если целое число b взаимно просто с каждым из целых чисел 
n
a
a
,
,
1 
, то 
b взаимно просто и с их произведением 
n
a
a
a
⋅
⋅
⋅

2
1
. 
Доказательство. Рассмотрим первоначально случай для двух целых чисел a1 и a2 
взаимно простых с целым числом b. Покажем, что их произведение 
2
1 a
a ⋅
 также взаимно 
просто с b. Из соотношения Безу следует, что существуют целые числа u1, v1, u2, v2 такие, что 

1
1
1
1
=
+ bv
u
a
, 
1
2
2
2
=
+ bv
u
a
. Перемножив эти равенства, после очевидных преобразований 
получим 
1
)
(
2
1
1
2
2
2
1
1
2
1
2
1
=
+
+
+
v
bv
v
u
a
v
u
a
b
u
u
a
a
, откуда следует, что числа 
2
1 a
a ⋅
 и b взаимно 
просты, поскольку u1u2 и 
2
1
1
2
2
2
1
1
v
bv
v
u
a
v
u
a
+
+
 – целые числа. 
Теперь вернемся к первоначальному утверждению, для доказательства которого 
применим метод математической индукции1. Поскольку утверждение верно при 
2
=
n
, то 
допустим, что оно верно для произведения  
1
−
n
 множителей, и в этом предположении 
докажем его для n множителей. Запишем 
n
a
a
a
⋅
⋅
⋅

2
1
 как 
)
(
2
1
n
a
a
a
⋅
⋅
. Первый множитель a1 
взаимно прост с b по условию. Второй 
n
a
a
⋅
⋅
2
 взаимно прост с b в силу индуктивного 
предположения. Следовательно, на основании первоначально рассмотренного случая, можно 
заключить, что 
n
a
a
a
⋅
⋅
⋅

2
1
 взаимно просто с b. 
 
Задания для самостоятельной работы 
 
1. Разделить с остатком число a на число b. Результат представить в виде 
r
bq
a
+
=
. 
Указать неполное частное от деления и остаток [8]. 
1) a = 115, b = 27; 
2) a = 115, b = 23; 
3) a = 7, b = 8; 
4) a = –31, b = 10; 
5) a = 14, b = –5; 
6) a = –18, b = –4. 
 
2. Используя алгоритм Евклида найти НОД(a,b) для данных пар чисел, определить какие 
из приведенных чисел являются взаимно простыми. 
1) a = 30, b = 18; 
2) a = 1071, b = 462; 
3) a = 4158, b = 1056; 
4) a = 315, b = 78; 
5) a = 123, b = 48; 
6) a = 39, b = 18. 
 
3. Используя расширенный алгоритм Евклида найти коэффициенты Безу u и v для 
следующих пар чисел [4]. Результат представить в линейной комбинации вида 
d
bv
au
=
+
.  
1) (153, 648); 
2) (83, 597); 
3) (113, 481); 
4) (1526, 748); 
5) (439, 817); 
6) (356, 499). 
 
Контрольные вопросы 
 
1. Что в записи 
q
b
a
=
/
 является делителем? Кратным? Частным от деления? 
2. Для записи 
r
bq
a
+
=
 как называются числа a, b, q, r? 
3. Сформулируйте теорему о делении с остатком. 
4. Что называется общим делителем двух чисел? 

                     
1 Математическая индукция представляет собой метод математического доказательства, применяемый для 
доказательства истинности некоторого утверждения для всех натуральных чисел n: «Если утверждение верно для 
n = 1 и из справедливости его для n = k вытекает справедливость этого утверждения для n = k + 1, то оно верно для 
всех n». 

5. Что такое наибольший общий делитель, каким условиям он должен удовлетворять и 
как обозначается? 
6. Опишите последовательность действий в алгоритме Евклида. 
7. Дайте определение простому числу, составному числу, взаимно простым числам. 
8. Сформулируйте теорему о линейном представлении НОД. 
9. Опишите алгоритм нахождения коэффициентов Безу. 
 
 
1.2. Сравнения по модулю в классах вычетов 
 
Модулярная арифметика (сравнение по модулю натурального числа) является 
математической основой современной криптографии. Её смысл состоит в том, что у любого 
выражения, в котором используются только целые числа, требуется вычислить не значение 
этого выражения, а остаток от деления этого значения на некоторое целое число m. Рассмотрим 
основные понятия модулярной арифметики. 
Пусть 
2
≥
m
 – данное натуральное число. Тогда, если отнести к одному классу числа, 
дающие один и тот же остаток при делении на m, то все целые числа по отношению к числу m 
могут быть разбиты на m классов. 
Так, если 
2
=
m
, целые числа разбиваются на классы четных и нечетных чисел. Если 

3
=
m
, классы составляют числа вида 

,2
3
,1
3
,
3
+
+
k
k
k
 при k ∈ ℤ. Рассмотрим последнее 
утверждение более наглядно (рисунок 1.1). 
Для случая 
3
=
m
 рассмотрим ось целых чисел, фрагмент которой приведен на 
рисунке 1.1, а. 
 

–1
0
1
2
3
4
5
6
7
–2
–3
–4
–5
–6
–7
 

а) 

–1
0
1
2
3
4
5
6
7
–2
–3
–4
–5
–6
–7
 

б) 

Рисунок 1.1 – Разбиение множества целых чисел на 
3
=
n
классов: 
а) исходный фрагмент оси целых чисел; б) произведенное разбиение на классы. 
 
Целые числа разбиваются на три класса, что отмечено на рисунке 2.1, б. К первому 
классу, обозначенному ●, относятся числа, отстоящие от нуля через два на третье: 0, 3, 6, –3, –6 
и т.д. Ко второму классу, обозначенному ∆, относятся числа, отстоящие от единицы через два 
на третье: 1, 4, 7, –2, –5 и т.д. К третьему классу, обозначенному □, относятся числа, отстоящие 
от двойки через два на третье: 2, 5, –1, –4, –7 и т.д. 
Таким образом, все множество целых чисел разбито на 3 множества (3 класса), которые 
называются «классы по модулю 3» и обозначаются чертой сверху: 0 , 1 , 2. Такое обозначение 
применимо и в любых других случаях – в общем случае a  обозначает класс по модулю m 
(который предполагается заданным), содержащий число a. Иная форма записи имеет вид 

)
(modm
a
, о чем будет сказано ниже. 
Принадлежность конкретного числа к классу также обозначается чертой сверху. 
Например, для данного примера 
4
2
−
=
, что означает, что число 2 и число 4 лежат в одном 
классе по модулю 3, т.е. отстоят друг от друга на число кратное 3.  
При рассмотрении классов по модулю в качестве объектов, действие над которыми 
нужно произвести, на первых порах такие обозначения вызывают затруднения, поскольку под 
классом понимается не число, а бесконечное множество чисел. Поэтому для упрощения 

рекомендуется вместо класса рассматривать одно произвольное число из этого класса, без 
различия одного от другого. 
Чтобы выполнить какое-либо действие над двумя классами, например, сложение, нужно 
взять в каждом из них по числу, сложить эти числа и рассмотреть соответствующий класс. 
Аналогично выполняется для разности и произведения. Приведем обобщенное определение. 
Определение. Суммой (разностью, произведением) двух классов по модулю m 
называется класс по модулю m, к которому принадлежит сумма (разность, произведение) каких-
либо чисел из слагаемых (вычитаемых, перемножаемых) классов: 

b
a
b
a
+
=
+
. 

b
a
b
a
−
=
−
. 

ab
b
a =
. 
Покажем корректность данного определения на примере суммы в том смысле, что какие 
бы числа из двух классов мы ни выбрали, их сумма будет принадлежать вполне определенным 
классам, не зависящим от выбора чисел внутри данных классов. Если из двух разных классов 
по модулю n выбрано по два представителя 
1a ,
2
a  и  
1b ,
2b , то каждый представитель в рамках 
одного класса отличается друг от друга на целое число раз по n, т.е. 
km
a
a
+
=
1
2
, 
tm
b
b
+
=
1
2
, 
где k,t ∈ ℤ. Тогда 
m
t
k
b
a
b
a
)
(
2
2
1
1
+
+
+
=
+
, что означает отличие суммы a1 и b1 от a2 и b2 на 

целое число шагов по m. Таким образом, 
1
1
b
a +
 и 
2
2
b
a +
 будут лежать в одном и том же классе 
по модулю n. Аналогично доказывается для разности и произведения. 
Как следствие, в случае многократного применения произведения двух классов по 
модулю m, можно получить выражение 

n
n
a
a
=
 
для любого натурального n. 
Пример. Доказать, что число 
50
100
14
49
−
 делится на 5.  
Иными словами требуется доказать, что данное число имеет остаток от деления по 
модулю 5 равный 0, т.е. что число находится в классе 0. Таким образом, работаем по модулю 5, 
что обозначается чертой сверху, после чего выполняется ряд преобразований с применением 
обозначенных выше правил: 

50
100
50
100
50
100
14
49
14
49
14
49
−
=
−
=
−
. 
Число 
1
49
−
=
, поскольку их разница, число 50, делится на 5 без остатка, т.е. данные 
числа отстают друг от друга на число кратное 5. Число 
1
14
−
=
 в силу того, что из разность, 
число 15, делится на 5. Таким образом, имеем 

0
1
1
)1
(
)1
(
)1
(
)1
(
14
49
50
100
50
100
50
100
=
−
=
−
−
−
=
−
−
−
=
−
, 
что означает, что исходное число находится в том же классе, где лежит 0, т.е. данное число 
делится на 5 без остатка. 
Определение. Два целых числа a и b называются сравнимыми по модулю m, где m ∈ ℕ, 
если их разность 
b
a −
 делится на m, что аналогично 
km
b
a
+
=
 для некоторого k ∈ ℤ.  
Высказывание «a и b сравнимы по модулю m» записывается в виде 
m
b
a
mod
≡
. 
Приведенное определение позволяет формализовать вышеописанное понятие классов чисел. Из 
него следует, что решениями сравнения 
m
b
x
mod
≡
 являются все целые числа вида 
km
b +
, где 
k ∈ ℤ, которые и образуют класс чисел по модулю m. 
Определение. Любое число из класса 
km
b +
, k ∈ ℤ, называется вычетом по модулю 
числа m.  
Каждое целое число попадает в один и только один класс попарно сравнимых между 
собой чисел. Эти классы и называются «классами вычетов по модулю m» или просто «классами 
по модулю m». 
Определение. Любая совокупность чисел, взятых по одному их каждого класса по 
модулю m, называется полной системой вычетов по модулю m. 

Например, числа 
)1
(,
,1,0
−
m

 образуют полную систему вычетов. Полной же системой 
вычетов будет 
m
,
,1 
; при нечетном 
1
2 +
= k
m
 полной системой вычетов будет 

k
k
,
,1,0,1
,
,

 −
−
 и т.д. 
Определение. Множество вычетов по модулю m, взаимно простых с модулем m, 
называется приведенной системой вычетов по модулю m. 
Числа одного и того же класса по модулю m имеют с модулем m один и тот же НОД. 
Особенно важны классы, для которых он равен 1. Взяв от каждого из таких классов по одному 
числу, получим приведенную систему вычетов по модулю m.  
Пример. Определить класс вычетов для числа 
)
10
(mod
7
3
)
8
6
(
4
⋅
+
+
⋅
. 
В исходных данных работаем по модулю 10, что обозначаем чертой сверху, после чего 
выполняется ряд преобразований 

21
14
4
21
14
4
7
3
)
8
6
(
4
+
⋅
=
+
⋅
=
⋅
+
+
⋅
. 

Число 
4
14 =
, поскольку их разница есть число 10, которое делится на 10 без остатка, 
число 
1
21= , поскольку их разностью является число 20, которое делится на 10. Тогда 

7
17
1
16
1
4
4
1
4
4
21
14
4
=
=
+
=
+
⋅
=
+
⋅
=
+
⋅
. 
Число 
7
17 =
 в силу того, что их разницей является число 10. Возможно так же решение 

3
17
−
=
 из чего следует, что число 7 и –3 лежат в одном и том же классе, но условием решения 
задачи было определение номера класса вычетов, а он должен быть положительным число от 0 
до 9. Таким образом, ответ 7. 
 
Задания для самостоятельной работы 
 
1. Доказать, что число 
222
555
555
222
+
 делится на 7. 
 
2. Определить класс вычетов [8]. 
1) 
)
20
(mod
17
13 +
; 
2) 
)
14
(mod
5
9⋅
; 
3) 
)
5
(mod
3
−
; 
4) 
)
5
(mod
35
; 
5) 
)
11
(mod
8
5
9
4
⋅
−
⋅
; 
6) 
)
18
(mod
1725
. 
 
Контрольные вопросы 
 
1. Дайте определение отношения сравнимости целых чисел по модулю m. 
2. Дайте определение класса вычетов по модулю натурального числа m. 
3. Как математически записывается высказывание «a и b сравнимы по модулю m»? 
4. Как определяются операции сложения и умножения для классов вычетов? 
5. Что называется полной системой вычетов по модулю m? 
6. Что называется приведенной системой вычетов? 
7. Какому классу вычетов соответствует число 23 (mod 5)? 
 
 
1.3. Сравнения первой степени 
 
Рассмотрим сравнение вида 
)
(mod
0
1
1
0
m
a
x
a
x
a
n
n
n
≡
+
+
+
−

. Если a0 не делится на n, то 
m называется степенью сравнения [9]. Решить сравнение  – значит найти все x, 
удовлетворяющие ему. Если приведенному сравнению удовлетворяет какое-то 
1x
x =
, то ему же 
будут удовлетворять все числа, сравнимые с x1 по модулю m: 
)
(mod
1
m
x
x ≡
. При этом весь