Построение и анализ декомпозиционных схем по методу карацубы - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Учебной дисциплины «Финансовая математика» программы профессиональной... 1 37.16kb.
В последние годы бурно развивается криптография с открытым ключом... 1 27.76kb.
Занятие № Тема : Метрика. Ритм и метр 1 260.37kb.
Оценка состояния. Снятие и построение электрических характеристик... 1 30.6kb.
Содержание: Раздел I 1 308.17kb.
Логические схемы 1 32.66kb.
Анализ жизни литературного героя по методу Фрейда Воплощение теории... 1 68.12kb.
Построение и анализ математических моделей деформации упругих стержней... 1 255.58kb.
Анализ тенденций развития федерального бюджета и внебюджетных фондов 1 131.35kb.
Занятие по методу Характерологическая креатология, направление «Воспоминания... 1 61.96kb.
Типовой анализ в ansys построение модели 1 338.82kb.
В последние годы бурно развивается криптография с открытым ключом... 1 27.76kb.
Направления изучения представлений о справедливости 1 202.17kb.

Построение и анализ декомпозиционных схем по методу карацубы - страница №1/1


УДК 004.056:378(06) Проблемы информационной безопасности в системе высшей школы

С.Ю. ЖЕБЕТ

Научный руководитель – А.Б. ФРОЛОВ, д.т.н., профессор



Московский энергетический институт (технический университет)
ПОСТРОЕНИЕ И АНАЛИЗ ДЕКОМПОЗИЦИОННЫХ СХЕМ ПО МЕТОДУ КАРАЦУБЫ
При реализации криптографических систем с открытым ключом возникает потребность в быстрых функциях, выполняющих арифметические операции в конечных алгебраических структурах [1]. При этом особое значение придается операции умножения. В числовом диапазоне, характерном для современных криптографических приложений, как правило, наиболее часто используются различные реализации алгоритмов, базирующихся на методе Карацубы. Особый интерес представляет использование декомпозиционных схем умножения на основе этого метода, которое было описано в [3, 4].

В данной работе рассматривается задача оптимизации операции умножения полиномов посредством построения наиболее быстрой схемы. Как было показано в [6] наибольшей скорости в классе алгоритмов, не использующих схему, можно достичь, используя композицию метода Карацубы и метода сдвигов и сложений. Основная идея заключалась в построении на стадии предварительных вычислений древовидной структуры, задающей последовательность действий и адреса используемых на каждой итерации элементов. Но эта структура занимала значительный объем оперативной памяти, что отрицательно сказывалось на скорости метода. Однако можно обойтись и без построения структуры вычислений, если создать последовательный алгоритм (схему) [4], который оперирует заранее вычисленными ещё до компиляции адресами. Это значительно снижает объём используемой оперативной памяти, но увеличивает размер исходного кода, что, в свою очередь, затрудняет поиск и устранение ошибок. Поэтому процесс генерации схем должен быть автоматизирован. Подробно автоматизация процесса построения декомпозиционной схемы метода Карацубы была рассмотрена в [5].

Для автоматического синтеза схемы используется уже написанная и протестированная процедура умножения полиномов. В ней элементарные операции умножения, сложения и присваивания заменяются действиями по сохранению типа операции и относительных адресов операндов с использованием синтаксиса языка программирования, на котором производится компиляция схемы. При этом реальные адреса операндов проецируются на массив данных, который будет затем использоваться схемой для вычислений.

Для оценки качества схемы используется два параметра: количество элементарных действий, которое подсчитывается на этапе генерации и время умножения с использованием данной схемы которое устанавливается экспериментально по результатам серии вычислений. Вследствие иерархической структуры памяти ЭВМ эти параметры не связаны линейной зависимостью, и потому оба представляют практический интерес.



Схема, построенная для полиномов порядка 2512 по описанному выше методу на основе алгоритма, рассмотренного в [6], так же является оптимальной в классе схем и даёт преимущество в 9,7% над исходной реализацией, которая использовала хранимую в оперативной памяти структуру вычислений. Построение такой схемы позволило вычислить полином порядка 21024 как произведение двух полиномов порядка 2512 за 3.2*10-5 секунды.
Список литературы


  1. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. О методах имплементации арифметических операций в криптографических системах. Известия РАН. Теория и системы управления (2002) N1. С. 86-96.

  2. Карацуба А.А., Офман Ю.П., Умножение многозначных чисел на автоматах. ДАН СССР. 1962. 145 N 2. С. 293-294.

  3. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. О методах реализации умножения многочленов над конечными полями. Вестник МЭИ (2000), N3. С. 33-40.

  4. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Программные и схемные методы умножения многочленов для эллиптической криптографии. Известия РАН. Теория и системы управления (2000) N5. С. 66-75.

  5. Дроздов А.Б. Автоматическое построение декомпозиционных схем умножения многочленов над полем GF(2), основанных на методе Карацубы. Четвертая Всероссийская научная Internet-конференция. Компьютерное и математическое моделирование в естественных и технических науках. Вып. 17, 2002. С. 6-7.

  6. Жебет С.Ю. «Об одном гибридном алгоритме умножения в кольце целых чисел», рук. дтн., проф Фролов А.Б. //Научная сессия МИФИ-2005 XII всероссийская научная конференция « Проблемы информационной безопасности в системе высшей школы» сборник научных трудов МИФИ, 2005. С. 105-106




ISBN 5-7262-0636-3. XIII Всероссийская научная конференция





Здоровые люди — это больные, которые еще не знают об этом. Жюль Ромен
ещё >>