Дистанционный электронный образовательный ресурс «Алгебраический процессор НИУ МЭИ»

Авторы статьи: , «НИУ«МЭИ», профессор, *****@***ru; , , «НИУ «МЭИ», магистр, al. *****@***ru , МГУ им. , профессор, *****@***com ; , «НИУ«МЭИ», аспирант, <*****@***com>

Описаны состав, область применения, поддерживаемые алгебраические структуры, функциональность алгебраической библиотеки дистанционного электронного образовательного ресурса «Алгебраический процессор НИУ МЭИ», и его особенности как программного продукта.

Состав, область применения и адрес ресурса

Дистанционный электронный образовательный ресурс (ЭОР) Алгебраический процессор НИУ МЭИ обеспечивает удаленный доступ к алгебраическим библиотекам, в частности к алгебраической библиотеке MPEI AAL(MPEI Algebraic Abstractions Library), при вычислениях в различных числовых, полиномиальных и эллиптических структурах по составляемым с подсказками алгебраического процессора программам или по готовым программам из лабораторного практикума. Он был создан в развитие локальной версии [1,2,3] и представляет собой комплекс программных средств, объединенных дистанционным интерактивным web-интерфейсом, обеспечивающим удаленный доступ как к теоретическим материалам изучаемых курсов, так и к интерактивным программам взаимодействия с вычислительными ресурсами в процессе реализации алгебраических вычислений с визуализацией результатов.

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

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

Теоретические разделы ресурса подготовлены авторами на основе изданий [4,5]. Функциональные возможности ресурса достаточны для воспроизведения (моделирования) и программирования большинства алгоритмов и криптографических протоколов, приведенных в этих изданиях.

Ресурс доступен по адресу http://mm. mpei. *****:8080/ (id:user, без пароля, временами страница может быть недоступна).

Поддерживаемые алгебраические структуры

Ниже перечислены алгебраические структуры, в которых возможны вычисления с использованием интерактивных средств «Алгебраического процессора».

1. - кольцо целых чисел, кольца вычетов по модулю n, простые поля характеристики p;

2. - квадратичные расширения простых полей ;

3. - кольца многочленов над полем GF(2), кольца вычетов по модулю многочлена f(X), поля;

4. - кольца многочленов над полем GF(3), кольца вычетов по модулю многочлена f(X) , поля;

5. - расширения четверной степени полей , порождаемые корнем многочлена

6. - расширения шестой степени полей , порождаемые корнем многочлена

7. - группы точек эллиптических кривых над полями про-стой характеристики;

8. - группы точек эллиптических кривых над квадратич-ными расширениями полей простой характеристики;

9. - группы точек эллиптических кривых над полями ха-рактеристики два;

10. - группы точек эллиптических кривых над полями характеристики три.

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

В ряде случаев, например при вычислении порядка элемента той или иной группы, используется разложение порядка группы. Для вычисления порядка и его разложения предусматривается вызов функций вычисления порядка и последующего его разложения. Разложение порядков мультипликативных групп полей характеристики два и три может быть получено из базы данных на основе каннингемовского проекта (The Cunningham Project) [6] в интерактивном режиме. Для разложения других больших чисел используется функция msieve библиотеки [7], а для вычисления порядков эллиптических кривых – функции schoof и schoof2 библиотеки M. I.R. A.C. L. [8]. Если условия выполнения операции или исходные данные не соответствуют требуемым, то при попытке ее выполнения появится сообщение с описанием исключения. Например, при выполнении сложения в передаваемый модулярный многочлен должен быть неприводимым. Если это не так, то появится предупреждение и выполнение операции будет прервано. При сложении в операция с таким полиномом выполнится.

Имеются операции генерации и тестирования простых чисел, неприводимых и примитивных многочленов над полями характеристики два и три. Таким образом, интерфейс дистанционной версии сохраняет функциональность интерфейса локальной версии «Алгебраического процессора» и устроен таким образом, чтобы все необходимое для вычислений, характерных для современных криптографических протоколов было «под рукой», что позволяет сосредоточиться на изучении их особенностей, не отвлекаясь на рутинное программирование. В дистанционной версии воспроизведён лабораторный практикум локальной версии [1].

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

