авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 |

Исследование программных методов реализации операций в конечных алгебраических структурах

-- [ Страница 1 ] --

На правах рукописи

Жебет Сергей Юрьевич

Исследование программных методов реализации операций в конечных алгебраических структурах

Специальность: 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Москва 2009

Работа выполнена на кафедре Математического моделирования Московского энергетического института (технического университета).

Научный руководитель: доктор технических наук, профессор

Фролов Александр Борисович.

Официальные оппоненты: доктор технических наук, профессор

Фальк Вадим Николаевич,

кандидат физико-математических наук, доцент

Часовских Анатолий Александрович.

Ведущая организация: Федеральное государственное унитарное предприятие “НИИ “Квант”.

Защита состоится «26» июня 2009 г. В 14:00 в ауд. М-704 на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул., д.17.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба отправлять по адресу: 111250, Москва, Красноказарменная ул., д.14, Ученый совет МЭИ (ТУ).

Автореферат разослан «___» мая 2009 г.

Ученый секретарь

диссертационного совета Д 212.157.01

кандидат технических наук, доцент Фомина М.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Операции в конечных алгебраических структурах кольцах, полях, группах, реализуемые в виде методов алгебраических библиотек, составляют вычислительную базу современных информационных технологий. Эффективность и надежность их реализации предопределяет соответствующие свойства таких информационных систем как системы цифровой обработки сигналов и криптографические протоколы. Вопросам эффективной реализации алгебраических операций посвящено значительное количество, как теоретических работ, так и работ практической направленности. В 1962 г. был опубликован метод умножения Карацубы1, как первый в понижении асимптотической оценки сложности целочисленного умножения. Затем был обоснован метод Шоенхаге-Штрассена2, понизивший эту оценку в еще большей степени. Однако понижение асимптотической сложности не всегда сопровождается понижением практической сложности, под которой мы понимаем число операций или время, затрачиваемые для выполнения операции при заданных размерностях операндов.

Несмотря на сравнительно малую асимптотическую сложность изученных в теории методов, часто при программной реализации в оценке практической сложности получается довольно большая мультипликативная константа. Это существенно ограничивает целесообразность их применения на практике и делает актуальным исследование других, в том числе обладающих большей асимптотической сложностью методов, которые дают лучшие оценки производительности по времени для наиболее часто используемых в современных информационных системах размерностей операндов.

Не случайно на рубеже тысячелетий появились новые интерпретации давно известного метода сдвигов и сложений для реализации умножения3, а также новые методы деления и инвертирования в конечных полях4, имеющие лучшую производительность, чем асимптотически оптимальные методы в диапазоне размерностей современных криптографических протоколов.

Следует также отметить, что асимптотические оценки сложности схемной и программной реализации методов одинаковы и не учитывают той специфики последней, что производительность программы зависит от взаимного расположения операндов, а также от вспомогательных действий, связанных с организацией вычислений по программе (условных переходов, циклов). Чтобы сократить объем таких действий была предложена программная реализация метода Карацубы в виде декомпозиционной схемы, имеющей структуру 5.

Для получения объективных оснований выбора того или иного метода при реализации конкретной информационной системы необходимы разработка и сравнительный анализ новых и известных методов (включая их комбинирование) программной реализации алгебраических операций в тех или иных диапазонах размерностей операндов, чему и посвящена тема настоящей диссертации. Актуальность этой тематики проявляется и в бурном развитии эллиптической криптографии, где появились новые криптографические протоколы, не имеющие аналогов в классе протоколов, основанных на свойствах мультипликативной группы6.

Целью диссертации является повышение эффективности программной реализации арифметических операций в конечных алгебраических структурах.

При этом ставились следующие задачи:

  1. систематизация и программная реализация типичных алгоритмов в конечных алгебраических структурах;
  2. разработка способов сравнения и оценки методов программной реализации алгебраических операций;
  3. разработка методов автоматической генерации последовательных программ умножения;
  4. сравнительный анализ и обоснование выбора методов программной реализации умножения в конечных полях;
  5. сравнительный анализ и обоснование выбора методов программной реализации производных операций (возведения в степень, инвертирования и деления) в конечных полях;
  6. сравнительный анализ методов программной реализации операций сложения и скалярного умножения в группе точек эллиптической кривой на основе рекомендуемых в диссертации методов умножения и деления в конечных полях.

