Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Исследование программных методов реализации операций в конечных алгебраических структурах
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В четвертой главе проводится сравнительный анализ эффективности алгоритмов умножения точки эллиптической кривой на константу с использованием аффинной и проективной систем представления операндов и усовершенствованных алгоритмов умножения, инвертирования и деления в конечных полях. Результаты экспериментов подтверждают рекомендации по применению проективных координат: использование ускоренного… Читать ещё >

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

Содержание

  • Глава 1. Систематизация типичных алгоритмов в полях и кольцах
    • 1. 1. Наиболее распространенные алгоритмы умножения в кольце многочленов
      • 1. 1. 1. Различные реализации метода сдвигов и сложений
      • 1. 1. 2. Умножение с использованием метода Карацубы
      • 1. 1. 3. Сравнение методов умножения
    • 1. 1. Наиболее распространенные алгоритмы приведения в кольце многочленов
    • 1. 2. Алгоритм возведения в степень
    • 1. 3. Алгоритмы инвертирования в стандартных базисах
    • 1. 4. Алгоритмы деления многочленов в поле
    • 1. 2. Выводы
  • Глава 2. Последовательные программы умножения и их синтез
    • 2. 1. Способы автоматического построения последовательных программ
      • 2. 1. 1. Аналитический способ построения последовательных программ
      • 2. 1. 2. Рекурсивный алгоритм синтеза последовательной программы умножения многочленов
      • 2. 1. 3. Автоматическое сравнение синтезированных последовательных программ умножения
    • 2. 2. Сравнение времени выполнения операции умножения для последовательных программ
      • 2. 2. 1. Оценка для метода Карацубы с методом сдвигов и сложений, использующим таблицу умножения
      • 2. 2. 2. Оценка для комбинации метода Карацубы и метода сдвигов и сложений с условными переходами
      • 2. 2. 3. Оценка для метода Карацубы с использованием таблицы умножения 8-разрядных слов
    • 2. 3. Обобщение результатов на поля большой характеристики
    • 2. 4. Наилучшие алгоритмы, и границы их применимости
    • 2. 5. Выводы
  • Глава 3. Локализация адресов и циклическая реализация метода Карацубы
    • 3. 1. Локализация операндов и оптимизация метода по памяти
    • 3. 2. Оценка количества операций по перемещению и влияние модификации на выбор оптимального параметра
    • 3. 3. Циклическая реализация метода Карацубы
      • 3. 3. 1. Общий анализ этапов, построение алгоритма
    • 3. 4. Сравнение времени умножения при использовании различных комбинированных методов
    • 3. 5. Выводы
  • Глава 4. Сравнительный анализ эффективности алгоритмов умножения точки эллиптической кривой на константу
    • 4. 1. Сложение и удвоение точек для суперсингулярной кривой над полем характеристики
      • 4. 1. 1. Стандартный алгоритм сложения и удвоения
      • 4. 1. 2. Алгоритм, использующий переход к проективным координатам
      • 4. 1. 3. Сравнение времени выполнения алгоритмов
    • 4. 2. Сложение и удвоение точек для несуперсингулярной кривой над полем характеристики
      • 4. 2. 1. Стандартный алгоритм сложения и удвоения
      • 4. 2. 2. Алгоритм, использующий переход к проективным координатам
      • 4. 2. 3. Сравнение времени выполнения алгоритмов
    • 4. 3. Метод аддитивных цепочек для скалярного умножения точек эллиптической кривой
    • 4. 4. Сравнение времени выполнения скалярного умножения точек эллиптических кривых различными алгоритмами
    • 4. 5. Выводы

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

