Помощь студентам в учебе
Сравнительный анализ методов построения базисов Грёбнера для решения систем уравнений в конечных полях характеристики 2
|
ВВЕДЕНИЕ 3
1. БАЗИСЫ ГРЁБНЕРА КАК СРЕДСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ 7
1.1 Общие сведения из теории полиномиальных систем уравнений 7
1.2 Базисы Грёбнера полиномиальных идеалов 13
1.3 Применение базисов Грёбнера для решения систем уравнений 32
2. АЛГОРИТМЫ ПОСТРОЕНИЯ БАЗИСОВ ГРЁБНЕРА, ОСНОВАННЫЕ НА
СИГНАТУРАХ ПОЛИНОМОВ 37
2.1 Сигнатуры и сигнатурные полиномы 37
2.2 Алгоритм F5: структура и критерии 39
2.3. Модификации F5, использующие редуцирование базисов 44
3. РЕАЛИЗАЦИЯ ПРОГРАММНОГО ПРОДУКТА 47
3.1 Описание структуры программного продукта 47
3.2 Результаты экспериментальных вычислений 54
ЗАКЛЮЧЕНИЕ 58
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 61
ПРИЛОЖЕНИЕ
1. БАЗИСЫ ГРЁБНЕРА КАК СРЕДСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ 7
1.1 Общие сведения из теории полиномиальных систем уравнений 7
1.2 Базисы Грёбнера полиномиальных идеалов 13
1.3 Применение базисов Грёбнера для решения систем уравнений 32
2. АЛГОРИТМЫ ПОСТРОЕНИЯ БАЗИСОВ ГРЁБНЕРА, ОСНОВАННЫЕ НА
СИГНАТУРАХ ПОЛИНОМОВ 37
2.1 Сигнатуры и сигнатурные полиномы 37
2.2 Алгоритм F5: структура и критерии 39
2.3. Модификации F5, использующие редуцирование базисов 44
3. РЕАЛИЗАЦИЯ ПРОГРАММНОГО ПРОДУКТА 47
3.1 Описание структуры программного продукта 47
3.2 Результаты экспериментальных вычислений 54
ЗАКЛЮЧЕНИЕ 58
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 61
ПРИЛОЖЕНИЕ
В настоящее время повсеместно во многих областях точных наук возникают задачи, в которых требуется находить решения систем алгебраических уравнений (САУ) от многих переменных в различных полях. Например, такие задачи возникают при решении задач электродинамики, термодинамики, физики поведения жидкостей. Естественно, что в общем случае точное решение такой задачи является далеко нетривиальной задачей, хотя для отдельных разновидностей таких систем существует целое множество разнообразных способов решения.
Конечно, многое зависит от степени уравнений в данной системе. В данный момент про решение систем линейных алгебраических уравнений (СЛАУ) известно практически всё. Для этого достаточно взглянуть на современные учебные пособия по линейной алгебре. Огромное количество точных и итерационных методов, включая методы Крамера, Гаусса, прогонки, простой итерации и т.д. Но решение систем нелинейных уравнений - гораздо более сложная задача, которая решается, используя огромные затраты по времени и памяти. Для таких систем изобрели свои методы, как точные, так и приближённые, например, методы линеаризации и линеаризационных множеств.
Данная диссертация посвящена проблеме решения систем уравнений в конечных полях характеристики 2. Такие системы используются при решении задач криптографии и теории кодирования. Важно помнить, что в случае конечных полей приближённые методы решения систем использовать невозможно, поэтому на первый план выходят точные методы. Другим неприятным моментом является то, что для уравнений в конечных полях в общем случае отсутствуют формулы корней. Таким образом, большинство систем уравнений решается, в основном, переборными методами за экспоненциальное время.
Целью данной диссертации является оценка эффективности алгоритмов построения базисов Грёбнера полиномиальных идеалов, применительно к конечным полям характеристики 2. Способ использования данных базисов для решения систем был описан Бруно Бухбергером в 1985 году и получил широкую известность за его универсальность. Особым толчком к его изучению стало развитие электронно-вычислительных устройств и компьютерной алгебры [4, стр. 20], которое позволило быстро совершать различные вычисления над полиномами.
Однако, в данный момент, несмотря на наличие в свободном доступе большого количества программных продуктов компьютерной алгебры для вычисления базисов Грёбнера для полиномиальных систем (Maple, Sage, Mathematica, WolframAlpha), все они в основном способны проводить вычисления в контексте трёх основных алгебраических полей: поля комплексных чисел С, поля рациональных чисел Q и конечного поля с простым числом элементов Wp.
Новизна данной работы заключается в том, что:
1) Программные инструменты, которые были бы способны строить базисы Г рёбнера для полиномиальных систем уравнений над конечными полями характеристики 2 W2n, не существует, и поэтому, для достижения цели был самостоятельно программно реализован подобный функционал.
2) Функционал был разработан на основе компилируемого языка программирования, который намного быстрее интерпретируемых языков, используемых современными системам компьютерной алгебры.
3) Данный инструмент очень полезен при разработке устойчивых ко взлому систем компьютерной и сетевой безопасности на основе шифров в конечных полях, а также помехоустойчивых кодов, так как при разработке подобных инструментов используются системы в конечных полях характеристики 2.
4) Было проведено тестирование и анализ известных алгоритмов построения базисов Грёбнера полиномиальных систем в слабо изученном случае коэффициентов в конечном поле характеристики 2.
Для достижения цели были поставлены следующие задачи:
1) Дать определение базисам Грёбнера и описать их свойства, которые будут полезны при решении подобных систем;
2) Изучить первоначальный алгоритм для построения базиса Грёбнера;
3) Встроить применение данного алгоритма в процесс решения системы;
4) Рассмотреть различные способы усовершенствования данного алгоритма;
5) Разработать реализацию рассмотренных алгоритмов для различных алгебраических полей;
6) Дать определение базисам Грёбнера и описать их свойства, которые будут полезны при решении подобных систем;
Структура работы и её содержание полностью соответствуют её цели и поставленным задачам. Текст работы структурно состоит из введения, основной части, заключения, списка использованных источников и приложения.
Основная часть состоит из трёх глав. Первая глава описывает основной теоретический материал, который требуется для понимания того, что из себя представляют базисы Грёбнера, и как они применяются для решения полиномиальных систем уравнений. Проводится анализ методов, которые используются для решения подобных систем. Подробно изложены основы теории полиномиальных идеалов, в том числе теорема Гильберта о базисе, в которой доказывается, что каждый идеал является конечно порождённым и имеет конечный базис. Базисами Грёбнера являются базисы идеалов, обладающие определёнными свойствами. В главе рассматриваются алгоритмы построения данных базисов, обозначается сложность данной процедуры и способы повысить её эффективность.
Вторая глава посвящена наиболее эффективным алгоритмам построения базисов Г рёбнера, которые в процессе вычислений используют так называемые сигнатуры полиномов. В начале главы приводится описание новых сущностей: сигнатуры и сигнатурного полинома и операций над ними. Второй параграф описывает алгоритм F5, который был разработан Жаном-Карлом Фожером в 2002 году, его структуру и механизм работы. Оставшаяся часть главы рассматривает его модификации F5R (2005 год) и F5C (2009 год), которые используют редуцированные базисы Грёбнера для ускорения вычислений.
В третьей главе приводится описание программной реализации алгоритмов, которая была разработана для вычислений базисов Грёбнера в различных алгебраических полях, её классов и методов. Также приводятся и анализируются результаты экспериментов по вычислению базисов Грёбнера в конечных полях характеристики 2.
В качестве приложения доступен весь программный код реализации.
Конечно, многое зависит от степени уравнений в данной системе. В данный момент про решение систем линейных алгебраических уравнений (СЛАУ) известно практически всё. Для этого достаточно взглянуть на современные учебные пособия по линейной алгебре. Огромное количество точных и итерационных методов, включая методы Крамера, Гаусса, прогонки, простой итерации и т.д. Но решение систем нелинейных уравнений - гораздо более сложная задача, которая решается, используя огромные затраты по времени и памяти. Для таких систем изобрели свои методы, как точные, так и приближённые, например, методы линеаризации и линеаризационных множеств.
Данная диссертация посвящена проблеме решения систем уравнений в конечных полях характеристики 2. Такие системы используются при решении задач криптографии и теории кодирования. Важно помнить, что в случае конечных полей приближённые методы решения систем использовать невозможно, поэтому на первый план выходят точные методы. Другим неприятным моментом является то, что для уравнений в конечных полях в общем случае отсутствуют формулы корней. Таким образом, большинство систем уравнений решается, в основном, переборными методами за экспоненциальное время.
Целью данной диссертации является оценка эффективности алгоритмов построения базисов Грёбнера полиномиальных идеалов, применительно к конечным полям характеристики 2. Способ использования данных базисов для решения систем был описан Бруно Бухбергером в 1985 году и получил широкую известность за его универсальность. Особым толчком к его изучению стало развитие электронно-вычислительных устройств и компьютерной алгебры [4, стр. 20], которое позволило быстро совершать различные вычисления над полиномами.
Однако, в данный момент, несмотря на наличие в свободном доступе большого количества программных продуктов компьютерной алгебры для вычисления базисов Грёбнера для полиномиальных систем (Maple, Sage, Mathematica, WolframAlpha), все они в основном способны проводить вычисления в контексте трёх основных алгебраических полей: поля комплексных чисел С, поля рациональных чисел Q и конечного поля с простым числом элементов Wp.
Новизна данной работы заключается в том, что:
1) Программные инструменты, которые были бы способны строить базисы Г рёбнера для полиномиальных систем уравнений над конечными полями характеристики 2 W2n, не существует, и поэтому, для достижения цели был самостоятельно программно реализован подобный функционал.
2) Функционал был разработан на основе компилируемого языка программирования, который намного быстрее интерпретируемых языков, используемых современными системам компьютерной алгебры.
3) Данный инструмент очень полезен при разработке устойчивых ко взлому систем компьютерной и сетевой безопасности на основе шифров в конечных полях, а также помехоустойчивых кодов, так как при разработке подобных инструментов используются системы в конечных полях характеристики 2.
4) Было проведено тестирование и анализ известных алгоритмов построения базисов Грёбнера полиномиальных систем в слабо изученном случае коэффициентов в конечном поле характеристики 2.
Для достижения цели были поставлены следующие задачи:
1) Дать определение базисам Грёбнера и описать их свойства, которые будут полезны при решении подобных систем;
2) Изучить первоначальный алгоритм для построения базиса Грёбнера;
3) Встроить применение данного алгоритма в процесс решения системы;
4) Рассмотреть различные способы усовершенствования данного алгоритма;
5) Разработать реализацию рассмотренных алгоритмов для различных алгебраических полей;
6) Дать определение базисам Грёбнера и описать их свойства, которые будут полезны при решении подобных систем;
Структура работы и её содержание полностью соответствуют её цели и поставленным задачам. Текст работы структурно состоит из введения, основной части, заключения, списка использованных источников и приложения.
Основная часть состоит из трёх глав. Первая глава описывает основной теоретический материал, который требуется для понимания того, что из себя представляют базисы Грёбнера, и как они применяются для решения полиномиальных систем уравнений. Проводится анализ методов, которые используются для решения подобных систем. Подробно изложены основы теории полиномиальных идеалов, в том числе теорема Гильберта о базисе, в которой доказывается, что каждый идеал является конечно порождённым и имеет конечный базис. Базисами Грёбнера являются базисы идеалов, обладающие определёнными свойствами. В главе рассматриваются алгоритмы построения данных базисов, обозначается сложность данной процедуры и способы повысить её эффективность.
Вторая глава посвящена наиболее эффективным алгоритмам построения базисов Г рёбнера, которые в процессе вычислений используют так называемые сигнатуры полиномов. В начале главы приводится описание новых сущностей: сигнатуры и сигнатурного полинома и операций над ними. Второй параграф описывает алгоритм F5, который был разработан Жаном-Карлом Фожером в 2002 году, его структуру и механизм работы. Оставшаяся часть главы рассматривает его модификации F5R (2005 год) и F5C (2009 год), которые используют редуцированные базисы Грёбнера для ускорения вычислений.
В третьей главе приводится описание программной реализации алгоритмов, которая была разработана для вычислений базисов Грёбнера в различных алгебраических полях, её классов и методов. Также приводятся и анализируются результаты экспериментов по вычислению базисов Грёбнера в конечных полях характеристики 2.
В качестве приложения доступен весь программный код реализации.
В качестве основных результатов проведённого исследования можно выделить следующие моменты. Во-первых, был произведён обзор широко известных имеющихся методов решения систем полиномиальных алгебраических уравнений. Были указаны их основные особенности, области применения. Также была дана оценка сложности выполнения данных методов.
Во-вторых, было дано определение базиса Грёбнера полиномиального идеала. Было рассмотрено понятие мономиального упорядочения, показана конечная порождённость идеалов с помощью леммы Диксона и теоремы Гильберта о базисе. Также, чтобы показать главные свойства данных базисов, был изучен алгоритм деления в кольцах полиномов от нескольких переменных. В совокупности с определением S-полинома, был рассмотрен критерий Бухбергера, на основании которого можно распознавать базисы Грёбнера.
В-третьих, был указан алгоритм построения искомых базисов Грёбнера, введённый Бухбергером. Данный алгоритм позволил нам получать базис Грёбнера идеала, порождённого любым набором полиномом, за конечное время. Как следует из исследования, сложность этого алгоритма определяется огромным числом вычислений остатков от деления на множество полиномов. Поэтому, единственным способом улучшить алгоритм является сокращение числа рассматриваемых S-полиномов.
В-четвёртых, был описан способ решения систем уравнений в конечных полях путём построения базиса Грёбнера. Данный способ использует лексикографическое мономиальное упорядочение, которое позволяет строить базис в виде треугольной системы уравнений, последовательно исключая переменные. Единственное неудобство состоит в том, что данное упорядочение строит базис Грёбнера с наивысшими степенями элементов базиса.
В-пятых, было проведено описание и сравнение между собой алгоритмов построения базисов Грёбнера семейства F5, основанных на сигнатурах полиномов. Было дано описание критериев исключения критических пар,
основанных на сигнатурах полиномов, в исходном алгоритме F5, а также показано, как можно улучшить этот алгоритм, представив его модификации F5R и F5C.
В качестве практической части были реализованы на языке программирования C# и протестированы 5 алгоритмов построения базисов Грёбнера во всех основных алгебраических полях, включая конечные поля характеристики 2, операции с которыми не были реализованы в общедоступных реализациях алгоритмов. Также приведены и проанализированы результаты тестов сигнатурных алгоритмов применительно к данным полям. На основании полученных данных, можно сказать, что сигнатурные алгоритмы достаточно эффективно строят базисы Грёбнера в конечных полях характеристики 2, при этом редуцирование промежуточных базисов на примере алгоритма F5C также даёт серьёзный выигрыш в производительности.
Поставленные задачи для достижения цели диссертации были выполнены целиком и полностью, подтверждая новизну проделанной работы. Был дан весь необходимый математический и алгоритмический аппарат, использующий базисы Грёбнера, для решения систем алгебраических уравнений в конечных полях. Готова реализация пяти алгоритмов построения базисов Грёбнера, способная эффективно работать в конечных полях характеристики 2, что недоступно для других известных реализаций. Данную реализацию можно применять в разработке криптографических защитных систем на основе блочного и поточного битового шифрования, а также в теории кодирования при разработке новых, более совершенных кодов, обнаруживающих и исправляющих ошибки.
Известен тот факт, что время и сложность построения базиса Грёбнера сильно зависят от степени и количества переменных в системе, а также от используемого мономиального упорядочения. Доказано, что данный метод имеет чрезвычайно высокую сложность в наихудшем случае. Но также широко известно, что вероятность такого случая чрезвычайно низка, и большинство алгоритмов для построения базисов Грёбнера работают гораздо быстрее. С появлением всё более эффективных алгоритмов, таких как F5, F5C и более новые модификации алгоритма Бухбергера, можно надеяться, что широко распространенное мнение о базисах Грёбнера, как сложном, неудобном и трудозатратном средстве решения систем полиномиальных уравнений, изменится, и пессимизм в их отношении пропадёт.
Во-вторых, было дано определение базиса Грёбнера полиномиального идеала. Было рассмотрено понятие мономиального упорядочения, показана конечная порождённость идеалов с помощью леммы Диксона и теоремы Гильберта о базисе. Также, чтобы показать главные свойства данных базисов, был изучен алгоритм деления в кольцах полиномов от нескольких переменных. В совокупности с определением S-полинома, был рассмотрен критерий Бухбергера, на основании которого можно распознавать базисы Грёбнера.
В-третьих, был указан алгоритм построения искомых базисов Грёбнера, введённый Бухбергером. Данный алгоритм позволил нам получать базис Грёбнера идеала, порождённого любым набором полиномом, за конечное время. Как следует из исследования, сложность этого алгоритма определяется огромным числом вычислений остатков от деления на множество полиномов. Поэтому, единственным способом улучшить алгоритм является сокращение числа рассматриваемых S-полиномов.
В-четвёртых, был описан способ решения систем уравнений в конечных полях путём построения базиса Грёбнера. Данный способ использует лексикографическое мономиальное упорядочение, которое позволяет строить базис в виде треугольной системы уравнений, последовательно исключая переменные. Единственное неудобство состоит в том, что данное упорядочение строит базис Грёбнера с наивысшими степенями элементов базиса.
В-пятых, было проведено описание и сравнение между собой алгоритмов построения базисов Грёбнера семейства F5, основанных на сигнатурах полиномов. Было дано описание критериев исключения критических пар,
основанных на сигнатурах полиномов, в исходном алгоритме F5, а также показано, как можно улучшить этот алгоритм, представив его модификации F5R и F5C.
В качестве практической части были реализованы на языке программирования C# и протестированы 5 алгоритмов построения базисов Грёбнера во всех основных алгебраических полях, включая конечные поля характеристики 2, операции с которыми не были реализованы в общедоступных реализациях алгоритмов. Также приведены и проанализированы результаты тестов сигнатурных алгоритмов применительно к данным полям. На основании полученных данных, можно сказать, что сигнатурные алгоритмы достаточно эффективно строят базисы Грёбнера в конечных полях характеристики 2, при этом редуцирование промежуточных базисов на примере алгоритма F5C также даёт серьёзный выигрыш в производительности.
Поставленные задачи для достижения цели диссертации были выполнены целиком и полностью, подтверждая новизну проделанной работы. Был дан весь необходимый математический и алгоритмический аппарат, использующий базисы Грёбнера, для решения систем алгебраических уравнений в конечных полях. Готова реализация пяти алгоритмов построения базисов Грёбнера, способная эффективно работать в конечных полях характеристики 2, что недоступно для других известных реализаций. Данную реализацию можно применять в разработке криптографических защитных систем на основе блочного и поточного битового шифрования, а также в теории кодирования при разработке новых, более совершенных кодов, обнаруживающих и исправляющих ошибки.
Известен тот факт, что время и сложность построения базиса Грёбнера сильно зависят от степени и количества переменных в системе, а также от используемого мономиального упорядочения. Доказано, что данный метод имеет чрезвычайно высокую сложность в наихудшем случае. Но также широко известно, что вероятность такого случая чрезвычайно низка, и большинство алгоритмов для построения базисов Грёбнера работают гораздо быстрее. С появлением всё более эффективных алгоритмов, таких как F5, F5C и более новые модификации алгоритма Бухбергера, можно надеяться, что широко распространенное мнение о базисах Грёбнера, как сложном, неудобном и трудозатратном средстве решения систем полиномиальных уравнений, изменится, и пессимизм в их отношении пропадёт.