В последней трети XX века важное значение в разных областях науки, в том числе математики, приобрели вопросы, для решения которых требуются информационно-коммуникативные технологии. Методы решения таких задач исследуются в компьютерной алгебре.
Компьютерная алгебра имеет дело в основном с целыми числами, употребляя соответствующие структуры данных. В ней основной целью является изучение алгоритмов аналитических преобразований с точки зрения их эффективной реализации в программах.
Одними из эффективных методов решения задач целочисленной математики являются методы модулярной арифметики.
В модулярной арифметике работают с остатками по модулю, т.е. вместо чисел рассматриваются их наименьшие неотрицательные вычеты. Таким образом, арифметика целых чисел реализуется через арифметику остатков.
Тема нашей выпускной квалификационной работы: «Задачи модулярной арифметики в компьютерной алгебре». Мы считаем, что тема работы достаточно актуальна, хотя она достаточно подробно освещена в специальной литературе. В настоящее время методы и средства модулярной арифметики используются для решения многих задач символьных вычислений в системах компьютерной алгебры.
Проблемой нашего исследования является исследование вопроса, как и какие методы теории чисел и теории сравнений используются в задачах компьютерной алгебры.
Целью нашего исследования является определение методов теории чисел, которые являются инструментом компьютерной алгебры.
Исходя из цели исследования, мы поставили перед собой следующие задачи:
1. На основе изучения теоретико-числовой литературы по теме исследования провести теоретический анализ проблемы.
2. Выделить задачи модулярной арифметики, при решении которых используются методы теории сравнений.
3. Провести доказательства теорем, лежащих в основе модулярных методов.
4. Описать классы чисел, применяемых в модулярной арифметике с целью решения её задач (числа Кармайкла и др.)
5. Приводить описание алгоритмов на языке Pascal, c контрольными примерами.
6. Составить сборник задач для самостоятельной работы по методам модулярной арифметики.
Объект исследования: математический аппарат модулярной арифметики.
Предметом исследования являются методы теории чисел и теории сравнений в компьютерной алгебре.
Для решения поставленных задач были использованы такие методы исследования:
1. Анализ литературы по проблеме исследования.
2. Специализация известных методов теории чисел к решению задач компьютерной алгебры.
3. Доказательство утверждений, лежащих в основе алгоритмов теории чисел в компьютерной алгебре.
Новизна и теоретическая значимость исследования состоит в том, что проведено систематизированное изучение теории и практики применения методов теории сравнений в компьютерной алгебре.
Практическая значимость исследования определяется наличием в нем анализа задач компьютерной алгебры решаемых теоретико-числовыми методами, доказательством необходимых утверждений и построением на их основе конкретных алгоритмов решения задач.
Апробация результатов исследования выполнялась в виде предварительной защиты на кафедре математики и прикладной информатики ЕИ КФУ.
Структура работы определяется последовательностью решения задач исследования. Работа состоит из введения, семи параграфов, заключения, списка использованной литературы.
Мы считаем, что в результате проведения данной работы нами решены поставленные перед собой задачи.
На основе изучения теоретико-числовой литературы по теме исследования проведен теоретический анализ проблемы.
Описаны теоретико-числовые методы, применяемые в компьютерной алгебре: функция Эйлера, теоремы Эйлера и Ферма, свойства сравнений, алгоритм Евклида и обобщенный алгоритм Евклида, линейное представление НОД, взаимно простые числа, обратные по модулю числа, вычисление степеней по бинарному алгоритму, теория простых чисел, в том числе больших, каноническое разложение и др.
Выделены задачи компьютерной алгебры, при решении которых используются методы теории чисел: вычисление мультипликативно обратных чисел, решение систем линейных сравнений, модулярный НОД многочленов, криптосистема с открытым ключом и др.
Разобраны доказательства теорем, лежащих в основе алгоритмов компьютерной алгебры с заполнением доказательств всех утверждений.
Описаны специальные классы чисел, применяемые в компьютерной алгебре с целью решения ее задач (Кармайкла и др.)
Теоретические выкладки и практические примеры показывают, что модулярные алгоритмы намного упрощают процесс работы с целыми числами.
В процессе обоснования их применения нам пришлось обратиться к различным понятиям и алгоритмам теории многочленов и теории чисел: алгоритм Евклида, простые и составные числа, обратимость чисел по модулю, китайская теорема об остатках и соответствующий алгоритм вычислений по ней, решение систем сравнений, неприводимые и примитивные многочлены, результант многочленов и его свойства.
