РОССИЙСКАЯ ФЕДЕРАЦИЯ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Федеральное бюджетное государственное образовательное
учреждение высшего профессионального образования
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНСТИТУТ МАТЕМАТИКИ, ЕСТЕСТВЕННЫХ НАУК
И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
ТЕОРЕТИКО-ЧИСЛОВЫЕ МЕТОДЫ
В КРИПТОГРАФИИ
СБОРНИК ЗАДАНИЙ (ЧАСТЬ II)
Учебно-методическое пособие
для студентов специальностей
«Компьютерная безопасность» и «Информационная безопасность автоматизированных систем»
Тюмень
Издательство
Тюменского государственного университета
2012
УДК: 003.26:519(075.8)
ББК: В973.26-018.2я73+В13я73
Н691
. Теоретико-числовые методы в криптографии. Сборник заданий (часть II): Учебно-методическое пособие для студентов IV курса ОДО специальностей 090201 – «Компьютерная безопасность» и 090105 – «Комплексное обеспечение информационной безопасности автоматизированных систем». Тюмень: Издательство ТюмГУ, 2012, 32 стр.
Учебно-методическое пособие включает задания к самостоятельной работе по курсу «Теоретико-числовые методы в криптографии», соответствующей второй дидактической единице курса «Теория квадратичных вычетов». Составлено 40 индивидуальных вариантов работы. Данное пособие предназначено для организации самостоятельной работы студентов.
Рекомендовано к печати Учебно-методической комиссией института математики, естественных наук и информационных технологий. Утверждено Учебно-методической секцией Ученого совета Тюменского государственного университета.
ОТВЕТСТВЕННЫЙ РЕДАКТОР: , заведующий кафедрой информационной безопасности ФБГОУ ВПО ТюмГУ, д. т.н., профессор.
РЕЦЕНЗЕНТЫ: , доцент кафедры информационной безопасности ФБГОУ ВПО ТюмГУ, к. т.н.
, зав. каф. алгебры и мат. логики, д. ф.-м. н., профессор.
Ó ФБГОУ ВПО Тюменский государственный университет, 2012.
Ó , 2012.
Содержание
Задания к работе №2….........………………………………………………… 4
Решение варианта 40 работы №2...……………….………………............ 24
Список литературы…………………………………………………………… 32
Задания к работе №2.
Вариант 1
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º20 (mod 31); b) x2º21 (mod 49); c) x2º2 (mod 55); d) x2º89(mod 160).
3. Решить квадратичные сравнения
a) x2º13 (mod 23); b) x2º24 (mod 53); c) x2º10 (mod 41);
d) x2º71 (mod 77); e) x2º7 (mod 9); f) x2º40 (mod 81);
g) x2º100 (mod 231); h) x2º1 (mod 110); i) x2º81 (mod 176);
j) x2º17 (mod 57).
Вариант 2
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º19 (mod 31); b) x2º22 (mod 49); c) x2º4 (mod 55); d) x2º93(mod 160).
3. Решить квадратичные сравнения
a) x2º3 (mod 23); b) x2º23 (mod 29); c) x2º41 (mod 73);
d) x2º1 (mod 15); e) x2º14 (mod 121); f) x2º31 (mod 125);
g) x2º16 (mod 105); h) x2º1 (mod 70); i) x2º1 (mod 96);
j) x2º18 (mod 73).
Вариант 3
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º6 (mod 43); b) x2º33 (mod 35); c) x2º3 (mod 121); d) x2º5 (mod 80).
3. Решить квадратичные сравнения
a) x2º18 (mod 23); b) x2º7 (mod 29); c) x2º48 (mod 73);
d) x2º4 (mod 15); e) x2º11 (mod 25); f) x2º19 (mod 125);
g) x2º9 (mod 385); h) x2º9 (mod 70); i) x2º1 (mod 48);
j) x2º63 (mod 79).
Вариант 4
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º22(mod 43); b) x2º29(mod 35); c) x2º14(mod 121); d) x2º41(mod 80).
3. Решить квадратичные сравнения:
a) x2º12 (mod 23); b) x2º3 (mod 61); c) x2º2 (mod 73);
d) x2º25 (mod 33); e) x2º15 (mod 49); f) x2º55 (mod 81);
g) x2º1 (mod 165); h) x2º53 (mod 154); i) x2º81 (mod 160);
j) x2º21 (mod 43).
Вариант 5
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º3(mod 5); b) x2º17 (mod 77); c) x2º19(mod 121); d) x2º47 (mod 64).
3. Решить квадратичные сравнения
a) x2º8 (mod 23); b) x2º34 (mod 37); c) x2º32 (mod 73);
d) x2º26 (mod 55); e) x2º30 (mod 49); f) x2º37 (mod 81);
g) x2º124 (mod 165); h) x2º71 (mod 110); i) x2º57 (mod 112);
j) x2º33 (mod 40).
Вариант 6
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º22(mod 43); b) x2º29(mod 35); c) x2º14(mod 121); d) x2º43 (mod 64).
3. Решить квадратичные сравнения
a) x2º6 (mod 23); b) x2º15 (mod 53); c) x2º8 (mod 41);
d) x2º16 (mod 77); e) x2º53 (mod 121); f) x2º29 (mod 125);
g) x2º163 (mod 231); h) x2º37 (mod 84); i) x2º137 (mod 224);
j) x2º17 (mod 24).
Вариант 7
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) ; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º5 (mod 17); b) x2º19 (mod 55); c) x2º7(mod 9); d) x2º33 (mod 64).
3. Решить квадратичные сравнения
a) x2º5 (mod 31); b) x2º27 (mod 37); c) x2º39 (mod 41);
d) x2º21 (mod 35); e) x2º92 (mod 121); f) x2º22 (mod 81);
g) x2º191 (mod 385); h) x2º23 (mod 154); i) x2º49 (mod 176);
j) x2º9 (mod 26).
Вариант 8
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º37(mod 101); b) x2º13(mod 35); c) x2º34(mod 169); d) x2º11(mod 32).
3. Решить квадратичные сравнения
a) x2º18 (mod 31); b) x2º33 (mod 37); c) x2º33 (mod 41);
d) x2º53 (mod 77); e) x2º37 (mod 49); f) x2º74 (mod 125);
g) x2º1 (mod 105); h) x2º11 (mod 70); i) x2º65 (mod 224);
j) x2º15 (mod 91).
Вариант 9
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º5 (mod 19); b) x2º7 (mod 15); c) x2º17(mod 121); d) x2º 7 (mod 12).
3. Решить квадратичные сравнения
a) x2º2 (mod 31); b) x2º28 (mod 29); c) x2º50 (mod 73);
d) x2º16 (mod 21); e) x2º46 (mod 49); f) x2º34 (mod 125);
g) x2º49 (mod 165); h) x2º9 (mod 110); i) x2º41 (mod 80);
j) x2º3 (mod 97).
Вариант 10
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) ; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º12(mod 89); b) x2º17(mod 82); c) x2º115(mod 289); d) x2º5(mod 16).
3. Решить квадратичные сравнения
a) x2º19 (mod 31); b) x2º11 (mod 53); c) x2º3 (mod 73);
d) x2º49 (mod 55); e) x2º119 (mod 121); f) x2º43 (mod 81);
g) x2º4 (mod 231); h) x2º91 (mod 110); i) x2º1 (mod 224);
j) x2º19 (mod 101).
Вариант 11
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º5 (mod 68); b) x2º11 (mod 23); c) x2º19 (mod 27); d) x2º 3 (mod 169).
3. Решить квадратичные сравнения
a) x2º7 (mod 31); b) x2º37 (mod 53); c) x2º54 (mod 73);
d) x2º4 (mod 35); e) x2º6 (mod 25); f) x2º34 (mod 81);
g) x2º64 (mod 385); h) x2º25 (mod 66); i) x2º89 (mod 176);
j) x2º48 (mod 87).
Вариант 12
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º17(mod 59); b) x2º17(mod 48); c) x2º31(mod 125); d) x2º13 (mod 16).
3. Решить квадратичные сравнения
a) x2º28 (mod 31); b) x2º60 (mod 61); c) x2º5 (mod 41);
d) x2º4 (mod 55); e) x2º3 (mod 121); f) x2º67 (mod 81);
g) x2º37 (mod 231); h) x2º81 (mod 154); i) x2º73 (mod 96);
j) x2º7 (mod 65).
Вариант 13
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º3 (mod 83); b) x2º9 (mod 62); c) x2º19 (mod 121); d) x2º 13 (mod 44).
3. Решить квадратичные сравнения
a) x2º20 (mod 31); b) x2º26 (mod 37); c) x2º40 (mod 41);
d) x2º9 (mod 77); e) x2º29 (mod 49); f) x2º71 (mod 125);
g) x2º58 (mod 231); h) x2º69 (mod 110); i) x2º9 (mod 80);
j) x2º16 (mod 75).
Вариант 14
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º19 (mod 67); b) x2º21 (mod 48); c) x2º16 (mod 39); d) x2º17(mod 32).
3. Решить квадратичные сравнения
a) x2º14 (mod 31); b) x2º43 (mod 53); c) x2º8 (mod 73);
d) x2º36 (mod 77); e) x2º43 (mod 49); f) x2º86 (mod 125);
g) x2º144 (mod 385); h) x2º37 (mod 154); i) x2º1 (mod 176);
j) x2º27 (mod 63).
Вариант 15
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º15 (mod 61); b) x2º11(mod 35); c) x2º13 (mod 49); d) x2º9 (mod 40).
3. Решить квадратичные сравнения
a) x2º10 (mod 31); b) x2º22 (mod 29); c) x2º37 (mod 73);
d) x2º4 (mod 33); e) x2º48 (mod 121); f) x2º70 (mod 81);
g) x2º46 (mod 105); h) x2º37 (mod 66); i) x2º25 (mod 112);
j) x2º39 (mod 41).
Вариант 16
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º13 (mod 83); b) x2º21(mod 289); c) x2º16(mod 39); d) x2º17(mod 32).
3. Решить квадратичные сравнения
a) x2º8 (mod 31); b) x2º11 (mod 37); c) x2º18 (mod 73);
d) x2º14 (mod 55); e) x2º78 (mod 121); f) x2º66 (mod 125);
g) x2º31 (mod 165); h) x2º39 (mod 70); i) x2º41 (mod 160);
j) x2º17 (mod 33).
Вариант 17
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º13 (mod 43); b) x2º10(mod 33); c) x2º66 (mod 125); d) x2º9 (mod 80).
3. Решить квадратичные сравнения
a) x2º6 (mod 43); b) x2º20 (mod 29); c) x2º24 (mod 73);
d) x2º34 (mod 55); e) x2º2 (mod 49); f) x2º51 (mod 125);
g) x2º136 (mod 165); h) x2º49 (mod 120); i) x2º81 (mod 224);
j) x2º13 (mod 25).
Вариант 18
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º21 (mod 79); b) x2º18 (mod 121); c) x2º2(mod 35); d) x2º17 (mod 32).
3. Решить квадратичные сравнения
a) x2º21 (mod 43); b) x2º5 (mod 29); c) x2º61 (mod 73);
d) x2º64 (mod 77); e) x2º24 (mod 25); f) x2º46 (mod 81);
g) x2º25 (mod 231); h) x2º81 (mod 110); i) x2º25 (mod 96);
j) x2º15 (mod 17).
Вариант 19
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º21 (mod 43); b) x2º 17 (mod 38); c) x2º19 (mod 49); d) x2º9 (mod 36).
3. Решить квадратичные сравнения
a) x2º38 (mod 43); b) x2º28 (mod 37); c) x2º32 (mod 41);
d) x2º25 (mod 77); e) x2º19 (mod 25); f) x2º24 (mod 125);
g) x2º16 (mod 165); h) x2º51 (mod 70); i) x2º25 (mod 224);
j) x2º29 (mod 49).
Вариант 20
1. Вычислить символ Якоби:
а) ; b) ; c) ; d) 
; e) ; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º15 (mod 97); b) x2º13 (mod 125); c) x2º 12(mod 77); d) x2º1(mod 24).
3. Решить квадратичные сравнения
a) x2º14 (mod 43); b) x2º47 (mod 53); c) x2º20 (mod 73);
d) x2º4 (mod 77); e) x2º71 (mod 121); f) x2º76 (mod 81);
g) x2º1 (mod 385); h) x2º89 (mod 110); i) x2º9 (mod 112);
j) x2º23 (mod 49).
Вариант 21
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º35 (mod 43); b) x2º17 (mod 38); c) x2º19 (mod 49); d) x2º9 (mod 36).
3. Решить квадратичные сравнения
a) x2º35 (mod 43); b) x2º10 (mod 53); c) x2º2 (mod 41);
d) x2º29 (mod 35); e) x2º44 (mod 49); f) x2º73 (mod 81);
g) x2º36 (mod 385); h) x2º9 (mod 154); i) x2º1 (mod 80);
j) x2º31 (mod 217).
Вариант 22
1. Вычислить символ Якоби:
а) 
; b) 
; c) ; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º15 (mod 97); b) x2º13 (mod 125); c) x2º12(mod 77); d) x2º1(mod 24).
3. Решить квадратичные сравнения
a) x2º15 (mod 43); b) x2º44 (mod 53); c) x2º23 (mod 73);
d) x2º4 (mod 21); e) x2º104 (mod 121); f) x2º58 (mod 81);
g) x2º148 (mod 231); h) x2º71 (mod 154); i) x2º9 (mod 160);
j) x2º21 (mod 43).
.
Вариант 23
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º5 (mod 19); b) x2º7 (mod 15); c) x2º17(mod 121); d) x2º7 (mod 12).
3. Решить квадратичные сравнения:
a) x2º40 (mod 43); b) x2º17 (mod 53); c) x2º35 (mod 73);
d) x2º9 (mod 35); e) x2º115 (mod 121); f) x2º6 (mod 125);
g) x2º67 (mod 231); h) x2º25 (mod 84); i) x2º9 (mod 176);
j) x2º3 (mod 97).
Вариант 24
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º12(mod 89); b) x2º17(mod 82); c) x2º115(mod 289); d) x2º5(mod 16).
3. Решить квадратичные сравнения
a) x2º24 (mod 43); b) x2º39 (mod 61); c) x2º23 (mod 41);
d) x2º1 (mod 35); e) x2º8 (mod 49); f) x2º104 (mod 125);
g) x2º4 (mod 105); h) x2º137 (mod 154); i) x2º137 (mod 176);
j) x2º21 (mod 101).
Вариант 25
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º5 (mod 31); b) x2º18 (mod 49); c) x2º3 (mod 55); d) x2º13(mod 160).
3. Решить квадратичные сравнения
a) x2º10 (mod 43); b) x2º6 (mod 29); c) x2º67 (mod 73);
d) x2º9 (mod 55); e) x2º23 (mod 121); f) x2º19 (mod 81);
g) x2º71 (mod 385); h) x2º29 (mod 70); i) x2º97 (mod 176);
j) x2º18 (mod 57).
Вариант 26
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º21 (mod 31); b) x2º40 (mod 49); c) x2º6 (mod 55); d) x2º17(mod 160).
3. Решить квадратичные сравнения
a) x2º41 (mod 43); b) x2º22 (mod 61); c) x2º18 (mod 41);
d) x2º67 (mod 77); e) x2º14 (mod 25); f) x2º10 (mod 81);
g) x2º64 (mod 105); h) x2º67 (mod 154); i) x2º25 (mod 48);
j) x2º72 (mod 73).
Вариант 27
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º35(mod 43); b) x2º3 (mod 35); c) x2º5 (mod 121); d) x2º9 (mod 80).
3. Решить квадратичные сравнения
a) x2º31 (mod 43); b) x2º13 (mod 29); c) x2º12 (mod 73);
d) x2º1 (mod 21); e) x2º82 (mod 121); f) x2º7 (mod 81);
g) x2º130 (mod 231); h) x2º1 (mod 84); i) x2º9 (mod 224);
j) x2º78 (mod 79).
Вариант 28
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º27(mod 43); b) x2º18(mod 35); c) x2º82(mod 121); d) x2º73(mod 80).
3. Решить квадратичные сравнения:
a) x2º23 (mod 43); b) x2º3 (mod 37); c) x2º38 (mod 73);
d) x2º1 (mod 33); e) x2º58 (mod 121); f) x2º13 (mod 81);
g) x2º81 (mod 385); h) x2º1 (mod 120); i) x2º89 (mod 160);
j) x2º39 (mod 43).
Вариант 29
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º2(mod 5); b) x2º63 (mod 77); c) x2º100(mod 121); d) x2º3 (mod 64).
3. Решить квадратичные сравнения
a) x2º17 (mod 43); b) x2º24 (mod 29); c) x2º72 (mod 73);
d) x2º16 (mod 33); e) x2º20 (mod 121); f) x2º79 (mod 81);
g) x2º16 (mod 385); h) x2º1 (mod 66); i) x2º129 (mod 160);
j) x2º31 (mod 40).
Вариант 30
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º23(mod 43); b) x2º31(mod 35); c) x2º15(mod 121); d) x2º45 (mod 64).
3. Решить квадратичные сравнения
a) x2º13 (mod 43); b) x2º20 (mod 61); c) x2º21 (mod 41);
d) x2º58 (mod 77); e) x2º21 (mod 25); f) x2º89 (mod 125);
g) x2º79 (mod 105); h) x2º141 (mod 154); i) x2º49 (mod 80);
j) x2º19 (mod 24).
Вариант 31
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º6 (mod 17); b) x2º21 (mod 55); c) x2º2(mod 9); d) x2º35 (mod 64).
3. Решить квадратичные сравнения
a) x2º11 (mod 43); b) x2º29 (mod 53); c) x2º20 (mod 41);
d) x2º37 (mod 77); e) x2º32 (mod 49); f) x2º91 (mod 125);
g) x2º4 (mod 165); h) x2º113 (mod 154); i) x2º1 (mod 112);
j) x2º11 (mod 26).
Вариант 32
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º39(mod 101); b) x2º16(mod 35); c) x2º37(mod 169); d) x2º13(mod 32).
3. Решить квадратичные сравнения
a) x2º2 (mod 47); b) x2º12 (mod 37); c) x2º65 (mod 73);
d) x2º31 (mod 33); e) x2º45 (mod 121); f) x2º28 (mod 81);
g) x2º4 (mod 385); h) x2º49 (mod 66); i) x2º121 (mod 160);
j) x2º17 (mod 91).
Вариант 33
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º6 (mod 19); b) x2º8 (mod 15); c) x2º18(mod 121); d) x2º5 (mod 12).
3. Решить квадратичные сравнения
a) x2º17 (mod 47); b) x2º6 (mod 53); c) x2º37 (mod 41);
d) x2º23 (mod 77); e) x2º23 (mod 49); f) x2º76 (mod 125);
g) x2º64 (mod 165); h) x2º135 (mod 154); i) x2º81 (mod 112);
j) x2º5 (mod 97).
Вариант 34
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º75(mod 89); b) x2º19(mod 82); c) x2º117(mod 289); d) x2º7(mod 16).
3. Решить квадратичные сравнения
a) x2º34 (mod 47); b) x2º7 (mod 37); c) x2º46 (mod 73);
d) x2º16 (mod 35); e) x2º37 (mod 121); f) x2º31 (mod 81);
g) x2º214 (mod 231); h) x2º31 (mod 66); i) x2º49 (mod 160);
j) x2º20 (mod 101).
Вариант 35
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º7 (mod 68); b) x2º13 (mod 23); c) x2º21 (mod 27); d) x2º5 (mod 169).
3. Решить квадратичные сравнения
a) x2º6 (mod 47); b) x2º10 (mod 37); c) x2º69 (mod 73);
d) x2º1 (mod 55); e) x2º47 (mod 121); f) x2º52 (mod 81);
g) x2º169 (mod 231); h) x2º49 (mod 110); i) x2º1 (mod 160);
j) x2º49 (mod 87).
Вариант 36
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º19(mod 59); b) x2º19(mod 48); c) x2º33(mod 125); d) x2º15 (mod 16).
3. Решить квадратичные сравнения
a) x2º27 (mod 47); b) x2º21 (mod 37); c) x2º70 (mod 73);
d) x2º16 (mod 55); e) x2º75 (mod 121); f) x2º61 (mod 81);
g) x2º64 (mod 231); h) x2º59 (mod 110); i) x2º49 (mod 96);
j) x2º8 (mod 65).
Вариант 37
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º5(mod 83); b) x2º11 (mod 62); c) x2º21 (mod 121); d) x2º15 (mod 44).
3. Решить квадратичные сравнения:
a) x2º3 (mod 47); b) x2º13 (mod 53); c) x2º31 (mod 41);
d) x2º15 (mod 77); e) x2º22 (mod 49); f) x2º109 (mod 125);
g) x2º91 (mod 165); h) x2º15 (mod 154); i) x2º65 (mod 112);
j) x2º17 (mod 75).
Вариант 38
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º20 (mod 67); b) x2º23 (mod 48); c) x2º17 (mod 39); d) x2º19(mod 32).
3. Решить квадратичные сравнения:
a) x2º28 (mod 47); b) x2º30 (mod 37); c) x2º6 (mod 73);
d) x2º31 (mod 55); e) x2º39 (mod 49); f) x2º44 (mod 125);
g) x2º16 (mod 231); h) x2º31 (mod 110); i) x2º113 (mod 176);
j) x2º28 (mod 63).
Вариант 39
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его:
a) x2º15 (mod 61); b) x2º11(mod 35); c) x2º13 (mod 49); d) x2º9 (mod 40).
3. Решить квадратичные сравнения:
a) x2º8 (mod 47); b) x2º28 (mod 53); c) x2º71 (mod 73);
d) x2º36 (mod 55); e) x2º18 (mod 49); f) x2º39 (mod 125);
g) x2º1 (mod 231); h) x2º25 (mod 154); i) x2º169 (mod 176);
j) x2º40 (mod 41).
Вариант 40
1. Вычислить символ Якоби:
а) 
; b) 
; c) 
; d) 
; e) 
; f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
a) x2º14 (mod 83); b) x2º22(mod 289); c) x2º17(mod 39); d) x2º19(mod 32);
3. Решить квадратичные сравнения
a) x2º37 (mod 47); b) x2º38 (mod 53); c) x2º27 (mod 73);
d) x2º1 (mod 77); e) x2º11 (mod 49); f) x2º111 (mod 125);
g) x2º34 (mod 165); h) x2º1 (mod 154); i) x2º25 (mod 176);
j) x2º20 (mod 33).
Решение варианта 40
1. Вычислить символ Якоби:
а) ; b) ; c) ; d) ; e) ; f) .
Решение:
а) 
, т. к. (9,33)=3>1;
b) 
c) 
, т. к. (65,135)=5>1;
d) 
;
e) 
;
f) 
.
2. Выяснить, сколько решений имеет сравнение, не решая его.
b) x2º14 (mod 83);
Решение: 83 – простое число. Вычислим символ Лежандра: 
. Данное сравнение имеет 2 корня.
b) x2º22(mod 289);
Решение: 289=172. Вычислим символ Лежандра: 
Корней нет.
c) x2º17(mod 39);
Решение: 39=3·13. Вычислим символы Лежандра:
, 
. Корней нет.
d) x2º19(mod 32);
Решение: 32=mod 8=3≠1. Корней нет.
3. Решить квадратичные сравнения
a) x2º37 (mod 47);
Решение:
Выясним наличие и количество корней.
47-простое число. Вычислим символ Лежандра: 
. Сравнение имеет 2 корня. Найдем их.
47 mod 4=3. Поэтому сранвение имеет 1 кандидат в решения. Представим 47 как 4k+3. Тогда k=11. Решение будет x≡±37k+1(mod 47).
x≡±3712≡±15(mod 47).
Ответ: x≡±15(mod 47).
c) x2º38 (mod 53);
Решение:
53 – простое число. Вычислим символ Лежандра:
. Сравнение имеет 2 корня. Найдем их.
53 mod 4=1. 53 mod 8=5. Имеется 2 кандидата в решение. Представим53 как 8k+5, тогда k=6. Кандидаты в решение:
Первый: x1≡±38k+1≡±387≡±11(mod 53).
Второй: x2≡22k+1x1≡213x1≡30x1≡±330≡±12(mod 53).
Выясним, какой из кандидатов является корнем, путем подстановки в исходное сравнение. (±11)2≡121≡15(mod 53). (±12)2≡144≡38(mod 53).
Ответ: x≡±12(mod 53).
d) x2º27 (mod 73);
Решение:
73 – простое число. Вычислим символ Лежандра:
. Сравнение имеет 2 корня. Найдем их.
73 mod 4=1. 73 mod 8=1. 73 mod 16=9. Имеется 4 кандидата в решение. Представим 73 как 16k+9, тогда k=4.
Найдем какойнибудь квадратичный невычет N по модулю 73. 
. N=5.
Кандидаты в решение:
Первый: x1≡±27k+1≡±275≡±27(mod 73).
Второй: x2≡N2k+1x1≡59x1≡10x1≡±270≡±51≡±22(mod 73).
Третий: x3 ≡N2k+1x2≡59x2≡10x2≡±220≡±1(mod 73).
Четвертый: x4≡N2k+1x3≡59x3≡10x3≡±10(mod 73).
Выясним, какой из кандидатов является корнем, путем подстановки в исходное сравнение: (±27)2≡72(mod 73); (±22)2≡46(mod 53);
(±1)2≡1(mod 73); (±10)2≡27(mod 73).
Ответ: x≡±10(mod 73).
e) x2º1 (mod 77);
Решение: 77=7·11. Вычислим символы Лежандра: 
, 
.
Сравнение имеет 4 корня. Исходное сравннение равносильно системе:
.
Решим получившиеся системы по Китайской теореме об лостатках.
M=77, M1=11, M2=7,
M1’=M1-1 mod m1=11-1 mod 7=4-1mod 7=2. M2’=M2-1 mod m2=7-1mod 11=8.
x1,2≡±(1·11·2+1·7·8) ≡±(22+56)≡±78≡±1(mod 77),
x3,4≡±(-1·11·2+1·7·8) ≡±(-22+56)≡±34(mod 77).
Ответ: x≡±1(mod 77), x≡±34(mod 77).
f) x2º11 (mod 49);
Решение:
49=72. Вычислим символ Лежандра: 
. Сравнение имеет 2 корня. Для того, чтобы найти корни исходного сравнения, необходмо решить сравнение:
x2º11 (mod 7)
x2º4 (mod 7)
x≡±2 (mod 7)
x=±(2+7t)
Подставим полученное x в исходное сравнение:
(±(2+7t))2≡11(mod 49)
4+28t+49t2≡11(mod 49)
4+28t≡11(mod 49)
28t≡7(mod 49).
Правая, левая части и модуль делятся на 7. Разделим.
4t≡1(mod 7).
4-1=2(mod 7) => t≡2(mod 7) => t=2+7t1 => x=±(2+7(2+7t1))=±(16+49t1) =>
x≡±16(mod 49).
Ответ: x≡±16(mod 49).
g) x2º111 (mod 125);
Решение:
125=53. Вычислим символ Лежандра: 
. Сравнение имеет 2 корня. Для того, чтобы найти корни исходного сравнения, необходмо решить сравнение:
x2º111 (mod 5)
x2º1 (mod 5)
x≡±1 (mod 5)
x=±(1+5t)
Подставим полученное x сравнение по модулю 52=25:
(±(1+5t))2≡111(mod 25)
1+10t+25t2≡111(mod 25)
1+10t≡11(mod 25)
10t≡10(mod 25).
Правая, левая части и модуль делятся на 5. Разделим.
2t≡2(mod 5).
t≡1(mod 5) => t=1+5t1 => x=±(1+5(1+5t1))=±(6+25t1).
Подставим полученное x сравнение по модулю 53=125:
(±(6+25t1))3≡111(mod 125)
36+300t1+625t12≡111(mod 125)
36+50t1≡111(mod 125)
50t1≡75(mod 125).
Правая, левая части и модуль делятся на 25. Разделим.
2t1≡3(mod 5).
2-1 mod 5=3 => t1≡9(mod 5) => t1≡4(mod 5) => t1=4+5t2 => x=±(6+25(4+5t2))=±(106+125t2).
x≡±106≡±(-19)(mod 125).
Ответ: x≡±19(mod 125).
g) x2º34 (mod 165);
Решение: 165=3·5·11. Вычислим символы Лежандра: 
, 
, 
Сравнение имеет 8 корней. Исходное сравнение равносильно системе:
.
Решим получившиеся системы по Китайской теореме об остатках.
M=165, M1=55, M2=33, M3=15.
M1’=M1-1 mod m1=55-1 mod 3=2-1mod 3=2.
M2’=M2-1 mod m2=33-1mod 5=3-1mod 5=2.
M3’=M3-1 mod m3=15-1mod 11=4-1mod 11=3.
x1,2≡±(1·55·2+2·33·2+1·15·3) ≡±(110+132+45)≡±287≡±122≡±43 (mod 165),
x3,4≡±(-1·55·2+2·33·2+1·15·3) ≡±(-110+132+45)≡±67 (mod 165).
x5,6≡±(1·55·2-2·33·2+1·15·3) ≡±(110-132+45)≡±23 (mod 165),
x7,8≡±(1·55·2+2·33·2-1·15·3) ≡±(110+132-45)≡±197≡±32 (mod 165).
Ответ: x≡±43,±67,±23,±32 (mod 165).
h) x2º1 (mod 154);
Решение: 154=2·7·11. Вычислим символы Лежандра: , ,
1 mod 2=1. Сравнение имеет 4 корня. Исходное сравнение равносильно системе:
.
Решим получившиеся системы по Китайской теореме об остатках.
M=154, M1=77, M2=22, M3=14.
M1’=M1-1 mod m1=77-1 mod 2=1-1mod 2=1.
M2’=M2-1 mod m2=22-1mod 7=1-1mod 7=1.
M3’=M3-1 mod m3=14-1mod 11=3-1mod 11=4.
x1,2≡±(1·77·1+1·22·1+1·14·4) ≡±(77+22+56)≡±155≡±1 (mod 154),
x3,4≡±(1·77·1+1·22·1-1·14·4) ≡±(77+22-56)≡±43 (mod 154).
Ответ: x≡±1,±43 (mod 154).
i) x2º25 (mod 176);
Решение: 176=24·11. Вычислим символ Лежандра: 
,
25 mod 8 = 1. Сравнение имеет 8 корней. Исходное сравнение равносильно системе:
.
Решим каждое из сравнений системы:
x2º9 (mod 16).
Чтобы решить это сравнение, воспользуемся решением по модулю 8:
x2º9 (mod 8)
x2º1 (mod 8).
Это сравнение имеет 4 решения: x≡±1,±3(mod 8), которые можно представить как x≡±1(mod 4), или, что то же самое, x=±(1+4t). Подставим полученное x в сравнение по модулю 16:
(±(1+4t))2º9 (mod 16)
1+8t+16t2º9 (mod 16)
8tº8 (mod 16).
Правая, левая части сравнения и его модуль делятся на 8. Разделим:
tº1(mod 2) => t=1+2t1 => x=±(1+4(1+2t1))=±(5+8t1)) => xº±5(mod 8).
Переходя к абсолютно наименьшим вычетам, получаем xº±3(mod 8), что дает 4 корня по модулю 16: xº±3, ±5 (mod 16).
Решим теперь сравнение по модулю 11:
x2º3 (mod 11).
11 mod 4=3, 11=4·2+3, k=2.
Тогда решение будет xº±3k+1º±33º±27º±5(mod 11).
Итак, получили две системы
.
Решим получившиеся системы по Китайской теореме об остатках.
M=176, M1=11, M2=16.
M1’=M1-1 mod m1=11-1 mod 16=3.
M2’=M2-1 mod m2=16-1mod 11=5-1mod 11=9.
Первая система имеет 4 решения:
x1,2≡±(3·11·3+5·16·9) ≡±(99+720)≡±819≡±115≡±(-61) (mod 176),
x3,4≡±(3·11·3-5·16·9) ≡±(99-720)≡±(-621)≡±(-93)≡±83 (mod 176).
Вторая система также имеет 4 решения:
x5,6≡±(5·11·3+5·16·9) ≡±(165+720)≡±885≡±5 (mod 176),
x7,8≡±(5·11·3-5·16·9) ≡±(165-720)≡±(-555)≡±(-60) (mod 165).
Переходя к абсолютно наименьшим вычетам, можем указать 8 решений: x≡±5,±60,±61,±83 (mod 154).
j) x2º20 (mod 33).
Решение:
33=3·11. Вычислим символ Лежандра: 
. Решений нет.
СПИСОК ЛИТЕРАТУРЫ
Основная литература:
1. , Ниссенбаум -числовые методы в криптографии: учеб. пособие. – Тюмень: Изд-во ТюмГУ, 2007. – 160 с.
2. Виноградов теории чисел. 10-е изд., стер. – СПб.: Изд-во «Лань», 2004. – 176 с.
Дополнительная литература:
3. A. Menezes, P. van Oorschort, S. Vanstone, Handbook of Applied Cryptography – CRC Press, Inc., 1997
4. Агибалов теоремы начального курса криптографии: Учебное пособие. – Томск: Изд-во НТЛ, 2005. – 116 с.
5. Черемушкин в алгебре и теории чисел. Курс лекций. — М.: 2002.
Ольга Владимировна Ниссенбаум
ТЕОРЕТИКО-ЧИСЛОВЫЕ МЕТОДЫ В КРИПТОГРАФИИ
СБОРНИК ЗАДАНИЙ (ЧАСТЬ II)
Учебно-методическое пособие
для студентов специальностей
«Компьютерная безопасность» и «Комплексное обеспечение информационной безопасности автоматизированных систем»
Подписано в печать _______ 2012 г. Тираж 100 экз.
Объем 2 п. л. Формат 60х84/16 Заказ № ________
Издательство Тюменского государственного университета
0.
