Вопросам эффективной реализации алгебраических операций посвящено значительное количество, как теоретических работ, так и работ практической направленности. В 1962г был опубликован метод умножения Карацубы, как первый в понижении асимптотической оценки сложности целочисленного умножения.
Алгоритмы для вычислений с использованием больших целых чисел реализуются в виде алгебраических библиотек. Эффективность и надежность их реализации предопределяют соответствующие свойства криптографических протоколов. В большинстве случаев для выполнения клиентской части криптопротоколов пользователи вынуждены использовать персональные компьютеры, обладающие ограниченными вычислительными ресурсами. Это обуславливает высокую актуальность вопроса быстродействия при программной реализации библиотек алгебры чисел большой разрядности.
В случае программной реализации RSA-криптосистем наибольшее внимание необходимо уделить оптимизации операций умножения и возведения в квадрат (именно на этих двух операциях построен алгоритм быстрого возведения в степень). В случае 8192-битного ключа на умножение приходиться 45% суммарной трудоемкости выполнения криптоопераций RSA, а на возведение в квадрат – 24%. [4]
Методы реализации операции умножения можно условно разделить на две группы:
— базовые методы – их трудоемкость носит квадратичный характер
— методы субквадратичной трудоемкости
Асимптотическая теория трудоемкости алгоритмов не рассматривает следующие аспекты:
1. Операция выделения/освобождения памяти — она тоже занимает время, и если память работает медленно и выделение памяти используется часто, то это вносит свой вклад в трудоемкость.
2. Эффективность алгоритма по использованию памяти
Метод умножения, который является стандартным, это умножения «в столбик». Этот метод был найден очень давно. Шумеры и египтяне широко применяли подобный метод уже более четырех тысяч лет назад, и есть мнение, что этот метод существует не менее шести тысячелетий. [2]
В 1956г. (может быть несколько раньше) А.Н. Колмогоров высказал гипотезу о том, что нижняя оценка сложности умножения есть величина порядка n2. Эту гипотезу естественно назвать гипотезой n2 Колмогорова. Основанием для возникновения этой гипотезы послужило, по-видимому, то обстоятельство, что человечество всю свою историю пользуется алгоритмом умножения «в столбик», сложность которого есть O(n2), и если бы был более экономный метод умножения, то он был бы уже найден. [2]
Осенью 1960г. в Московском университете на механико-математическом факультете начал работать семинар по математическим вопросам кибернетики под руководством А.Н. Колмогорова, где им была сформулирована гипотеза n2 и поставлен ряд задач об оценке сложности решений линейных систем уравнений и других сходных вычислений.
Анатолий Алексеевич Карацуба, один из слушателей семинара, обнаружил, что разработанный им алгоритм имеет оценку сложности nlog23 (log23 = 1,5849.. .), что противоречило гипотезе Колмагорова.
После очередного заседания семинара Карацуба сообщил Колмогорову о новом алгоритме умножения. На следующем заседании семинара этот метод умножения был подробно рассмотрен, и на этом семинар прекратил свою работу. После этого началась бурная деятельность в области прикладной математики, которая получила название «быстрые вычисления». [3]
В основе нового метода лежит такой фундаментальный принцип, как «разделяй и властвуй» («divide and conquer»), на котором построены сотни различных быстрых алгоритмов (вспомним хотя бы сортировки или динамическое программирование). Задачу разбивают на части, находят их решение, а затем получают решение всей задачи. Этот приём часто эффективен, особенно если его применять рекурсивно. [1]
Представим числа A и B в виде:
A = a0 + a1x
B = b0 + b1x
Таким образом, мы разобьем исходные множители на старшую и младшую части. Тогда их произведение, с использованием базового метода, выглядит следующим образом:
C = (a0 + a1x)(b0 + b1x) = a0b0 + (a0b1 + a1b0)x + a1b1x2
Введем следующие обозначения:
D1 = a0b0
D2 = (a1 + a0)(b1 + b0)
D3 = a1b1
Тогда: C = (a0 + a1x)(b0 + b1x) = a0b0 + (a0b1 + a1b0)x + a1b1x2 =
D1 + (D2 — D1 — D3)x + D3x2
Числа D1, D2, D3 – промежуточные значения. Их также можно (при необходимости) вычислять методом Карацубы, т.е. метод носит рекурсивный характер.
Наглядно процесс умножения по Карацубе представляется в виде дерева рекурсивных вызовов. На входе в рекурсию произведение двух «длинных» чисел порождает вычисление трех произведений «коротких» чисел, каждое из которых – ещё по три произведения, и так до произведений однозначных чисел. «Последние» произведения вычисляются обычным способом, а затем на выходе из рекурсии «собираются» произведения более высоких уровней до искомого произведения в вершине. [1]
Ссылка
Основная особенность программы заключается в том, что в функциях собственно умножения не осуществляет переход разрядов. Это позволяет упростить модификацию программы для вывода результата в другой системе исчисления. Но здесь есть и существенный недостаток – при увеличении максимальной длины числа (MAX_DIGITS) существует потенциальная возможность переполнения – т.е. полученный результат будет некорректен.
Еще одним существенным недостатком программы является не экономичное использование памяти компьютера – на хранение «цифр» отводится массив типа int.
Ну и время автор программы считает несколько… странно.
В общем, не русская школа программирования – но для понимания вполне приемлемо.
Результаты выложенные автором программы.
Мои результаты несколько отличаются. В частности, метод Карацубы начинает превосходить базовый, когда длина одного из операндов становится больше 32-х. Результаты были получены на процессоре AMD Athlon™ 64 X2 Dual Core Processor 4000+. 1.0 ГБ ОЗУ. Программа скомпилирована MinGW. ОС – MS Windows XP.
Литература
1. Иванов, С. Ю. Метод Карацубы, или соревнование с обычным способом умножения «в столбик» // Вестник Вятского государственного гуманитарного университета. Информатика. Математика. Язык. Научно-методический журнал. – 2005. – № 3. – С. 46–51.
2. Карацуба А.А. Сложность вычислений. // Труды математического института РАН. – 1995. – Т. 211. – С.186-202
3. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // Докл. АН СССР. – 1962. – Т. 145 – № 2. – С. 293-294
4. Лопатин С.Ю. Методы умножения чисел большой разрядности в программных комплексах асимметричной криптографии. Определение границ эффективности методов. // «Искусственный интеллект» — Журнал. – 2004. – №4. – С. 776-784.
Алгоритмы для вычислений с использованием больших целых чисел реализуются в виде алгебраических библиотек. Эффективность и надежность их реализации предопределяют соответствующие свойства криптографических протоколов. В большинстве случаев для выполнения клиентской части криптопротоколов пользователи вынуждены использовать персональные компьютеры, обладающие ограниченными вычислительными ресурсами. Это обуславливает высокую актуальность вопроса быстродействия при программной реализации библиотек алгебры чисел большой разрядности.
В случае программной реализации RSA-криптосистем наибольшее внимание необходимо уделить оптимизации операций умножения и возведения в квадрат (именно на этих двух операциях построен алгоритм быстрого возведения в степень). В случае 8192-битного ключа на умножение приходиться 45% суммарной трудоемкости выполнения криптоопераций RSA, а на возведение в квадрат – 24%. [4]
Методы реализации операции умножения можно условно разделить на две группы:
— базовые методы – их трудоемкость носит квадратичный характер
— методы субквадратичной трудоемкости
Асимптотическая теория трудоемкости алгоритмов не рассматривает следующие аспекты:
1. Операция выделения/освобождения памяти — она тоже занимает время, и если память работает медленно и выделение памяти используется часто, то это вносит свой вклад в трудоемкость.
2. Эффективность алгоритма по использованию памяти
Классическая схема умножения
Метод умножения, который является стандартным, это умножения «в столбик». Этот метод был найден очень давно. Шумеры и египтяне широко применяли подобный метод уже более четырех тысяч лет назад, и есть мнение, что этот метод существует не менее шести тысячелетий. [2]
Гипотеза n2 Колмогорова
В 1956г. (может быть несколько раньше) А.Н. Колмогоров высказал гипотезу о том, что нижняя оценка сложности умножения есть величина порядка n2. Эту гипотезу естественно назвать гипотезой n2 Колмогорова. Основанием для возникновения этой гипотезы послужило, по-видимому, то обстоятельство, что человечество всю свою историю пользуется алгоритмом умножения «в столбик», сложность которого есть O(n2), и если бы был более экономный метод умножения, то он был бы уже найден. [2]
Опровержение гипотезы n2 Колмогорова
Осенью 1960г. в Московском университете на механико-математическом факультете начал работать семинар по математическим вопросам кибернетики под руководством А.Н. Колмогорова, где им была сформулирована гипотеза n2 и поставлен ряд задач об оценке сложности решений линейных систем уравнений и других сходных вычислений.
Анатолий Алексеевич Карацуба, один из слушателей семинара, обнаружил, что разработанный им алгоритм имеет оценку сложности nlog23 (log23 = 1,5849.. .), что противоречило гипотезе Колмагорова.
После очередного заседания семинара Карацуба сообщил Колмогорову о новом алгоритме умножения. На следующем заседании семинара этот метод умножения был подробно рассмотрен, и на этом семинар прекратил свою работу. После этого началась бурная деятельность в области прикладной математики, которая получила название «быстрые вычисления». [3]
Метод Карацубы
В основе нового метода лежит такой фундаментальный принцип, как «разделяй и властвуй» («divide and conquer»), на котором построены сотни различных быстрых алгоритмов (вспомним хотя бы сортировки или динамическое программирование). Задачу разбивают на части, находят их решение, а затем получают решение всей задачи. Этот приём часто эффективен, особенно если его применять рекурсивно. [1]
Представим числа A и B в виде:
A = a0 + a1x
B = b0 + b1x
Таким образом, мы разобьем исходные множители на старшую и младшую части. Тогда их произведение, с использованием базового метода, выглядит следующим образом:
C = (a0 + a1x)(b0 + b1x) = a0b0 + (a0b1 + a1b0)x + a1b1x2
Введем следующие обозначения:
D1 = a0b0
D2 = (a1 + a0)(b1 + b0)
D3 = a1b1
Тогда: C = (a0 + a1x)(b0 + b1x) = a0b0 + (a0b1 + a1b0)x + a1b1x2 =
D1 + (D2 — D1 — D3)x + D3x2
Числа D1, D2, D3 – промежуточные значения. Их также можно (при необходимости) вычислять методом Карацубы, т.е. метод носит рекурсивный характер.
Наглядно процесс умножения по Карацубе представляется в виде дерева рекурсивных вызовов. На входе в рекурсию произведение двух «длинных» чисел порождает вычисление трех произведений «коротких» чисел, каждое из которых – ещё по три произведения, и так до произведений однозначных чисел. «Последние» произведения вычисляются обычным способом, а затем на выходе из рекурсии «собираются» произведения более высоких уровней до искомого произведения в вершине. [1]
Программная реализация метода Карацубы на C
Ссылка
Особенности программы
Основная особенность программы заключается в том, что в функциях собственно умножения не осуществляет переход разрядов. Это позволяет упростить модификацию программы для вывода результата в другой системе исчисления. Но здесь есть и существенный недостаток – при увеличении максимальной длины числа (MAX_DIGITS) существует потенциальная возможность переполнения – т.е. полученный результат будет некорректен.
Еще одним существенным недостатком программы является не экономичное использование памяти компьютера – на хранение «цифр» отводится массив типа int.
Ну и время автор программы считает несколько… странно.
В общем, не русская школа программирования – но для понимания вполне приемлемо.
Границы эффективности
Результаты выложенные автором программы.
Мои результаты несколько отличаются. В частности, метод Карацубы начинает превосходить базовый, когда длина одного из операндов становится больше 32-х. Результаты были получены на процессоре AMD Athlon™ 64 X2 Dual Core Processor 4000+. 1.0 ГБ ОЗУ. Программа скомпилирована MinGW. ОС – MS Windows XP.
Литература
1. Иванов, С. Ю. Метод Карацубы, или соревнование с обычным способом умножения «в столбик» // Вестник Вятского государственного гуманитарного университета. Информатика. Математика. Язык. Научно-методический журнал. – 2005. – № 3. – С. 46–51.
2. Карацуба А.А. Сложность вычислений. // Труды математического института РАН. – 1995. – Т. 211. – С.186-202
3. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // Докл. АН СССР. – 1962. – Т. 145 – № 2. – С. 293-294
4. Лопатин С.Ю. Методы умножения чисел большой разрядности в программных комплексах асимметричной криптографии. Определение границ эффективности методов. // «Искусственный интеллект» — Журнал. – 2004. – №4. – С. 776-784.