На рис.1 приведен пример программы генерации и тестирования простого числа заданной длины в битах, которая может быть выполнена на сервере кафедры математического моделирования (ММ) «НИУ «МЭИ» с любого удаленного компьютера.

На рис. 2. Показан результат, доставленный на удаленный компьютер.

На рис.3 дан скриншот листингов программы и результата.

p=Integer()

print "Получение псевдопростого числа p=",

print p. GeneratePrime(100)

order=Integer()

print "p-1=", order. Sub(p, Integer(1))

res=FactorizationAlgorithms(order).MsieveDecomposition()

print "Разложение p-1:", res. toList()

print "Подтверждение по тесту Люка, что p есть простое число: "

print Integer().ModifiedTestLuka(res, p)

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

Получение псевдопростого числа p= AAL. Integer()

p-1= AAL. Integer()

Разложение p-1: [('2', '4'), ('3', '1'), ('4159', '1'), ('', '1')]

Подтверждение по тесту Люка, что p есть простое число: True

>>> 

Рис. 2. Результат исполнения программы на рис. 1

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

Примечание. Для наблюдения процесса дистанционного исполнения программы на рис. 1 и других программ можно вызвать Алгебраический процессор по адресу http://mm. mpei. *****:8080/

далее скопировать программу на рис. 1 в правое окно рабочего стола и по кнопке «Поехали» получить результат в левом окне. Особенности составления подобных программ, использования языка pyton, библиотеки MPEI AAL можно увидеть в справке, открывающейся нажатием панели «Справка» верхнего меню (рекомендуется ее открывать в отдельной вкладке).

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

Общая характеристика и функциональность библиотеки MPEI AAL, доступной посредством дистанционного алгебраического процессора « НИУ«МЭИ».

Теоретическую базу алгебраической библиотеки составляют теория конечных полей и теория эллиптических кривых.

MPEI AAL – это статически подключаемая библиотека, разработанная на языке программирования C++, использующая STL (Standard Template Library – стандартная библиотека шаблонов для С++), содержащая 29 классов.

MPEI AAL включает функции, реализующие:

1.  Теоретико-числовые алгоритмы: вычисления символов Лежандра и Якоби, извлечения квадратного корня из квадратичного вычета по модулю простого числа и по составному модулю с известным его разложением; различные модификации алгоритма Евклида (основной, расширенный, бинарный, основной, расширенный бинарный, расширенный для нахождения обратного элемента).

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

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

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

Особенности дистанционного ЭОР Алгебраический процессор «НИУ «МЭИ» как программного продукта

В дистанционном ЭОР Алгебраический процессор «НИУ «МЭИ» (Свидетельство о государственной регистрации программы для ЭВМ № от 01.01.01г.) для выполнения программ, аналогичных программе, показанной выше, используется интерпретатор языка python, к возможностям которого добавлены функции Алгебраической библиотеки MPEI AAL. Связывание осуществляется через прикладной программный интерфейс языка (C API), который позволяет вызывать в программах функции из библиотек и других компилируемых модулей, написанных на C и C++. Реализован способ автоматизации связывания с помощью генератора интерфейсов SWIG (англ. Simplified Wrapper and Interface Generator) [9].

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

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

2. Есть возможность автоматизировать выполнение определенных операций на различных наборах входных данных с использованием текстовых скриптов.

3. C++ хорошо подходит для алгебраических задач, когда быстродействие играет важную роль. Однако для рядовых задач, по статистике, только 20% времени тратится на выполнения 80% кода. Для этих 80% не критичного к времени выполнения кода используется интерпретируемый язык высокого уровня. Такой вариант сочетает лучшие качества обоих программных сред: быстроту компилируемого C++ и богатую стандартную библиотеку Python, включающую средства для работы со многими сетевыми протоколами, элементами интерфейса пользователя, форматами сериализации данных и криптографическими протоколами, что позволяет создавать на его основе сложные приложения. Также в языке имеется набор встроенных средств для научных вычислений: поддерживаются многозначные и комплексные числа, построение графиков и диаграмм и даже символьные вычисления.

