Программный комплекс облегчения работы с конечными полями
П. А. ГАЛКИН
Научный руководитель – Д. Г. МЕЩАНИНОВ, к. ф.-м. н., доцент
Московский энергетический институт (технический университет)
ПРОГРАММНЫЙ КОМПЛЕКС ОБЛЕГЧЕНИЯ РАБОТЫ С КОНЕЧНЫМИ ПОЛЯМИ
Описываются возможности программного комплекса, разработанного и созданного для проведения стандартных вычислений в конечных полях. Дано описание интерфейса программы, приведены некоторые алгоритмы.
При проведении исследований в дискретной математике иногда приходится работать с полиномами над конечными полями. Некоторые операции достаточно трудоемки, например умножение двух полиномов, возведение полинома в степень, или нахождение неявной функции. При этом основное время тратится на стандартные механические действия, тогда как можно было бы его использовать для решения более творческих задач. Понятно, что для проведения стандартных механический действий идеальным образом подходит компьютер, поэтому было принято решение написать соответствующую программу.
Программа была сделана в виде многодокументного приложения, работающего под операционной системой Windows. Ее окно выглядит следующим образом:
Здесь каждый элемент является строкой. Если строка начинается с символа <пробел>, элемент считается комментарием, выделяется светло-коричневым цветом и при обработке не рассматривается. Все остальные элементы выделяются черным курсивом и обрабатываются по очереди сверху вниз. Строка вида “GF(<число>)” задает размерность поля, и в дальнейшем операции рассматриваются над этим полем. Строка вида “<название функции>[(<список переменных>)]:=<выражение>” задает функцию, которую затем можно использовать, при этом в выражении могут присутствовать ранее определенные функции. Строка вида “<выражение>=” заставляет программу вычислить значение выражения. Значением может быть как элемент поля, так и формула с переменными, присутствующими в выражении. При этом результат отображается синим курсивом справа от символа ‘=’. Каждый из элементов можно двигать по полю с помощью мыши, при этом в случае изменения их взаимного расположения поменяется последовательность обработки элементов.
Для нахождения неявной функции в программе есть предопределенная функция Solve. Она имеет три параметра. Первый – имя функции, определенной ранее в процессе вычисления. Второй – название одной из переменных этой функции, зависимость которой от остальных мы хотим посмотреть, при условии равенства функции нулю. Таких зависимостей, выражаемых функциями, может быть много, но среди них существует конечное число базовых, равное размерности поля [1]. Поэтому есть третий параметр – номер решения, которое необходимо вычислить.
Если базовая функция f(x,y), и мы хотим выявить зависимость y от x при условии f(x,y)=0, решение будет найдено по формуле:
где k – размерность поля, a=0…k-1 – номер решения, Aai=a-i(mod k). Здесь используется ранее разработанный авторами метод аналитического решения логических уравнений.
Рассмотрим следующий пример. Пусть f(x,y)=x4+2xy+3y2+4yx3, поле GF(5). Тогда результатом функции Solve(f,y,0) будет x. Поместив в окне программы строку “f(x,x)=”, видим результат 0.
Список литературы
1. , Мещанинов метод решения уравнений в k-значной логике.// Журнал «Вестник МЭИ» Том 1. – М.:Изд-во МЭИ, 2001. – С.229.
