Специалитет
2020/2021
Введение в теорию чисел
Статус:
Курс обязательный (Компьютерная безопасность)
Кто читает:
Кафедра компьютерной безопасности
Когда читается:
1-й курс, 2, 3 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Анашкин Александр Владимирович,
Нестеренко Алексей Юрьевич,
Рогачёва Ольга Алексеевна
Специальность:
10.05.01. Компьютерная безопасность
Язык:
русский
Кредиты:
3
Контактные часы:
56
Программа дисциплины
Аннотация
Данная дисциплина относится к вариативной профильной части Профессионального цикла (Major), проводится на 1 курсе обучения и является обязательной. Для освоения учебной дисциплины студенты должны владеть базовыми школьными знаниями и компетенциями. Результаты освоения дисциплины используются в дальнейшем при изучении таких дисциплин, как Дискретная Математика, Комбинаторика, Математическая Логика, Теория Графов, Теория кодирования. Дисциплина Введение в Теорию Чисел обеспечивает приобретение знаний и умений в соответствии с государственным образовательным стандартом, формированию мировоззрения и развитию системного мышления. Она знакомит студентов с основными элементарными понятиями и методами, связанными с изучением свойств натуральных и целых чисел. Знания и практические навыки, полученные по дисциплине, используются студентами при изучении профессиональных дисциплин, а также при выполнении курсовых и домашних работ. Место дисциплины в структуре ООП специалитета. Дисциплина Теория Чисел относится к базовой части математического и естественнонаучного цикла. Она обеспечивает фундаментальные знания, и формирует умения и навыки, необходимые для изучения многих математических дисциплин и дисциплин инженерных направлений. Дисциплина реализуется в он-лайн формате
Цель освоения дисциплины
- Ознакомить студентов с основными элементарными понятиями и методами, связанными с изучением свойств натуральных и целых чисел
Планируемые результаты обучения
- Знать определение и основные свойства множеств натуральных, целых и рациональных чисел
- Знать о существовании общего наибольшего делителя у любых двух натуральных чисел
- Уметь находить общий наибольший делитель нескольких чисел
- Знать определение простого числа и о существовании бесконечного множества простых чисел
- Знать о существовании и единственности разложения натурального числа в произведение простых
- Уметь определять, является ли данное число простым
- Уметь факторизовать данное натуральное число
- Знать определение и основные свойства сравнений
- Знать что классы сравнимых друг с другом целых чисел mod m образуют кольцо с делителями нуля, если m - составное число и поле, если m - простое число
- Знать какие элементы кольца вычетов mod m обратимы в этом кольце
- Уметь решать системы линейных сравнений
- Знать какой функцией определяется число обратимых элементов кольца вычетов mod m, и как она вычисляется
- Знать что группа обратимых элементов и кольце вычетов является циклической
- Знать формулировку и доказательство теорем Эйлера и Ферма
- Уметь вычислять Функцию Эйлера
- Знать определение квадратичного вычета и невычета
- Знать для каких p число -1 является квадратичным вычетом mod p и для каких - квадратичным невычетом mod p
- Знать для каких p число 2 является квадратичным вычетом mod p и для каких - квадратичным невычетом mod p
- Знать определение и свойства символа Лежандра и формулы для его вычисления
- Знать квадратичный закон взаимности и как он применяется
- Уметь решать квадратные уравнения в кольце вычетов mod m
- Уметь вычислять символ Лежандра
- Знать какие числа являются квадратичными вычетами
- Знать определение и свойства символа Якоби
- Уметь вычислять символ Якоби
- Знать определение и свойства первообразных корней индексов
- Уметь находить первообразные корни и индексы и уметь их применять
Содержание учебной дисциплины
- Числовая ось. Натуральные числа. Целые числа. Рациональные числа. Целая и дробная части числа. Метод математической индукции Формула бинома Ньютона. Число точек с целыми координатами в заданном множестве.
- Делимость натуральных чисел. Делимость с остатком. Общий наибольший делитель нескольких целых чисел. Алгоритм Евклида.
- Простые числа. Бесконечность множества простых чисел. Решето Эратосфена. Факторизация натуральных чисел.
- Кольцо вычетов mod m. Группа обратимых элементов в этом кольце. Нахождение обратного элемента к обратимому элементу кольца вычетов mod m
- Кольцо вычетов mod m как прямая сумма колец вычетов p^k, где p - простые числа, делящие число m, а p^k - наибольшая степень каждого такого p, делящая число m. Группа обратимых элементов в этом кольце как прямое произведение. групп обратимых элементов в указанных выше кольцах вычетов p^k. Применение к решению систем линейных сравнений.
- Функция Эйлера и её вычисление. Теоремы Эйлера и Ферма. Кольцо вычетов mod p как поле характеристики p. Полиномы над произвольным полем.
- Квадратичные вычеты и невычеты mod m. Символ Лежандра. Квадратичный закон взаимности.
- Символ Якоби, его свойства и применение. Квадратичные вычеты и невычеты mod 2^k.
- Цикличность группы обратимых элементов в кольце вычетов mod p^k, где p - нечётное простое число. Первообразные корни, индексы и их применение.
Промежуточная аттестация
- Промежуточная аттестация (3 модуль)0.25 * Домашняя работа + 0.25 * Контрольная работа + 0.5 * Экзамен
Список литературы
Рекомендуемая основная литература
- Глухов М.М., Круглов И.А., Пичкур А.Б. - Введение в теоретико-числовые методы криптографии - Издательство "Лань" - 2011 - 400с. - ISBN: 978-5-8114-1116-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/68466
- Теоретико - числовые методы в криптографии : учеб. пособие, Нестеренко, А. Ю., 2012
Рекомендуемая дополнительная литература
- Василенко О.Н. - Теоретико-числовые алгоритмы в криптографии - Московский центр непрерывного математического образования - 2006 - 336с. - ISBN: 5-94057-103-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9303