Математические основы защиты информации

 
 

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное автономное образовательное 
учреждение высшего образования 
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
 
 
 
 
 
 
В. С. Пилиди 

 
МАТЕМАТИЧЕСКИЕ ОСНОВЫ  

ЗАЩИТЫ ИНФОРМАЦИИ 

 

 

 

Рекомендовано экспертным советом по направлению  
«Математика, механика, информатизация» ЮФУ  
в качестве учебного пособия  
для студентов, обучающихся по направлениям подготовки 
«Фундаментальная информатика и информационные технологии»  
и «Прикладная математика и информатика» 
 

 

 

 

 

Ростов-на-Дону – Таганрог 
Издательство Южного федерального университета 
2019 

 
 

УДК 511+512.5  
ББК 22.13+22.144 
     П32 

 
Печатается по решению экспертного совета «Математика, механика, 
информатизация» Южного федерального университета  
(протокол № 1 от 25 ноября 2019 г.) 
 
Р е ц е н з е н т ы :  
кандидат технических наук, доцент, заведующий кафедрой 
«Программное обеспечение вычислительной техники 
и автоматизированных систем» ФГБОУ ВО ДГТУ 
В. В. Долгов; 
кандидат физико-математических наук,  
доцент кафедры алгебры и дискретной математики 
института математики, механики и компьютерных наук 
Южного федерального университета 
С. С. Михалкович 
 

Пилиди, В. С. 
П32      Математические основы защиты информации : учебное пособие 
/ В. С. Пилиди ; Южный федеральный университет. – Ростов-на-Дону ; 
Таганрог : Издательство Южного федерального университета, 2019.        
–  308 с. 

ISBN 978-5-9275-3363-3 
 

Настоящая книга представляет собой учебник по математическим основам 
защиты информации. Она посвящена изложению основ теории чисел и общей 
алгебры, в ней среди прочего рассматриваются такие вопросы как делимость чисел 
и мультипликативные функции, теория групп, элементы теории колец и полей, 
символы Лежандра и Якоби, тестирование чисел на простоту и дискретное 
логарифмирование. Во второе издание книги добавлены главы, посвященные 
введению в криптографию и теорию информации. Приведены решения всех 
имеющихся в тексте задач. 
Пособие может быть использовано студентами, обучающимися по программам бакалавриата направлений подготовки «Фундаментальная информатика 
и информационные технологии» и «Прикладная математика и информатика». 
Публикуется в авторской редакции. 
УДК 511+512.5  
ББК 22.13+22.144 

ISBN 978-5-9275-3363-3 
© Южный федеральный университет, 2019  
© Пилиди В. С., 2019 

Введение

Хорошо известно, какую важную роль играют алгебра и теория чисел в алгоритмах защиты информации. Предлагаемая книга написана на
основе читаемых автором курсов «Теория чисел», «Общая алгебра», «Математические основы защиты информации», ориентированных на студентов, обучающихся по направлениям подготовки «Фундаментальная информатика и информационные технологии» и «Прикладная математика
и информатика», специализация «Защита информации».

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

Приводимые в тексте утверждения нумеруются следующим образом:
теоремы — в пределах главы, леммы и задачи — в пределах раздела.
Знак
означает конец доказательства. В случаях, когда завершаемый
текст очень короткий, этот знак часто опускается.

Список литературы содержит небольшое число книг. Этот список является заведомо неполным и может рассматриваться только как стартовый для дальнейшего изучения теории.

Глава 1

Введение в теорию чисел

1.1
Предварительные сведения

Будем рассматривать числовые множества, каждое из которых строго содержится в следующем:
▶ N — множество всех натуральных чисел 1, 2, 3, . . . ;
▶ Z — множество всех целых чисел . . . −3, −2, −1, 0, 1, 2, 3, . . . ;
▶ Q — множество всех рациональных чисел, т.е. чисел вида m/n, где
m, n ∈ Z, n ̸= 0;
▶ R — множество всех вещественных чисел;
▶ C — множество всех комплексных чисел.
Существует аксиоматическая теория натуральных чисел. На базе этой
теории можно строго ввести и исследовать числа, принадлежащие остальным указанным выше множествам. Мы не будем излагать эту теорию,
ограничившись следующим утверждением.

Аксиома полной упорядоченности. Любое непустое множество натуральных чисел содержит наименьший элемент.

Это означает, что в произвольном непустом множестве M ⊂ N существует такой элемент a, что для любого x ∈ M выполняется неравенство
a ⩽ x. Такой элемент множества M является единственным. Действительно, если множество M содержит еще один наименьший элемент a′,
то выполняются неравенства a ⩽ a′ (поскольку a является наименьшим)
и a′ ⩽ a (поскольку наименьшим является a′). Из выписанных неравенств
следует, что a = a′.