Полученные в диссертации научные результаты:

    1. Обоснована целесообразность комбинирования метода умножения путем сдвигов и сложений (вспомогательного метода) и метода Карацубы с уточнением порога перехода к вспомогательному методу умножения для комбинированных методов, построенных с использованием рекурсивной, циклической и последовательной реализации метода Карацубы.
    2. Разработан метод автоматического синтеза последовательных программ умножения многочленов, обеспечивающий локализацию адресов, и способ автоматической верификации результата такого синтеза.
    3. Разработан метод аналитического сравнения производительности последовательных программ умножения.
    4. Определены наилучшие условия применения последовательных программ умножения по методу А. Карацубы в процессе умножения многочленов высоких степеней над полями различных характеристик и показано существенно большее быстродействие последовательных программ по сравнению с рекурсивными.
    5. Выявлены области рекомендуемого применения методов при умножении многочленов высоких степеней над полями различных характеристик.
    6. На основе сравнительного анализа эффективности алгоритмов скалярного умножения на эллиптических кривых с использованием аффинной и проективной систем представления операндов подтверждено, что существенное преимущество проективной системы сохраняется и в условиях применения наиболее эффективных алгоритмов умножения, инвертирования и деления в конечных полях.

Методы исследования. Поставленные задачи решались с использованием методов дискретной математики, линейной алгебры, теории вычислительной сложности алгоритмов. При разработке программного обеспечения использовались методы объектно-ориентированного программирования и техники оптимизации программного обеспечения.

Научная новизна:

  1. Проведено уточнение порога перехода для комбинированных методов, построенных с использованием рекурсивной, циклической и последовательной реализации метода Карацубы.
  2. Предложен метод автоматического подтверждения правильности синтезируемых различными способами программ умножения.
  3. Предложены аналитический метод оценки сложности и метод автоматического синтеза последовательных программ умножения по методу Карацубы, обеспечивающий локализацию адресов.
  4. Подтверждена эффективность применения проективных координат при вычислениях в группе точек эллиптической кривой в условиях применения наиболее эффективных методов умножения и деления в конечных полях.

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

Практическая значимость полученных результатов. Применение предложенного метода автоматической проверки правильности синтезированных программ умножения позволит повысить качество разрабатываемого программного обеспечения и снизить временные затраты на его разработку и тестирование за счет формальной проверки 100% исходного кода еще до компиляции.

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

Применение в алгоритмах на эллиптических кривых предложенных модификаций алгоритмов умножения многочленов для полей с порождающим многочленом степени больше 256 позволило сократить время выполнения операции умножения точки эллиптической кривой на константу на 5-15% в зависимости от типа кривой и порядка поля, в котором производились вычисления.

Реализация результатов. Работа выполнялась в соответствии с проектом РФФИ 08-01-00632-a и заданием по разработке программного средства «Алгебраический процессор» инновационной образовательной программы. Разработанные программные средства использованы в МЭИ (ТУ) при создании электронного образовательного ресурса «Алгебраический процессор»7

. Результаты внедрены в виде математического и методологического обеспечения лабораторной работы «Сравнительный анализ временных характеристик алгоритмов операций в конечных группах, кольцах и полях» электронного образовательного ресурса «Алгебраический процессор», и используются в лабораторном практикуме по дисциплине «Криптографические методы и средства защиты информации», что подтверждено актами об использовании.

Апробация полученных результатов осуществлена при их обсуждении на одиннадцатой, двенадцатой, четырнадцатой и пятнадцатой международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Москва 2005, 2006, 2008, 2009; девятой, десятой и одиннадцатой Московской Международной телекоммуникационной конференции студентов и молодых ученых «Молодежь и наука», Москва 2006, 2007, 2009.

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 10 печатных изданиях, включая 3 статьи в журнале из Перечня ВАК.

Структура и объем работы. Работа состоит из введения, 4 глав, заключения, списка использованной литературы, содержащей 86 наименований, и приложений. Основной текст занимает 146 машинописных страниц, в том числе 31 рисунок и 33 таблицы. Полный объем диссертации (с приложениями) составляет 149 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, ее научная новизна и практическая значимость, сформулирована цель работы и приведено краткое содержание диссертации по главам.

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

При этом приводятся алгоритмы:

  1. Четыре вариации классического алгоритма умножения методом сдвигов и сложений.
  2. Алгоритм умножения с использованием рекурсивной реализации метода Карацубы.
  3. Три комбинированных метода умножения (с использованием метода Карацубы и классического метода).
  4. Два алгоритма приведения по модулю.
  5. Алгоритм возведения в степень.
  6. Четыре алгоритма инвертирования в поле в стандартном базисе.
  7. Три алгоритма деления многочленов в поле в стандартном базисе.

