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


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

Работа №32614

Тип работы

Магистерская диссертация

Предмет

информатика

Объем работы33
Год сдачи2019
Стоимость5700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
386
Не подходит работа?

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


Введение
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 минут после оплаты.



Подобные работы

Заказать работу

Заявка на оценку стоимости

Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы

Каталог работ (130312)

Новости

06.01.2018 Помощь студентам и аспирантам в выполнении работ от наших партнеров Помощь студентам и аспирантам в выполнении работ от наших партнеров

Помощь в выполнении учебных и научных работ на заказ ОФОРМИТЬ ЗАКАЗ

дальше

»» Все новости

Заказать работу

Заявка на оценку стоимости

Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы

Заказать диплом

Приглашаем авторов студенчесчких работ


©2024 Cервис помощи студентам в выполнении работ
.