Замечание. При строгом аксиоматическом построении теории натуральных чисел приведенная «аксиома» становится одной из теорем.

Будем использовать следующие утверждения, вытекающие из приведенной аксиомы (и, как легко заметить, равносильные этой аксиоме).

1) Пусть M — множество целых чисел, содержащее хотя бы одно на

1.2. Деление с остатком
5

туральное число. Тогда существует такое натуральное число a ∈ M, что
для любого натурального x ∈ M выполняется неравенство a ⩽ x.

2) Пусть M — множество целых чисел, содержащее хотя бы одно
неотрицательное число. Тогда существует такое неотрицательное число
a ∈ M, что для любого неотрицательного числа x ∈ M выполняется
неравенство a ⩽ x.

Число a будем называть в первом случае наименьшим положительным
числом из множества M, а во втором — наименьшим неотрицательным
числом из этого множества.

Доказательство первого утверждения сводится к рассмотрению множества M∩N. Это непустое множество натуральных чисел, и его наименьший элемент a удовлетворяет требуемому условию. Для доказательства
второго утверждения можно рассмотреть множество L = {x+1 : x ∈ M}.
Это множество содержит хотя бы одно натуральное число. Если a — наименьшее натуральное число из множества L, то a−1 — наименьшее неотрицательное число из множества M.

Из аксиомы полной упорядоченности следует, что любая строго убывающая последовательность натуральных чисел является конечной. Действительно, допустим противное, что последовательность натуральных
чисел
a1 > a2 > · · · > an > · · ·

бесконечная. Пусть a — наименьший элемент множества всех чисел, входящих в эту последовательность. Тогда a = an для некоторого n ⩾ 1, и
неравенство a = an > an+1 противоречит минимальности элемента a.

В дальнейшем, используя слово «число», если не оговорено что-то
иное, мы имеем в виду целое число.

1.2
Деление с остатком

Нам потребуется следующее важное утверждение.

Лемма 1 (о делении с остатком). Предположим, что a ∈ Z, b ∈ N.
Тогда существуют такие числа q и r, что a = bq +r, 0 ⩽ r < b. Числа q
и r, обладающие этими свойствами, находятся единственным образом.

Доказательство. Рассмотрим числовое множество M = {a − bx :
x ∈ Z}. В этом множестве есть неотрицательные числа. Действительно,
полагая x = −|a|, находим:

a − bx = a + b|a| ⩾ a + |a| ⩾ 0.

Глава 1. Введение в теорию чисел

Здесь учтено, что b ⩾ 1.

Пусть r — наименьшее неотрицательное число из множества M. Тогда
r = a−bq для некоторого q ∈ Z. Отсюда следует, что a = bq+r. Покажем,
что r < b. Действительно, допустим, что r ⩾ b. Тогда получаем:

0 ⩽ r − b = (a − bq) − b = a − b(q + 1).

Отсюда следует, что r−b ∈ M. Поскольку 0 ⩽ r−b < r, число r не может
быть наименьшим неотрицательным числом из множества M. Полученное противоречие доказывает, что r < b.

Докажем теперь единственность чисел q и r. Допустим, что имеют
место соотношения

a = bq + r,
a = bq′ + r′,
0 ⩽ r, r′ < b.

Отсюда получаем: bq + r = bq′ + r′,

b(q − q′) = r′ − r.
(1)

Допустим, что q ̸= q′. Тогда |q − q′| ⩾ 1, и из (1) получаем:

|r − r′| = |b(q − q′)| = b|q − q′| ⩾ b.

С другой стороны, из неравенств 0 ⩽ r < b, 0 ⩽ r′ < b вытекают оценки
r − r′ < b, r′ − r < b, то есть |r − r′| < b. Полученные оценки для |r − r′|
противоречат друг другу. Поэтому q = q′, и из (1) находим, что r = r′.

Замечание. Если выполняется равенство a = bq+r рассматриваемого в формулировке леммы вида, то число q называется неполным частным, а r — остатком от деления. Случай, когда r = 0, будет рассмотрен
ниже.

Определение.
Остаток от деления числа a ∈ Z на число b ∈ N
обозначается следующим образом: a mod b.

Лемма 2. Предположим, что m ∈ N и числа a, b ∈ Z связаны соотношением a = b + mt, при некотором целом t. Тогда a mod m = b mod m.

Доказательство. Обозначим b mod m = r. Тогда

