Котова лидия Владимировна

М
М
М
Ма
• 
Д
жно свести
• 
Н
бходимых
• 
О
тему счис
• 
Н
оритма Ев
• 
Р
ширенные
оритм. Ср
нформаци
с. 2.2.7). 
Модули
М1, М2, 
М3, М4
атематический
анализ
Модуль М
Рис
Докажите 
и к трем у
Найдите 
х для выч
Оцените 
сления. 
Найдите Н
вклида, ср
Решите не
е алгорит
равните и
ии»; содер
Курсовые
ВКР
й 
Теория ч
М7
. 2.2.7. Реал
теорему 
умножени
верхнюю
числения 
сложност
НОД (123
равните р
еопределе
тмы Евкл
х трудоем
85
ржит инт
Модуль М
е,
чисел
Т
алг
лизация ва
Примеры
Карацубы
иям k- зна
ю границ
ть перев
Примеры
345 , 2469
решения п
енное ура
лида (обы
мкость. 
5 
тересные 
М 5
Теория 
горитмов
Модуль М6
ариативного
ы Т-задан
ы: умнож
ачных чис
цу для 
ода числ
ы П-задан
90) с пом
по трудое
авнение 5
ычный, би
возможно
Профе
дея
Программ
М
ме
к
о модуля М
ний. 
жение дву
сел. 
числа дв
ла из k 
ний. 
ощью об
емкости. 
551x - 247
инарный),
ости для 
ессиональная
ятельность
мирование
Математически
тоды обработ
информации
Теоретико-
числовые 
алгоритмы в
криптографи
М5 
ух 2k- зна
воичных 
бит в д
ычного и
7y =4522
а также 
реализац
я 
ие 
тки 
и
в 
ии
чных чис
операци
десятичну
и бинарно
, использ
матричны
ии 
сел 
ий, 
ую 
ого 
зуя 
ый 

---

86 
В качестве основной литературы студентам могут быть предложены 
пособия: Деза Е.И., Котова Л.В. «Теоретико-числовые основы защиты 
информации» [84];
Коблиц Н. «Курс теории чисел и криптографии» [74]. 
В качестве дополнительной литературы могут быть использованы 
работы [7], [13], [26], [29], [30], [31], [38], [40], [41], [55], [98], [122], [127], 
[142], [177]. 
М6 ПРОСТЫЕ И ПСЕВДОПРОСТЫЕ ЧИСЛА. Простые числа; 
критерии простоты; тесты на простоту (Ферма, Соловэя-Штрассена, 
Миллера-Рабина); псевдопростые числа; числа Ферма, Эйлера, Кармайкла; 
сильные псевдопростые; генерация больших простых и больших 
псевдопростых чисел. 
Для изучения данного модуля требуется знание основных разделов 
теории чисел; необходимы и навыки программирования (внешние ППК). 
Актуальными внутренними ППК дисциплины являются для данного модуля 
ТППК-2, ТППК-5, ПППК-4, ПППК-5, ПППК-6, ОПППК-2, ОПППК-3, 
ОПППК-4. 
Уточняя их, мы получаем следующие ТППКМ6, ПППКМ6 и ОПППКМ6 
модуля М6:
- знает определение и критерии простоты натуральных чисел (ТППКМ6-
1); знает теоретические основы, лежащих в основе тестов на простоту 
(ТППКМ6-2); 
- знаком с понятием псевдопростого числа (ТППКМ6-3); 
- способен реализовывать тесты на простоту, анализировать их 
достоверность и эффективность (ПППКМ6-1); 
- способен использовать материал о простых числах во время урочной и 
внеурочной деятельности (ОПППКМ6-1); 
- готов использовать полученные знания для помощи учащимся школы в 
подготовке к ЕГЭ и олимпиадам (ОПППКМ6-2). 
Примеры Т-заданий. 

---

87 
• 
Докажите, что если p и 2p-1 - простые числа и n = p·(2p-1),
то n - псевдопростое для половины возможных оснований, а именно для тех, 
которые являются квадратичными вычетами по модулю 2p-1. 
• 
Докажите, что если p - простое число и p-1=2
к
d, где d - нечетное, 
то для любого целого а, взаимно-простого с p, будет выполняться сравнение 
)
(mod
1
p
a
d
≡
или одно из сравнений
)
(mod
1
2
p
a
d
r
−
≡
, где r
∈
[0, ..., k-1] 
(тест Миллера-Рабина). 
Примеры П- заданий. 
• 
Найдите все основания, для которых число 21 - псевдопростое. 
• 
Докажите, что никакое целое n=3p, где p- простое, большее 3, не 
может быть псевдопростым по основаниям 2, 5 или 7. 
В качестве основной литературы студентам могут быть предложены 
разработанные на кафедре теории чисел математического факультета МПГУ 
пособия: Деза Е.И., Котова Л.В. «Теоретико-числовые основы защиты 
информации» [84]; Деза Е.И. «Специальные числа натурального ряда» [51]. 
Дополнительными источниками могут служить работы [7], [8], [10], 
[26], [30], [31], [40], [41], [74], [98], [99], [104], [122], [127], [140], [146], [152], 
[153], [177]. 
Модуль М6 в рамках изучения дисциплины МСИЗ является 
логическим продолжением модулей М4 и М5. Совместно с модулем М7 он 
может полностью содержательно обеспечить дисциплину по выбору 
«Теоретико-числовые алгоритмы в криптографии».
Однако модуль вполне 
самостоятелен и может быть реализован в рамках теоретико-числовой 
дисциплины «Специальные числа натурального ряда». Тема простых чисел и 
их уникальных свойств дает широкие возможности для индивидуальной 
исследовательской деятельности студентов при написании ими курсовых и 
выпускных квалификационных работ, а также организации внеурочной 
деятельности будущего учителя, как информатики, так и математики.

---

88 
Наглядно возможности реализации данного модуля показаны на 
рисунке 2.2.8.