Тип работы:
Предмет:
Язык работы:


РЕАЛИЗАЦИЯ И АНАЛИЗ АЛГОРИТМОВ БЫСТРОГО УМНОЖЕНИЯ И ДЕЛЕНИЯ ДЛИННЫХ ЧИСЕЛ

Работа №32614
Тип работыМагистерская диссертация
Предметинформатика
Объем работы33
Год сдачи2019
Стоимость5700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 243
Не подходит работа?

Узнай цену на написание

Введение
1. Основные понятия и алгоритмы 4
2. Описание алгоритмов, используемых в диссертации 10
2.1. Алгоритмы деления длинных чисел 10
2.2. Алгоритмы умножения длинных чисел 14
2.3. Алгоритм Евклида 17
2.4. Расширенный алгоритм Евклида 19
3. Реализация и сравнительный анализ алгоритмов 20
3.1 Алгоритмы умножения и деления длинных чисел 20
3.2 Сравнение работы расширенного алгоритма Евклида 25
ЗАКЛЮЧЕНИЕ 27
СПИСОК ЛИТЕРАТУРЫ 29
ПРИЛОЖЕНИЕ


Длинная арифметика - операции, производимые над числами, разрядность которых превышает разрядность вычислительной техники, на которой выполняются вычисления [1].
Большие целые числа используют в арифметике высокой точности, криптографическом кодировании сообщений, иначе в шифровании. Длина чисел может быть значительной, достигать нескольких сотен и более. Компьютером не могут быть выполнены арифметические операции, такие как сложение, вычитание, умножение, деление над такими числами за один шаг. Любая подобная операция должна реализовываться специально написанной процедурой.
В связи с ростом мощности современной вычислительной техники появляется возможность эффективной реализации операций над числами большой длины. Например, такую возможность дают алгоритмы быстрого умножения: Карацубы и Тоома - Кука и алгоритм быстрого деления - метод Ньютона.
Актуальность темы заключается в стремительном развитии
информационной безопасности, основанной на алгоритмах деления и умножения длинных чисел, требующей удлинения ключей шифрования.
Научной новизной диссертации является реализация алгоритма Евклида с использованием алгоритма Карацубы умножения длинных чисел.
Целью магистерской диссертации является исследование
эффективности алгоритмов умножения и деления длинных чисел, реализация и сравнительный анализ алгоритмов умножения, а также исследование эффективности использования алгоритма Карацубы для нахождения наибольшего общего делителя [2].
Исходя из данной цели, необходимо решить следующие задачи:
- исследование основных алгоритмов умножения и деления длинных чисел, алгоритма Евклида нахождения НОД;
- реализация программ для умножения и деления длинных чисел, а также вычисления НОД;
- экспериментальные вычисления с длинными числами;
- сравнение результатов и оценка эффективности алгоритмов. Значимость магистерской диссертации заключается в применении
данных исследования в ряде важнейших информационных областей, использующих операции с длинными числами: в криптографии, в
программной инженерии.
Основными источниками литературы послужили: книга К. Померанса и Р. Крэндала под названием «Простые числа. Криптографические и вычислительные аспекты», учебное пособие Ш.Т. Ишмухаметова и Р.Г. Рубцовой - «Математические основы защиты информации», статья «Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера» Барышниковой М.Ю.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


Задача эффективной реализации длинной арифметики (т.е. арифметики над числами, превышающими длину машинного слова) является одной из важнейших в области компьютерных вычислений. Наиболее важными в длинной арифметике являются операции умножения и деления.
В магистерской диссертации были исследованы и реализованы алгоритмы умножения и деления длинных чисел. Произведен сравнительный анализ эффективности применения данных алгоритмов для разных числовых диапазонов.
На основе экспериментов сделаны следующие выводы: на малых числовых разрядах преимуществом обладает школьный алгоритм умножения. При увеличении порядка числа наивный алгоритм теряет позиции, и время выполнения операции возрастает. На порядках более пятидесяти доминирование переходит к конкурирующим алгоритмам. Чем выше порядок числа, тем меньше время, затраченное на умножение, выполненное алгоритмом Тоома - Кука.
Что касается алгоритмов деления, здесь наблюдается, что на низких порядках преимуществом обладает школьный алгоритм деления, с увеличением разрядности чисел для сокращения времени выполнения операций деления более уместно использовать метод Ньютона. Таким образом, можно судить, что оценка эффективности алгоритмов зависит от длины чисел и схем умножения и деления.
Также был изучен алгоритм Евклида для вычисления НОД, разработан вариант его модификации для оптимального применения в длинной арифметике: использован алгоритм Карацубы вместо школьного алгоритма в качестве операции умножения. На начальных этапах оба алгоритма выполняются с одинаковой скоростью. С разрядности чисел от 3 тысяч на графике наблюдается, что доминирование переходит то к алгоритму Карацубы, то к школьному алгоритму. Это свидетельствует о том, что результаты не сходятся с теоретическими предположениями.
27
На основе проведенных качественных и численных оценок можем утверждать, что при реализации алгоритмов быстрого умножения и деления не разумно останавливать свой выбор только на одном из них, так как в этом случае мы получим просадки в скорости работы либо на малых порядках, либо на сверхбольших. На малых порядках лучше использовать наивные алгоритмы умножения и деления, а на длинах чисел более тысячи алгоритм умножения Тоома - Кука и метод деления Ньютона.


