Разработка методов и алгоритмов модулярных вычислений для задач большой алгоритмической сложности

• Автор: Лобес, Мария Владимировна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Ставрополь
• Количество страниц: 192 с. : ил.

ОГЛАВЛЕНИЕ

Основные обозначения и сокращения

Введение.
Раздел I. Аналитический обзор методов и алгоритмов решения задач большой алгоритмической сложности.
1.1. Анализ методов и алгоритмов решения теоретикочисловых задач большой алгоритмической сложности.
1.2. Анализ методов и алгоритмов выполнения арифметических операций при решении задач большой алгоритмической сложности.
1.3. Обоснование целесообразности применения целочисленной арифметики для решения задач большой алгоритмической сложности.

1.4. Постановка цели и задач исследования.

Выводы по первому разделу.

Раздел II. Разработка методов и алгоритмов модульного возведения в степень многоразрядных чисел
2.1. Модификации классического алгоритма модульного возведения в степень многоразрядных чисел
2.2. Развитие метода и алгоритма Монтгомери ускоренного модульного умножения многоразрядных чисел
2.3. Разработка базовых методов и алгоритмов расширения системы оснований и масштабирования чисел, представленных в системе остаточных классов.
2.4. Адаптация метода и алгоритма Монтгомери модульного умножения многоразрядных чисел для системы остаточных
классов.
2.5. Разработка метода и алгоритма модульного возведения в степень многоразрядных чисел на базе алгоритма Монтгомери, адаптированного для системы остаточных классов.
2.6. Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных
Выводы по второму разделу.
Раздел III. Разработка методов и алгоритмов деления многоразрядных чисел, представленных в системе остаточных классов.
3.1. Развитие метода и алгоритма деления многоразрядных чисел на основе спуска Ферма
3.2. Разработка метода и алгоритма целочисленного деления многоразрядных чисел на основе итераций Ньютона
3.3. Разработка метода и алгоритма сравнения чисел по величине в системе остаточных классов
3.4. Реализация метода и алгоритма деления Ныотона, адаптированного для
системы остаточных классов
3.5 Компьютерное моделирование и сравнительная оценка разработанного метода и алгоритма деления многоразрядных чисел, представленных в
системе остаточных классов
Выводы по третьему разделу
Заключение
Список литературы


Выполнено компьютерное моделирование и проведена сравнительная оценка разработанного метода и алгоритма модульного возведения в степень многоразрядных чисел. Монтгомери, адаптированный для системы остаточных классов уступает основному алгоритму Монтгомери приблизительно в 1,2 раза. Однако за счет малой разрядности оснований СОК и параллельной структуры вычислений разработанный метод и алгоритм дает огромный выигрыш по времени реализации операции модульного возведения в степень, причем этот выигрыш растет с ростом разрядностей операндов. Применение разработанного алгоритма позволяет время вычисления шифрования с битовыми операндами уменьшить в ,5 раз. В третьем разделе рассмотрен итерационный модулярный метод и алгоритм общего деления на основе модификации метода спуска Ферма. Его недостатком является то, что в случае если разрядности делимого и делителя отличаются значительно, то для вычисления округленного частного может потребоваться много итераций. В то же время если допустимая ошибка задана не выше 0. Разработан метод и алгоритм деления в СОК, основанный на итерациях Ньютона. В сравнении с алгоритмом деления, основанным на спуске Ферма, алгоритм обладает несколькими преимуществами. Вопервых, пет необходимости составления, хранения и аппроксимации таблицы приблизительных делителей. Вовторых, количество итераций для определения величины мь не зависит от величины делимого. Таким образом, если необходимо разделить несколько чисел на одно и тоже число Ь, то величина может быть вычислена один раз. Алгоритм на основе спуска Ферма при делении каждой новой пары чисел а и выполняется полностью. Втретьих, предложенный алгоритм имеет огромные временные преимущества при делении чисел, разрядность которых значительно отличается. Кроме того, количество итераций может быть уменьшено, если в
качестве начального приближения выбрать 2 , где К выбирается из условия Л2Л1 . Для того чтобы реализовать предложенный метод и алгоритм деления в СОК, разработан параллельный алгоритм выполнения операции сравнения чисел. Этот алгоритм является универсальным, так как он позволяет различать равенство двух чисел, знак числа, абсолютное значение чисел и переполнение разрядной сетки ЭВМ. Время сравнения при использовании этого метода равно и 1, где п число оснований СОК. Выполнено компьютерное моделирование в системе МАТЬЛВ и проведена сравнительная оценка методов и алгоритмов деления спуска Ферма и итераций Ньютона. Которая показала, при условии выполнения только одной итерации они имеют приблизительно одну вычислительную сложность. Если выполняется деление чисел одинаковой разрядности или если их разрядность отличается незначительно, то метод Ферма реализуется быстрее. Если разрядности делимого и делителя отличаются значительно, огромное преимущество по времени выполнения деления дает применение метода Ньютона. Например, если делимое 6ти разрядное, а делитель х разрядное число, то время реализации разработанного метода и алгоритма деления в сравнении с методом спуска Ферма сокращается в 8 раз. В заключении подведены итоги и обобщены результаты исследования. В приложении приведены численные примеры и листинги программ, а так же табличный материал необходимый для проводимых оценок. Автор выражает искреннюю благодарность научному руководителю, заслуженному деятелю науки и техники РФ, доктору технических наук, профессору Н. И. Червякову, а так же коллективу кафедр высшей алгебры и геометрии и прикладной математики и информатики за помощь, оказанную при написании диссертации, и критические замечания, высказанные при ее обсуждении. РАЗДЕЛ I. В последние годы интенсивно развивается и имеет важные приложения в различных областях науки и техники прикладная теория чисел. В Приложении 1 рассмотрены схема ключевого обмена ДиффиХеллмана и основные этапы алгоритма В8А. Натуральное число р большее единицы, называется простым, если оно делится нацело только на 1 и на себя. Иначе число называется составным. Тест простоты это алгоритм, который по заданному натуральному числу определяет, простое ли это число или составное. Среди всех простых чисел выделяются простые числа специального вида это числа Мерсенна и Ферма 2,8,.