Можно считать, что изучение асимптотически быстрых алгоритмов умножения началось еще до появления понятия криптографии с открытым ключом, в, 1962 году, когда А. Карацуба предложил использовать метод умножения, имеющии асимптотическую сложность [33]. Несколько позднее, Тоомом и Куком в 1963;1966 г. в работах [41] и [49] было показано, что данную асимптотическую оценку можно улучшить, до oip.2^2log2″ log2 nj. А в 1966;1971 году в работах [76, 78−80] был предложенметод умножения, использующий быстрое дискретное преобразование Фурье и показано, что он имеет асимптотическую сложность 0(nog2 nog2 log2(n)).

Изучение операции инвертирования в поле началось намного позднее и нашло свое отражение в работах [11, 12, 20, 35, 65, 84]. В работах [11, 12, 65] рассматриваются алгоритмы инвертирования, использующее следствие из малой теоремы Ферма, в [35, 72, 79, 84] используются различные вариации расширенного алгоритма Евклида, имеющего асимптотическую сложность о (п3), а в [44] был предложен более эффективный вариант расширенного алгоритма, однако известен теоретически более быстрый вариант Шенхаге-Моенка алгоритма Евклида, его асимптотическая сложность оценивается как O (M (rc)log0z)), где М (и) — сложность умножения многочленов степени п [72, 79]. В работе [20] в 2006 году алгоритмы инвертирования в бинарных полях были обобщены на поля характеристики большей или равной трех.

Актуальность темы

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

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

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

П].

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

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

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

1) систематизация и программная реализация типичных алгоритмов в конечных алгебраических структурах;

2) разработка способов сравнения и оценки методов программной реализации алгебраических операций;

3) разработка методов автоматической генерации последовательных программ умножения;

4) сравнительный анализ и обоснование выбора методов программной реализации умножения в конечных полях;

5) сравнительный анализ и обоснование выбора методов программной реализации производных операций (возведения в степень, инвертирования и деления) в конечных полях;

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

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

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

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

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

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

5. Выявлены области рекомендуемого применения методов при умножении многочленов высоких степеней над полями различных характеристик.

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

Научная новизна полученных результатов:

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

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

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

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

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

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

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

Применение в алгоритмах на эллиптических кривых предложенных модификаций алгоритмов умножения в расширениях полей степени 256 и выше позволило сократить время выполнения операции умножения точки эллиптической кривой на константу на 5−15% в зависимости от типа кривой. Реализация результатов. Работа выполнялась в соответствии с проектом РФФИ 08−01−632-а и заданием по разработке программного средства «Алгебраический процессор» инновационной образовательной программы. Результаты внедрены в виде математического и методологического обеспечения лабораторной работы «Сравнительный анализ временных характеристик алгоритмов операций в конечных группах, кольцах и полях» электронного образовательного ресурса «Алгебраический процессор» [43].

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

Полученные результаты опубликованы в десяти печатных изданиях [23−31, 43], включая 3 статьи из перечня ВАК [23−25].

Основное содержание работы. Диссертация состоит из настоящего введения, четырех глав, заключения и библиографического списка.

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

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

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

Идея схемной реализации метода Карацубы была предложена и обоснована в 1999;2006 г. г. в работах [4, 5] и заключается в том, что предварительное сложение и умножение фрагментов многочленов, как и последующая сборка этих результатов, осуществляется схемой без циклов. Автоматизация построения таких схем была рассмотрена в работах [22, 42]. В обеих работах на основе аналитического исследования метода строились таблицы операций и адресов операндов, а затем из таких таблиц извлекалась схема. Однако такой метод построения схем не учитывает необходимость оптимизации по объему занимаемой памяти и по размещению в ней результатов промежуточных вычислений, что делает его применение довольно ограниченным для получения последовательных программ умножения. В нашем случае под последовательной программой понимается последовательность элементарных арифметических действий и операций присваивания. Последовательная программа характеризуется размером этой последовательности, объемом используемой памяти и степенью локализации адресаций. По этим параметрам последовательные программы можно оптимизировать.

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

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

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

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

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