1. Гуев Т.А. Длинная арифметика от Microsoft [Текст] / Т.А. Гуев // RSDN Magazine. - 2013. - №2. - С.22-25.
2. Саляхова Р.В. Реализация и анализ алгоритмов быстрого умножения и деления длинных чисел: курсовая работа [Текст] / К(П)ФУ. - Казань, 2018. - 19с.
3. Орлов В.А. Теория чисел в криптографии [Текст]: учебное пособие /
B. А. Орлов, Н.В. Медведев, Н.А. Шимко, А.Б. Домрачева. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2011. - 223с.
4. Ишмухаметов Ш.Т. Математические основы защиты информации [Текст]: эл. учебное пособие / Ш.Т. Ишмухаметов, Р.Г. Рубцова. - 2012. - 138с.
5. Кормен Т. Алгоритмы: построение и анализ [Текст] / Т.Кормен, Ч.Лейзерсон, Р.Риверст. - М: МЦНМО, 1999. - 960 с.
6. Померанс К. Простые числа. Криптографические и вычислительные аспекты [Текст] / К. Померанс, Р. Крэндалл. - М.: УРСС: Книжный дом «Либроком», 2011. - 664 с.
7. Червяков Н.И., Лобес М. В. Алгоритм целочисленного деления в системе остаточных классов [Текст] / Н.И.Червяков, М.В.Лобес // Инфокоммуникационные технологии. - 2007. Том 5. №4. - С.8-13.
8. Барышникова М.Ю. Сравнительный анализ алгоритмов умножения длинных чисел [Текст] / М.Ю. Барышникова, Д.В. Меркулов, П.Ю. Павелко, А.В. Силантьева // Сборник научных трудов по материалам VII международной научно - практической конференции. - Вологда. - 2015. -
C. 16-21.
9. Куляс М.Е. О программной имплементации метода умножения Карацубы [Текст] / М.Е. Куляс // Радиоэлектроника, электротехника и энергетика. - 2016. - С.206-207.
10. Барышникова М.Ю. Скоростные свойства алгоритмов умножения и
деления целых чисел произвольного размера [Текст] / М.Ю. Барышникова,
29
А.Ф. Деон, А.В. Силантьева // Инженерный журнал: наука и инновации. - Московский государственный технический университет имени Н.Э. Баумана. - 2013. - С.14-25.
11. Куляс М.Е. Разработка комплексного алгоритма умножения [Текст] / М.Е. Куляс // Информационные системы и технологии. - 2015. - С.73-81.
12. Кнут Д. Искусство программирования [Текст]: в 3 т. / Д.Кнут. - М.: Вильямс, 2007. - Т.2: Получисленные алгоритмы. - 3-е изд. - 832с.
13. Карацуба А.А. Умножение многозначных чисел на автоматах [Текст] / А.А.Карацуба, Ю.П.Офман // Доклады Академии Наук СССР. - 1962. - Т. 145 №2. - С.293-294.
14. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел [Текст]: учебное пособие / Ш.Т. Ишмухаметов. - Казань: Казан. ун., 2011. - 190 с.
15. Саляхова Р.В. Реализация и анализ алгоритмов быстрого умножения и деления длинных чисел: отчет по НИР [Текст] / К(П)ФУ. - Казань, 2018. - 20с.


Работу высылаем на протяжении 30 минут после оплаты.




© 2008-2022 Cервис помощи студентам в выполнении работ