4. Благодаря использованию в Python сборщика мусора, программист может не беспокоиться об утечках памяти при использовании динамических объектов библиотеки.

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

На рис. 4 показаны отношения компонентов среды разработки библиотеки MPEI AAL. Созданием такой среды мы обеспечиваем независимость разрабатываемой нами библиотеки от различных компиляторов и языков программирования.

Рис. 4. Отношения компонентов среды разработки библиотеки MPEI AAL

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

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

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

Заимствования. На сервере помимо библиотеки MPEI AAL используется функция msieve библиотеки [Msieve integer factorization library. http://www. /~jasonp/qs. html], функции schoof и schoof2 библиотеки M. I.R. A.C. L. [Multiprecision Integer and Rational Arithmetic C/C++ Library. www. cs. sunysb. edu/.../implement. shtml], интерпретатор python 2.7.2, фреймворк bottle. py 0.11, сервер cherrypy 3.1.2, субд sqlite 3.7.7. На стороне клиента (через сервер) используются следующие библиотеки: prettyprint. js, bootstrap, ace editor, cleditor, jqconsole, knonckout. js. При создании раздела «Справка» использованы программы pydoc, markdown, xsltproc. Все заимствованные и использованные при создании ресурса программы, как и дистанционный алгебраический процессор, распространяются для образовательных целей свободно. Параметры сервера. ОС Ubuntu 11.10 (GNU/Linux 3.0.0-12-generic i686).
Процессор Intel(R) Celeron(R) CPU 2.00GHz. Память 1GB, диск 110GB,
сеть Broadcom Corporation BCM4Base-T и Realtek Semiconductor Co., Ltd. RTL-8139/8139C/8139C+.

Общий объем программного обеспечения (без текстовых файлов). 
Библиотека AAL 3,9мб(код). Дист. версия 146.2 кб код, 158.2 кб интерфейс и справка, 1мб картинки, 8.4 мб файлы практикума. все вместе 9.8мб.

Работа выполнена при финансовой поддержке РФФИ, проект а.

Литература

1.  Фролов А. Б., , М Электронный образовательный ресурс "Алгебраический процессор". Труды VI Международной научно-практической конференции "Современные информационные технологии и ИТ-образование". 12-14 декабря 2011, Москва, МГУ им. . 2011. C. 599-606.

2.  Фролов А. Б., , М Электронный образовательный ресурс "Алгебраический процессор". Труды международной научно-методической конференции «Информатизация инженерного образования ИНФОРИНО 2012». Издательский дом МЭИ. С.517-520.

3.  Программное средство «Алгебраический процессор»// , , . В кн. Информатизация инженерного образования. Электронные образовательные ресурсы МЭИ. Вып.С.

4.  Болотов А. А., Гашков С. Б., Фролов   введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. Изд. 2, доп. М.: Комкнига. 2012.

5.  Болотов А. А., Гашков С. Б., Фролов  введение в эллип-тическую криптографию. Протоколы криптографии на эллиптических кривых. Изд. 2, доп. М.: Комкнига. 2012.

6.  John Brillhart D. H., Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff, Jr. Factorisations of bn±1, b=2,3,6,7,10,11 up to high powers. Amer. Math. Soc., Providence, Rhode Island, 2002.

http://www. ans. org/online_bks/conm22

7.  Msieve integer factorization library. http://www. /~jasonp/qs. html

8.  Multiprecision Integer and Rational Arithmetic C/C++ Library. www. cs. sunysb. edu/.../implement. shtml

9.  Guido van Rossum. Python/C API Reference Manual. CreateSpace, 2009.