Здесь ль П2 — параметры алгоритма, причем п = пхп2- количество разрядов в многочленах — операндах, а п2 — параметр перехода — размерность базы рекурсии, осуществляемой при синтезе программы. Таким образом, задача получения оценки сводится к задаче определения постоянных Сь. для ограниченного набора элементарных действий. Что делается путем построения семи последовательных программ и решением системы линейных уравнений для каждого выбранного действия. В итоге были получены следующие оценки:

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

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

Р = С^З1022″ 1 п2 + С231оё2Щ п2 + Същп2 + С4 З1022″ 1 + С5пх + С6п2 + С7 С1) 310^'!1+4.

1022 И,.

2).

16 зб#з1о&" «+1.

16 2 8.

3).

3) для последовательных программ, построенных по методу Карацубы, использующему таблицу умножения для многочленов степени не выше 7.

31оы.11*и + 4 ^.

243 8.

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

1) для последовательных программ, построенных по комбинированному методу, использующему метод сдвигов и сложений с таблицей оптимальный параметр перехода равен 32;

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

Для обобщения данной оценки сложности операции умножения в СР (р"), где р>2, отмечается, что при реализации умножения над полями нечетной характеристики, возникает необходимость табулирования операций сложения и вычитания, для реализации которых в ОР (2п) использовались операции «исключающего или» (ХСЖ). То есть каждая операция «исключающего или» заменяется операциями адресации по таблицам сложения и вычитания в вР (р). Дополнительно с увеличением характеристики поля, последовательная программа неявно усложняется вследствие увеличения количества бинарных разрядов, которые отводятся на один элемент поля ОР (р). Повторением вычислений констант, описанных выше, было получено, что функция сложности по количеству операций адресации в последовательной программе умножения многочленов в СР (3П) имеет вид: р = 15 * З12″ 1 п22 +107,5 * З10®-2″ 1 п2 -106 * щп2 +12 Так как в указанной последовательной программе вместо всех арифметических операций использовались адресации по таблице, то для дальнейшего увеличения характеристики поля не требуется изменение алгоритма, достаточно лишь заменить таблицы выполнения элементарных арифметических действий. Иначе, если обозначить 8(и, р) — последовательную программу умножения многочленов степени п над полем СР (рп), то при условии использования таблиц операций с 8-разрядными словами и р<251, получим 8(п, 2)=8((п/8)4жГ2(рЛ)-1,р).

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

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

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

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

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

В заключении даны выводы по результатам исследования.

4.5 Выводы.

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

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

Заключение

.

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

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

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

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

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

6. Экспериментально подтверждены рекомендации по применению проективных координат в операциях умножения точки эллиптической кривой на константу.

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

Показать весь текст

Список литературы

  1. П.И., Фролов А. Б. О делении бинарных полиномов на полином с малым числом членов. // Вестник МЭИ, 2004 г., № 6, стр. 5−16.
  2. Ахо А., Хопкрофт Дж., Ульман Дж. «Построение и анализ вычислительных алгоритмов. // М.: Мир, 1979.
  3. Ю.В. Быстрые вычисления //ДАН СССР. 1975. Т. 223. № 5. С. 1041−1043.
  4. A.A., Гашков С. Б., Фролов А. Б., Часовских A.A. Алгоритмические основы эллиптической криптографии. // Препринт. М.: МЭИ, 2000 г., 100 стр.
  5. A.A., Гашков С. Б., Фролов А. Б., Часовских A.A. Программные и схемные методы умножения многочленов для эллиптической криптографии. // Известия Академии Наук. Теория и системы управления. 2000 г. № 5, стр. 66−75.
  6. A.A., Гашков С. Б., Фролов А. Б., Часовских A.A. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. М.: КомКнига, 2006, 324 стр.
  7. A.A., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М.: КомКнига, 2006, 274 стр.
  8. A.A., Гашков С. Б. О быстром умножении в нормальных базисах конечных полей. // Дискретная математика, т.13 № 3, 2001 г., стр. 3−31.
  9. A.A., Гашков С. Б., Фролов А. Б. Криптографические протоколы на эллиптических кривых: учебное пособие по курсу «Криптографические методы защиты информации» М.: Издательский дом МЭИ, 2007. — 80 стр.
  10. A.A., Гашков С. Б., Фролов А. Б. Криптографические протоколы, основанные на спаривании: учебное пособие по курсу «Криптографические методы защиты информации» М.: Издательский дом МЭИ, 2007. — 64 стр.
  11. A.A., Гашков С. Б., Фролов А. Б., Часовских A.A. О методах имплементации арифметических операций в криптографических системах // Известия РАН. Теория и системы управления. 2002 № 1 с 86−96.
  12. A.A., Гашков С. Б., Фролов А. Б., Часовских A.A. О методах имплементации арифметических операций в полях Галуа // Вестник МЭИ. 2000 № 4 с. 88−96.
  13. A.A., Гашков С. Б., Фролов А. Б., Часовских A.A. О методах реализации умножения многочленов над конечными полями. Вестник МЭИ, № 3, 2000 г., стр. 33−40.
  14. A.A., Гашков С. Б., Хохлов P.A. Быстрые вычисления в конечных полях с использованием оптимальных, нормальных базисов. // Интеллектуальные системы, № 7 2002−2003 гг., стр 245−292.
  15. С.Б. Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли. // Дискретная математика, т. 12 № 3, 2000 г., стр. 124−153.
  16. С.Б., Бурцев A.A. О схемах для арифметики в композитных полях большой характеристики. // Чебышевский сборник, т.7, вып.1, 2006 г., стр. 186 204.
  17. С.Б., Гашков И. Б., Бурцев A.A. О сложности булевых схем для арифметики в некоторых башнях конечных полей. // Вестник МГУ, Математика. Механика. № 5, 2006 г., стр. 10−16.
  18. С.Б., Сергеев И. С. О приложении метода аддитивных цепочек к инвертированию в конечных полях. // Дискретная математика, № 4 2006 г., стр. 56−72.
  19. С.Б., Фролов А. Б. Об умножении многочленов над конечным полем посредством быстрого преобразования Фурье. // Вестник МЭИ, № 6, 2004 г., стр. 27−38.
  20. С.Б., Фролов А. Б., Шилкин С. О. О некоторых алгоритмах инвертирования и деления в конечных кольцах и полях // Вестник МЭИ. 2006, № 6, стр. 52−61.
  21. С.Б., Хохлов P.A. О глубине логических схем для операций в конечных полях GF(2n). // Чебышевский сборник, т.4 № 4(8), 2003 г., стр. 59−71.
  22. С.Ю. Сравнительный анализ алгоритмов умножения бинарных многочленов в полиномиальном базисе // Вестник МЭИ, № 6, 2006, Москва, Издательство МЭИ, с. 52−61.
  23. С.Ю. Сравнительный анализ алгоритмов умножения многочленов над полями большой характеристики // Вестник МЭИ, № 6, 2007, Москва, Издательство МЭИ, с. 84−90.
  24. С. Ю. Фролов А.Б. Автоматический синтез программ умножения многочленов над конечным полем // Вестник МЭИ, № 6, 2008, Москва, Издательство МЭИ, с. 59−71.
  25. А., Сложность вычислений. // Труды Математического института им. Стеклова, т. 211, с. 169−183 (1995).
  26. A.A., Офман Ю. П. Умножение многозначных чисел на автоматах// ДАН СССР. Т. 145 № 2. 1962 с.293−294.
  27. К. Техника оптимизации программ. Эффективное использование памяти СПб.: БХВ-Петербург, 2003. 464 с.
  28. Д. Искусство программирования т.2 // СПб.: Вильяме, 2000
  29. Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988 — 820 с.
  30. В.И. Элементы криптографии. М.: Высшая школа, 1999.
  31. А. Криптография с открытым ключом. М.: Мир, 1996.
  32. И.С. Инвертирование в конечных полях с логарифмической глубиной. //Математические вопросы кибернетики вып. 15 (2007), стр. 35−64.
  33. И.С. Об инвертировании в конечных полях характеристики два с логарифмической глубиной. // Вестник МГУ, Математика. Механика. № 1, 2007, стр.28−33.
  34. A.JI. О сложности схемы из функциональных элементов, реализующей умножение целых чисел //ДАН СССР Т. 150 № 3 1963 с. 496−498.
  35. A1 US2002/55 962. Automatically solving equations in finite fields / Schroeppel R. // US Patent application № 09/834, p.363
  36. Ahmadi O., Menezes A. Irreducible polynomials of maximum weight. January 2005 Preprint. (http://www.cacr.math.uwaterloo.ca/~ajmeneze/publications/weightn.pdf)
  37. Ash D.W., Blake I.F., Vanstone S.A. Low complexity normal bases //Discrete Applied Mathematics 1989. vol 25 p. 191−210.
  38. Brent R., Gaudry P., Thome E., Zimmermann P. Faster multiplication in GF (2)x]. // Springer-Verlag, 2008, p. 153−166.
  39. Brunner H., Curigerand A., Hofsteter M. On computing multiplicative inverses in GF (2n) // IEEE Transactionson Computers, Vol. 42, no.8 1993 p. 1010−1015
  40. Cook S.A. On the Minimum Computation Time of Functions // Thesis, Harward University 1966 p. 51−77
  41. Dahab R. Hankerson D., Hu F., Lang M., Lopez J., Menezes A. Software Multiplication using Normal Basis. 2005 (Technical report CACR 2004−12, University of Waterloo, 2004. http://cacr.math.uwaterloo.ca/ajmeneze).
  42. Drolet G. A new representation of elements of finite fields GF (2m) yielding small complexity arithmetic circuits. // IEEE Transaction on Computers. 1998. 47. p.938−946
  43. Fan H. and Hasan M.A., Alternative to the Karatsuba Algorithm for Software Implementation of GF (2n) Multiplication, Technical Report CACR 2006−13, Univ. of Waterloo, Waterloo, Canada, May 2006.
  44. Fan H., Hasan M.A. A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields Technical Report CACR 2006−02, University of Waterloo, Jan, 2006.
  45. H. Fan and Y. Dai Fast bit parallel GF (2n) Multiplier for All Trinomials. //IEEE Transactions on Computers, vol. 54, no. 4, pp. 485−490, 2005.
  46. Gantor D. On arithmetical algorithms over finite fields // Journal of Combinatorial Theory Series A, v.50 n.2, 1989, p.285−300
  47. Gao S., Gathen J. von zur, Panario D. Gauss Periods: orders and cryptographical applications //Mathematics of Computation. 1998. vol. 67 p. 343−352.
  48. Gao S., Lenstra H.W. Optimal normal bases // Design, Codes and Cryptography. 1992. vol. 2. p. 315−323.
  49. Gao S., Vanstone S.A. On orders of optimal normal bases generators // Mathematics of Computation 1995. vol. 64 p. 1227−1233.
  50. Gathen J. von zur, Gerhard J. Modern computer algebra. // Cambridge University Press 1999.
  51. Gaudry, P., Kruppa, A., and Zimmermann, P. A GMP-based implementation of Schonhage-Strassen's large integer multiplication algorithm // Proceedings of ISSAC'07 (Waterloo, Ontario, Canada, 2007), pp. 167−174.
  52. Geiselmann W., Lukhaub H. Redundant representation of finite fields. Public Key Cryptography // Lecture Notes in Computer Science 1992 № 2001 p.339−352.
  53. Granger R., Page D., Stam M. Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three // IEEE Transaction on Computers v.54, No 7 (2005), 852−860.
  54. Hankerson D., Lopez. J.H. Menezes A. Software implementation of elliptic curve cryptography over binary fields // CHES 2000, Lecture Notes in Computer Science. 2000. № 1965. p. 1−23.
  55. Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography // Springer, 2004.
  56. Itoh K., Takenaka M., Torii N. et. al. Fast implementation of public-key cryptography on DSP TMS320C6201, CHES'99, LNC 1717. 1999 p. 61−72
  57. Jungnickel D. Finite fields: Structure and arithmetic. Wissenschaftsverlag, 1995.
  58. Karacuba A., Berechnungen und die Kompliziertheit von Beziehungen. // EIK, N11, s. 10−12(1975).
  59. Lim G.H., Lee P.G. More flexible exponentiation with precomputation. // Crypto-94. Springer p. 95−107
  60. Lopez J. Dahab R. Improved algorithm for elliptic curve over GF (2n) SAC'98 // Lecture Notes in Computer Science 1999. № 1556 p.201−212.
  61. Lopez J., Dahab R. High Speed Multiplication in GF (2m) // Proceedings of Indocrypt 2000, LNCS 1977. Springer, 2000. P.203−212
  62. Menezes A, van P. Oorschot, Vanstone S. Handbook of Applied Cryptography. CRC Press. 1997.
  63. Moenk R. Fast algorithm of GCD’s // Proceedings of the 5th annual ACM Symposium on Theory of Computing. 1973. p. 142−151
  64. Montgomery P. Five, Six, and Seven-Term Karatsuba-Like Formulae. // IEEE Transactions on Computers, vol. 54, no.3, 2005 p. 362−369,.
  65. Montgomery P. Speeding the Polard and elliptic curve methods of factorization // Mathematics 5f-Computation. 1987. Vol. 48 p. 243−264.
  66. Mullin. R.C., Onyszchuk I.M., Vanstone S.A., Wilson R.M. Optimal normal bases in GF (pn).
  67. Pollard J.M. The fast Fourier transform in a finite field. Mathematics of Computation № 25, 1971, 365−374
  68. R. Katti and J. Brennan. Low complexity multiplication in a finite field using ring representation // IEEE Transactions on Computers, 52(4):418−427, 2003
  69. Schonhage A. Schnelle berehnung von kettenbruchentwicklungen // Acta Informatica 1. 1971 p.139−144.
  70. Schonhage A. Schnelle Multiplication von Polynomen uber Koerpern der Charakteristik 2 // Acta Informatica. 1977 vol.7 p. 395−398
  71. Schonhage A., Strassen V. Schnelle Multiplikation grosser Zahlen. // Computing № 7 1971 p.281−292
  72. Schroeppel R., Orman H., Malley S’O., Spatschek O. Fast Key exchange with elliptic curve systems // CRYPTO 95, Lecture Notes in Computer Science. 1995 № 963. p. 43−56
  73. Shallit J. Origins of the Analysis of the Euclidean Algorithm. // Historia Mathematica, v. 21, pp. 401−419 (1994).
  74. Silverman J.H. Fast Multiplication in Finite Fields GF (2N) // Cryptographic Hardware and Embedded Systems, Proc. First Intl Workshop, CHES 99, C K. Koc and C. Paar, eds. pp. 122−134, 1999.
  75. Von zur Gathen J. Pappalardi F. On the reverse Artin problem for primitive roots // Preprint. 1995.
  76. Wu H., Hasan M. A., Blake I.F., Gao S. Finite field multyplier using redundant representation // IEEE Transaction on Computers. 2002. 51. p/1306−1316.
  77. Win E., Bosselaers A., Vandenberghe S., Gersem P., Vandewalle J. A fast software implementation for arithmetic operations in GF (2n) // Lecture Notes in Computer Science. Springer Berlin 1996 p. 65−76
Заполнить форму текущей работой

Сессия? Спокойно!