b = mq + r, q, r ∈ Z, 0 ⩽ r < m,
a = b + mt = m(q + t) + r.

Поскольку отстаток от деления является единственным, получаем, что
a mod m = r.

Замечание. В отличие от приведенного нами определения операции
mod, в некоторых языках программирования в случае отрицательного
значения a или (не используемого нами) отрицательного значения b, результат такой операции может принимать отрицательное значение.

1.2. Деление с остатком
7

Теорема 1. Пусть m ⩾ 2, a, b ∈ Z. Тогда

(a + b) mod m = (a mod m + b mod m) mod m,
(a · b) mod m = ((a mod m) · (b mod m)) mod m.

Доказательство. Предположим, что a mod m = r, b mod m = s.
Тогда
a = mu + r,
b = mv + s

для некоторых u, v ∈ Z. Отсюда следует, что

a + b = m(u + v) + (r + s),
ab = m(muv + us + vr) + rs.

Остается воспользоваться в каждом из двух последних соотношений леммой 2.

Введем две важные числовые функции. Для вещественного x определим следующие величины:
▶ ⌊x⌋ — наибольшее целое число, меньшее или равное x;
▶ ⌈x⌉ — наименьшее целое число, большее или равное x.
Например, ⌊3.45⌋ = 3, ⌈3.45⌉ = 4, ⌊−3.45⌋ = −4, ⌈−3.45⌉ = −3.
Функция ⌊x⌋ носит название «целая часть» и обозначается также через [x].

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

Отметим следующие простые свойства введенных функций (здесь и
далее знак ”⇔” означает «тогда и только тогда»):

1) Для произвольного x ∈ R ⌊−x⌋ = −⌈x⌉, ⌈−x⌉ = −⌊x⌋.
2) Для любых x ∈ R, n ∈ Z ⌊x + n⌋ = ⌊x⌋ + n, ⌈x + n⌉ = ⌈x⌉ + n,

⌊x⌋ = n
⇔
n ⩽ x < n + 1
⇔
x − 1 < n ⩽ x;
⌈x⌉ = n
⇔
n − 1 < x ⩽ n
⇔
x ⩽ n < x + 1,

Задача 1.1. Доказать следующие свойства, где x обозначает вещественное число, n — целое число:

⌊x⌋ < n
⇔
x < n;
⌊x⌋ > n
⇔
x ⩾ n + 1;
⌈x⌉ < n
⇔
x ⩽ n − 1;
⌈x⌉ > n
⇔
x > n;
⌊x⌋ ⩽ n
⇔
x < n + 1;
⌊x⌋ ⩾ n
⇔
x ⩾ n;
⌈x⌉ ⩽ n
⇔
x ⩽ n;
⌈x⌉ ⩾ n
⇔
x > n − 1.

Глава 1. Введение в теорию чисел

Задача 1.2. Доказать, что для любого целого n выполняются соотношения
1) n =
n

2

+
n

2

;

2) n =
n

2

+
n + 1

2

;

3) n =
n

3

+
n + 1

3

+
n + 2

3

.

4) Сформулировать и доказать обобщение свойств 2) и 3) на случай
произвольного натурального знаменателя в правой части.

Задача 1.3. Предположим, что −∞ < a < b < +∞, I — промежуток
с концами a и b. Обозначим через N количество целых чисел, содержащихся в I. Доказать, что

N =

⌊b⌋ − ⌈a⌉ + 1,
если I = [a, b],
⌈b⌉ − ⌈a⌉,
если I = [a, b),
⌊b⌋ − ⌊a⌋,
если I = (a, b],
⌈b⌉ − ⌊a⌋ − 1,
если I = (a, b).

1.3
Отношение делимости

Пусть a, b ∈ Z, причем b ̸= 0. Говорят, что число b делит число a,
если существует такое c ∈ Z, что a = bc.

Наличие такого соотношения отмечается следующим образом: b | a. Если указанное свойство не имеет места, это записывается так: b ∤ a. Например, 3 | 6, 4 ∤ 6.

Замечание 1. При наличии соотношения b | a иногда говорят так: b
является делителем числа a, или a кратно b.

Замечание 2. Любое ненулевое число b является делителем числа 0,
поскольку 0 = b · 0.

Замечание 3.
Для любого a ∈ Z выполняется соотношение 1 | a,
поскольку a = 1 · a.

Замечание 4. Числа a и −a имеют одинаковые делители. Действительно, пусть d | a, тогда a = dc для некоторого целого c. Из соотношения
−a = d(−c) получаем, что d | (−a).