Для каждого класса программ приводятся сравнительные таблицы времени выполнения и даются рекомендации по использованию одного из методов класса в зависимости от размера входных данных.

Для комбинированных методов умножения дополнительно приводится обоснование асимптотической оценки и производится экспериментальный выбор оптимальной базы рекурсии. Если представить количество разрядов в каждом многочлене множителе в виде , где n2 – база рекурсии по методу Карацубы (количество разрядов в каждом многочлене – операнде, при котором производится переход от метода Карацубы к одному из вспомогательных методов), то глубина рекурсии по методу Карацубы определяется как log2(n1), при этом будет верно утверждение 1.

Утверждение 1. Для комбинированного метода умножения асимптотическая сложность определяется как .

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

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

Идея схемной реализации метода Карацубы была предложена и обоснована в 1999-2006 г.г. в работах А.А. Болотова, С.Б. Гашкова, А.Б. Фролова и А.А. Часовских. Она заключается в том, что предварительное сложение и умножение фрагментов многочленов, как и последующая сборка этих результатов, осуществляется схемой без циклов. Автоматизация построения таких схем была рассмотрена в работах М.И. Фомичева и А.Б. Дроздова в 2001-2002 г.г. В обеих работах на основе аналитического исследования метода строятся таблицы операций и адресов операндов, а затем из таких таблиц извлекается схема. Однако такой метод построения схем не учитывает необходимость оптимизации по объему занимаемой памяти и по размещению в ней результатов промежуточных вычислений. В нашем случае под последовательной программой понимается последовательность элементарных арифметических действий и операций присваивания. Последовательная программа характеризуется размером этой последовательности, объемом используемой памяти и степенью локализации адресаций. По этим параметрам последовательные программы можно оптимизировать. Пример последовательной программы приведен на рисунке 1. В программе делается предположение, что множители располагаются последовательно, начиная с единичного адреса, а после выполнения программы результат записывается на место сомножителей.

Mem[5]=Mem[1]; Mem[5]^=Mem[2]; Mem[6]=Mem[4]; Mem[6]^=Mem[3]; Mem[7]=Mul(Mem[1],Mem[3],2); Mem[3]=Mul(Mem[2],Mem[4],2); Mem[5]=Mul(Mem[5],Mem[6],2); Mem[6]^=Mem[8]; Mem[5]^=Mem[7]; Mem[6]^=Mem[4]; Mem[5]^=Mem[3]; Mem[3]^=Mem[6]; Mem[8]^=Mem[5]; Mem[1]=Mem[7]; Mem[2]=Mem[8];

Рис. 1. Пример последовательной программы для умножения 64-разрядных бинарных многочленов

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

Mem[1]=(A[0])*(B[0])[0] Mem[2]=(A[0])*(B[0])[1]+(A[0]+A[1])*(B[1]+B[0])[0]+(A[0])*(B[0])[0]+(A[1])*(B[1])[0] Mem[3]=(A[1])*(B[1])[0]+(A[0]+A[1])*(B[1]+B[0])[1]+(A[0])*(B[0])[1]+(A[1])*(B[1])[1] Mem[4]=(A[1])*(B[1])[1]

Рис. 2. Пример цепочек действий для последовательной программы на рисунке 1

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

Одним из способов автоматического построения последовательных программ умножения является использование аналитически выведенных формул и таблиц распределения адресов операндов в элементарных операциях.

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

Последовательные программы, получаемые в результате реализации описанных выше подходов, принадлежат одному классу, при этом отличаются только способами адресации элементов и методами распределения памяти для хранения промежуточных результатов. Поэтому для доказательства их эквивалентности можно использовать метод сравнения цепочек действий. Таким образом, автоматизация проверки заключается в том, что при выбранных максимально возможных степенях сомножителей, задающих область применимости программ, автоматически синтезируются две последовательные программы с использованием первого подхода без оптимизации и второго подхода с оптимизацией. Затем из каждой программы извлекаются цепочки действий по формированию базовых слов результата умножения. Формальными преобразованиями производится автоматическое приведение цепочек к единому виду и их сравнение. При положительном заключении о равенстве цепочек формируется заключение о первичной корректности обеих синтезированных программ. Последующий этап компиляции, выполнения программ и сравнения результатов с эталонными значениями позволяет сделать окончательные выводы о корректности синтезированных программ.

В получаемых описанным выше методом последовательных программ умножения, можно выделить набор типовых операций, количество которых подчинено уточненной оценке:

(1)


Pages:   || 2 | 3 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.