Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями



Скачать 30.91 Kb.
Дата26.07.2014
Размер30.91 Kb.
ТипДокументы
Чернышева Н.В.

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


Московский энергетический институт (технический университет)
ПРОГРАММНЫЕ СРЕДСТВА ГЕНЕРАЦИИ И ТЕСТИРОВАНИЯ МНОГОЧЛЕНОВ С ЗАДАННЫМИ СВОЙСТВАМИ НАД КОНЕЧНЫМИ ПОЛЯМИ
Описываются возможности программного обеспечения по тестированию и генерации многочленов обладающих свойствами неприводимости, примитивности и базисности нормального множества.
В современных системах защиты информации используются различные конечные поля высоких порядков или иные алгебраические структуры, базирующиеся на таких полях, например, эллиптические кривые. Алгоритмическая структура конечного поля, являющегося расширением того или иного простого поля, определяется неприводимым многочленом, корень которого используется для порождения его базиса. При этом помимо свойства неприводимости имеют значение такие свойства как примитивность многочлена и базисность нормального множества, порождаемого многочленом. В настоящее время актуальна разработка программных средств генерации и анализа применительно к многочленам над полями GF(2) и GF(3) высоких степеней.

Рассматриваются многочлены над конечным полем GF(p). Пусть x – корень многочлена, то есть элемент поля GF(pn), такой что f(x) = 0. Многочлен называется неприводимым, если его нельзя представить в виде произведения многочленов меньшей степени над этим полем и примитивным, если его корень x является примитивным элементом поля GF(pn). Нормальным множеством называется множество следующих степеней корня x - {x, x2,…,x2^(n-1)}. Если это множество является базисом поля GF(pn), то многочлен обладает свойством базисности нормального множества. Особое значение имеют так называемые оптимальные нормальные базисы, имеющие таблицы умножения линейной сложности, и их обобщения – гауссовы нормальные базисы [1].

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

Программное обеспечение включает функции реализующие:

тестирование свойства неприводимости многочлена, с предварительной проверкой приводимости по достаточным признакам,

тестирование свойства примитивности многочлена с использованием базы факторизации [2,3],

тестирование свойства базисности нормального множества,

генерация многочленов со свойствами неприводимости, примитивности и свойством базисности нормального множества,

генерация таблиц неприводимых и примитивных многочленов малого веса,

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

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

Разработанное программное обеспечение охватывает указанные задачи тестирования и генерации многочленов с заданными свойствами над полями GF(2) и GF(3) в широком диапазоне степеней, включающем диапазон степеней, характерных для современных протоколов защиты информации. Разработанное программное обеспечение включено в электронный образовательный ресурс «Алгебраический процессор» [4] и используется для вычисления таблиц в научных публикациях.


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


  1. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А.  Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы.  М.: КомКнига, 2006.

  2. Белова А.Ю., Волокитин М.В. База данных факторизации больших чисел. В книге Труды международной научно-технической конференции Информационные средства и технологии в трех томах. Том 2 – М.:МЭИ, 2008, стр. 161-168.

  3. Brillhart J., Lehmer D., Selfridge J., Tuckerman B., Wagstaff, S., Jr., Factorizations of b^{n}\pm 1,b= 2, 3, 5, 6, 7,10, 11, 12 up to high powers, 3-d ed.,Contemp. Math., vol.22, Amer. Math. Soc., Providence, Rhode Island

  4. Фролов А.Б. Гашков С.Б., Белова А.Ю., Морозов С.В., Жебет С.Ю., Щуров И.И. Программное средство «Алгебраический процессор». В кн. Информатизация инженерного образования: электронные образовательные ресурсы МЭИ. / Под общей ред. С.И.Маслова. - М.: Издательский дом МЭИ, 2008. Стр. 271- 274.

Похожие:

Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconПрограмма междисциплинарного экзамена по специальности 010101 "Математика"
Корни и канонические разложения многочленов над полями вещественных и комплексных чисел. Неприводимые многочлены над полями
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconГиперэллиптические кривые над конечными полями
Целью спецкурса является ознакомление студентов с основными понятиями теории алгебраических кривых, свойствами гиперэллиптических...
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconЛогические дифференциальные операторы и уравнения над конечными полями и параллельные вычисления

Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconСписок вопросов
Теоремы о разложении многочленов над полями r и с на неприводимые множители. Корни многочлена. Теорема о числе корней (над С)
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconСписок вопросов
Теоремы о разложении многочленов над полями r и с на неприводимые множители. Корни многочлена. Теорема о числе корней (над С)
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconСписок вопросов
Теоремы о разложении многочленов над полями r и с на неприводимые множители. Корни многочлена. Теорема о числе корней (над С)
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconОктября 2004 г. Список вопросов
Теоремы о разложении многочленов над полями r и с на неприводимые множители. Корни многочлена. Теорема о числе корней (над С)
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconСовершенная схема множественного разделения секрета над кольцом вычетов по модулю m
Полученные результаты обобщают известные ранее утверждения о свойствах линейных схем разделения секрета над конечными полями, векторными...
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconЗадача для спектров Галуа многочленов § Теорема Гильберта о неприводимости § Обратная задача для спектров Галуа многочленов третьей степени
Циклические расширения 4-ой степени над полями характеристики два ¦
Программные средства генерации и тестирования многочленов с заданными свойствами над конечными полями iconМногоуровневые модели и языки dsl как основа создания интеллектуальных case-систем
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org