Отметим теперь некоторые свойства отношения делимости.
1) Если a | b и b | c, то a | c (транзитивность отношения делимости).

Если c = bk и b = al, то, исключая число b в первом равенстве с
помощью второго, получаем: c = a(kl), a | c.

1.4. Наибольший общий делитель
9

2) Если b | a1, b | a2, ..., b | ak, то для любых чисел c1, c2, ..., ck

b | (a1c1 + a2c2 + · · · + akck).

Действительно, из соотношений a1 = bq1, a2 = bq2, . . . , ak = bqk получаем:

a1c1 + a2c2 + · · · + akck = bq1c1 + bq2c2 + · · · + bqkck =
= b(q1c1 + q2c2 + · · · + qkck).

3) Если b | a и a ̸= 0, то |b| ⩽ |a|.
Из соотношений a = bc, a ̸= 0 следует, что c ̸= 0, следовательно,
|c| ⩾ 1. Тогда |a| = |b| · |c| ⩾ |b|.

4) Если a | b и b | a, то a = ±b.
Из предыдущего свойства получаем оценки |a| ⩽ |b| и |b| ⩽ |a|. Отсюда
вытекает, что |a| = |b|, a = ±b.

Из свойства 4) немедленно получаем такое утверждение.
5) Если a, b ∈ N, a | b и b | a, то a = b.
6) Если a | b, то da | db для любого d ∈ Z, d ̸= 0.
Это утверждение непосредственно вытекает из определения отношения делимости.

7) Если b | a, d | a и d | b, то b

d

a

d.

Действительно, пусть a = bc, a = a1d, b = b1d для некоторых a1,
b1 ∈ Z. Исключаем числа a и b в первом равенстве: a1d = b1dc. Сокращая
обе части на d, получаем: a1 = b1c, a1 | b1.

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

1.4
Наибольший общий делитель

Определение.
Ненулевое число b называется общим делителем чисел a1, a2, . . . , ak, если b делит каждое из этих чисел.

Определение.
Пусть a1, a2, . . . , ak (k ⩾ 2) — числа, не равные нулю одновременно. Наибольшим общим делителем этих чисел называется
число d, обладающее следующими свойствами:
1) d | a1, d | a2, . . . , d | ak;
2) если d′ | a1, d′ | a2, . . . , d′ | ak, то d′ | d.
Иначе говоря, наибольший общий делитель — это общий делитель,
который делится на любой общий делитель этих чисел.

Глава 1. Введение в теорию чисел

Теорема 2. Пусть a1, a2, ..., ak (k ⩾ 2) — числа, не равные нулю одновременно. Тогда наибольший общий делитель этих чисел существует
и находится единственным образом с точностью до знака.

Доказательство. Ограничимся рассмотрением случая k = 2. Пусть
a и b — числа, не обращающиеся в нуль одновременно. Обозначим через M
множество всех чисел вида au + bv, где u, v ∈ Z. Существуют положительные числа, принадлежащие множеству M. Действительно, полагая
u = a, v = b, получаем: au + bv = a2 + b2 ⩾ 1.

Обозначим через d наименьшее натуральное число из множества M
и покажем, что число d является наибольшим общим делителем чисел a
и b. Отметим сначала, что число d, будучи элементом множества M, допускает представление вида

d = au0 + bv0
(2)

с некоторыми u0, v0 ∈ Z.

Покажем, что d | a. Действительно, разделим число a с остатком на d:

a = dc + r,
0 ⩽ r < d.

Выражая из последнего соотношения r и исключая d по формуле (2),
получаем:

r = a − dc = a − c(au0 + bv0) = a(1 − cu0) + b(−cv0).

Отсюда следует, что r ∈ M. Число d является наименьшим положительным в множестве M. Поэтому из неравенства 0 ⩽ r < d вытекает, что
r = 0. Мы доказали, что d | a. Аналогично получаем, что d | b.

Теперь допустим, что d′ | a, d′ | b. Тогда из соотношения (2) получаем,
что d′ | d. Мы доказали, что число d является наибольшим общим делителем.

Докажем теперь единственность наибольшего общего делителя. Предположим, что числа d и d′ являются наибольшими общими делителями
чисел a и b. Наибольший общий делитель двух чисел является, в частности, общим делителем этих чисел. Учитывая, что d — наибольший общий
делитель указанных чисел, а d′ — общий делитель, получаем, что d′ | d.
Аналогично находим, что d | d′. Из полученных соотношений следует, что
d = ±d′.

Следствие 1. Положительный наибольший общий делитель чисел
a1, a2, ..., ak (k ⩾ 2), не равных нулю одновременно, определяется этими числами однозначно.