Введение
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
На основе проведенных качественных и численных оценок можем утверждать, что при реализации алгоритмов быстрого умножения и деления не разумно останавливать свой выбор только на одном из них, так как в этом случае мы получим просадки в скорости работы либо на малых порядках, либо на сверхбольших. На малых порядках лучше использовать наивные алгоритмы умножения и деления, а на длинах чисел более тысячи алгоритм умножения Тоома - Кука и метод деления Ньютона.
