МатВест

Периодический межвузовский сборник научно-методических работ
Математический вестник педвузов и университетов
Волго-Вятского региона
22.11.2019 03:12 Киров  
Логин:

Пароль:

- запомнить
Забыли пароль?
Ваша корзина
Ваша корзина пуста
Статистика

Авторов: 17
Загружено статей: 3
Всего страниц: 23



Дешевый хостинг

Книги кафедры ФМ
Д. В. Чупраков - Компьютерная алгебра. Алгоритмы теории чисел

Описание
В учебном пособии изложен материал, читаемый при изучении дисциплины "Компьютерная алгебра" студентам бакалавриата математических направлений подготовки. Пособие может быть использовано студентами и магистрантами для изучения дисциплин "Компьютерная алгебра", "Математические методы в информатике", "Криптография и защита информации", "Программирование", "Теория чисел" в качестве учебного пособия или справочника теоретико-числовых алгоритмов.
Ссылка
скачать
Содержание
Предисловие 7
Глава 1. Системы компьютерной алгебры 10
1.1. История систем компьютерной алгебры . . . . . . . . 10
1.2. Система компьютерной алгебры Maxima . . . . . . . . 12
1.3. Первые шаги в Maxima . . . . . . . . . . . . . . . . . . 13
1.3.1. Калькулятор . . . . . . . . . . . . . . . . . . . . 13
1.3.2. Переменные и их значения . . . . . . . . . . . . 14
1.3.3. Функции . . . . . . . . . . . . . . . . . . . . . . 15
1.3.4. Графики функций . . . . . . . . . . . . . . . . . 16
1.3.5. Основные преобразования выражений . . . . . 16
1.4. Элементы программирования в Maxima . . . . . . . . 18
1.4.1. Конструкция следования . . . . . . . . . . . . . 19
1.4.2. Конструкция ветвления . . . . . . . . . . . . . 19
1.4.3. Циклическая конструкция . . . . . . . . . . . . 20
1.4.4. Списки . . . . . . . . . . . . . . . . . . . . . . . 24
Глава 2. Фундаментальные понятия компьютерной алгебры 30
2.1. Сложность алгоритмов . . . . . . . . . . . . . . . . . . 30
2.1.1. Асимптотическая сложность алгоритма . . . . 32
2.1.2. Классы сложности алгоритмов . . . . . . . . . 33
2.1.3. Построение эффективных алгоритмов . . . . . 35
2.2. Задача представления . . . . . . . . . . . . . . . . . . . 36
2.3. Абстрактные типы данных . . . . . . . . . . . . . . . . 37
2.3.1. Алгебры и алгебраические системы . . . . . . . 37
2.3.2. Сигнатуры . . . . . . . . . . . . . . . . . . . . . 39
2.3.3. Термы . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.4. Абстрактные типы данных . . . . . . . . . . . . 41
2.4. Представление классических математических объектов 42
2.4.1. О структуре памяти . . . . . . . . . . . . . . . . 42
2.4.2. Представление целых чисел . . . . . . . . . . . 43
2.4.3. Алгоритмы перевода числа из одной системы
счисления в другую . . . . . . . . . . . . . . . . 44
2.4.4. Представление рациональных чисел . . . . . . 46
2.4.5. Представление многочленов . . . . . . . . . . . 47
2.4.6. Представление математических выражений . . 47
Глава 3. Арифметика в числовых кольцах 51
3.1. Операция сложения . . . . . . . . . . . . . . . . . . . . 51
3.2. Операция умножения . . . . . . . . . . . . . . . . . . . 53
3.2.1. Египетский алгоритм умножения . . . . . . . . 53
3.2.2. Алгоритм умножения столбиком . . . . . . . . 54
3.2.3. Алгоритм умножения Карацубы . . . . . . . . 56
3.3. Возведение в степень . . . . . . . . . . . . . . . . . . . 60
3.3.1. Бинарное возведение в степень . . . . . . . . . 60
3.3.2. Вычислительная сложность бинарного алгоритма возведения в степень 62
3.3.3. Метод множителей показателя . . . . . . . . . 65
Глава 4. Делимость 67
4.1. Деление с остатком . . . . . . . . . . . . . . . . . . . . 67
4.1.1. Евклидово кольцо . . . . . . . . . . . . . . . . . 67
4.1.2. Алгоритм деления с остатком вычитанием . . 68
4.1.3. Бинарный алгоритм деления с остатком . . . . 68
4.1.4. Сложность бинарного алгоритма деления с остатком 72
4.2. Наибольший общий делитель. Алгоритм Евклида . . 73
4.2.1. Наибольший общий делитель . . . . . . . . . . 73
4.2.2. Свойства НОД целых чисел . . . . . . . . . . . 74
4.2.3. Алгоритм Евклида . . . . . . . . . . . . . . . . 74
4.2.4. Сложность алгоритма Евклида в полукольце N0 76
4.2.5. Расширенный алгоритм Евклида . . . . . . . . 79
4.2.6. Бинарный алгоритм Стайна . . . . . . . . . . . 81
Глава 5. Алгоритмы теории чисел в компьютерной алгебре 86
5.1. Сравнения . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.1.1. Представления классов Zm . . . . . . . . . . . . 87
5.1.2. Решение сравнений первой степени . . . . . . . 88
5.1.3. Алгоритм решения сравнения первой степени . 89
5.2. Китайская теорема об остатках . . . . . . . . . . . . . 91
Глава 6. Простые числа 96
6.1. Свойства простых чисел . . . . . . . . . . . . . . . . . 98
6.1.1. Основная теорема арифметики . . . . . . . . . 98
6.1.2. Малая теорема Ферма . . . . . . . . . . . . . . 99
6.1.3. Критерий Вильсона . . . . . . . . . . . . . . . . 100
6.1.4. Тест Поклингтона . . . . . . . . . . . . . . . . . 101
6.1.5. Полиномиальный тест Агравала Каяла Саксены . 102
6.2. Распределение простых чисел . . . . . . . . . . . . . . 105
6.3. Алгоритмы получения всех простых чисел на
промежутке . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.1. Перебор делителей . . . . . . . . . . . . . . . . 111
6.3.2. Решето Эратосфена . . . . . . . . . . . . . . . . 112
6.3.3. Решето Аткина . . . . . . . . . . . . . . . . . . 113
6.4. Простые числа специального вида . . . . . . . . . . . 118
6.5. Вероятностный алгоритм проверки числа на простоту 121
6.5.1. Сильно псевдопростые числа . . . . . . . . . . 121
6.5.2. Тест Миллера Рабина . . . . . . . . . . . . . 122
Глава 7. Применения методов компьютерной алгебры 129
7.1. Разложение числа на множители . . . . . . . . . . . . 129
7.1.1. Метод Ферма . . . . . . . . . . . . . . . . . . . . 129
7.1.2. Метод Диксона . . . . . . . . . . . . . . . . . . 130
7.2. Асимметричное шифрование . . . . . . . . . . . . . . . 135
7.2.1. Криптографические системы с открытым ключом 135
7.2.2. Криптосистема RSA . . . . . . . . . . . . . . . . 136
7.2.3. Атаки на RSA . . . . . . . . . . . . . . . . . . . 138
Библиографический список 142

Сайт управляется SiNG cms © 2010-2015