Алгоритмы компьютерной алгебры в теории групп, кодировании и кристаллографии

Грачев, Евгений Владимирович

Алгоритмы компьютерной алгебры в теории групп, кодировании и кристаллографии тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Грачев, Евгений Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2010 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Алгоритмы компьютерной алгебры в теории групп, кодировании и кристаллографии»

Автореферат диссертации на тему "Алгоритмы компьютерной алгебры в теории групп, кодировании и кристаллографии"

004600178

УДК 512.54 |-[а правах рукописи

Грачев Евгений Владимирович

АЛГОРИТМЫ КОМПЬЮТЕРНОЙ АЛГЕБРЫ В ТЕОРИИ ГРУПП, КОДИРОВАНИИ И КРИСТАЛЛОГРАФИИ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск-2010

1 1 АПР 2010

004600178

Работа выполнена в Новосибирском государственном техническом университете

Научный руководитель:

кандидат физико-математических наук, доцент Ивлева Ася Михайловна

Официальные оппоненты:

доктор физико-математических наук, доцент Бардаков Валерий Георгиевич

Защита состоится 27 апреля 2010 г. в 14 часов на заседании диссертационного совета Д 212.099.02 в Сибирском федеральном университете по адресу: 660041, г. Красноярск, пр. Свободный, 79.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета.

Автореферат разослан "_" марта 2010 г.

Ученый секретарь диссертационного совета _¿^У Бушуева Н.А.

доктор физико-математических наук, профессор Созутов Анатолий Ильич

Ведущая организация:

Государственное образовательное учреждение высшего профессионального образования "Новосибирский государственный педагогический университет"

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Начало изучения строения групповых колец и их мультипликативной структуры было положено в работах Г. Хигмана (1940). В них изучались групповые кольца абелевых групп, их мультипликативная структура и строение группы единиц групповых колец (т.е. группы обратимых элементов группового кольца).

Дальнейшые исследования групп единиц целочисленных групповых колец неабелевых групп основаны на их представлении группами матриц. Укажем на результаты J. Hughers, K.R. Pearson |7], которые описали группу единиц кольца ZS$ следующим образом:

Аналогичное представление получили P.J. Allen, C.Hobby [1] для кольца ZAc

U(ZAa) = {±1} х {X € SL3(Z): X = (zy) удовлетворяет (1), (2)} ,

В работе E.G. Goodaire, Е. Jespers, M.M.Parmenter [5] описаны единицы кольца ZG в случае, когда G - конечная группа, такая, что G/Z{G) = С2хС2 и G/G' и Z(G) каждая имеют экспоненту 2,3,4 или 6. В

(1)

ж 12 + ям + £з1 = а; 13 + ^21 + хзг = 0 (mod 4).

(2)

статье J. Ritter, S.K. Sehgal [10] описаны порождающие для подгрупп конечного индекса группы единиц целочисленного группового кольца ZG, где G принадлежит некоторому классу конечных групп, и приводят пример такой группы G =< а, Ь,с : а4 = [о, 6] = [а, с] = 1,а2 = б2 = с2 = [Ь, с] >. Кроме того, С.Р. Milies [9] описал группы единиц целочисленного группового кольца диэдральной группы восьмого порядка ZD\ и доказал, что в ней существуют только 2 несопряженные максимальные подгруппы порядка 8. Отметим в заключение, что в работах Р.Ж. Алеева и его учеников изучены центральные единицы целочисленных групповых колец различных конечных групп.

Все эти результаты относятся к описанию порождающих групп единиц целочисленных групповых колец конкретных конечных групп. Они направлены на решение проблемы 17 из монографии S.K. Sehgal (12J: определить представления мультипликативных групп ZG* различных конечных групп G.

Следует отметить значение для всей теории групповых колец проблемы изоморфизма, сформулированной уже Г.Хигманом: следует ли из изоморфизма групповых колец ZG\ = ZG2 изоморфизм самих групп Gx £ G2?

Понятно, что для групповых колец с тривиальной группой единиц, ответ положительный, но Г. Хигман доказал, что и для конечных абеле-вых групп это так. Были получены положительные результаты во многих других частных случаях. Однако в общем случае ответ на проблему оказался отрицательный, М. Hertweck [6] показал, что существуют две неизоморфные конечные группы G\ и G%, групповые кольца которых ZG 1 и ZG2 изоморфны.

В связи с проблемой изоморфизма для произвольных конечных групп G.H. Cliff, S.K. Sehgal и A.K. Weiss [3j поставили два вопроса.

1) Расщепляемо ли вложение G —► V(ZG)7

2) Если расщепляемо, то существует ли нормальное дополнение без кручения?

Отметим, что

V(ZG) = € U(ZG): £aff = 1}

- нормализованная группа единиц кольца ZG. Здесь через U(ZG) обозначена группа единиц группового кольца ZG.

Очевидно, что U(ZG) = {±1} х V(ZG), поэтому часто вместо U(ZG) рассматривают V(ZG). Вложение группы G в группу Я называется расщепляемым, если Я = N\G, где G = G, УУ<зЯ, TVnÓ = {1}, при этом N называется нормальным дополнением G. В случае положительных ответов на оба вопроса получаем, что G имеет в V(ZG) нормальное дополнение без кручения, а отсюда следует, что всякая конечная подгруппа группы V(ZG) изоморфна подгруппе G, что ведет к решению проблемы изоморфизма для ZG. Это объясняет интерес к нормальным дополнениям группы G в группе V(ZG). Укажем известные к настоящему времени результаты.

Так P.J. Allen и С. Hobby [2] определили два нормальных дополнения для S3 в V(ZS3): одно без кручения, второе содержит элемент порядка 2, при этом дополнение без кручения является свободной группой ранга 3. А Е. Jespers и G. Leal [8] описали метод вычисления единиц кольца ZG, в котором G - конечная 2-группа с условием, что G/Z(G) - четверная группа Клейна. Этот класс групп содержит две группы порядка 8, группу кватернионов и диэдральную группу Di, а также четыре группы порядка 16. Кроме этого, A. Dooms и Е. Jespers [4] описали четыре нормальных дополнения к S3 в V(ZS¡), три из которых изоморфны свободной группе ранга 3, а одно содержит периодические элементы. При этом они показали, что других нормальных дополнений нет.

Укажем, что R.K. Sharma и S. Gangopadhyay [11] доказали, что в V(ZSi) имеется подгруппа конечного индекса без кручения, но оставили открытым вопрос о существовании нормального дополнения без кручения к 54 в группе V(ZSi).

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

Другой раздел диссертации посвящен построению новой криптосистемы - защищенной системы связи, предложенной С.К. Росошеком.

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

Заключительные разделы работы посвящены задачам кристаллографии. Известен широкий класс гидратных соединений включения, т.е. таких соединений, в которых молекулы воды посредством водородных связей образуют трехмерный каркас, имеющий полости различного типа. На данный момент известны следующие типы гидратных каркасов: кубические структуры I, II; гексагональные структуры I, II, III; тетрагональные структуры I, II, III; ромбическая структура. Анализ этих структур показал наличие в них полостей D, D', Т, Н, Р и Е -типов. В 2001 году была открыта тетрагональная структура IV с ранее неизвестным типом полости. Строение каркасов с этими структрами сложное, а разбиение каркаса на полости является довольно трудоемким. Поэтому большой интерес вызывает теоретическое обоснование и практическое определение такого разбиения. Предварительным шагом на пути определения этого разбиения служит задача генерации простых многогранников, а также задача о строении групп автоморфизмов точечных кристаллографических групп. Поскольку процесс получения новых гидратных структур продолжается, то решение поставленных задач является крайне актуальным для химии клатратных соединений.

Цель диссертации

Целью настоящей диссертационной работы является разработка и реализация алгоритмов для описания строения мультипликативных групп целочисленных групповых колец групп As, S5, Aß, Ср на языке полупрямых произведений и нахождения линейных представлений этих групп, разработка алгоритмов для построения криптосистем на основе использования целочисленных групповых колец, разработка математического аппарата и алгоритмов для кристаллографического анализа гидратных каркасов.

Методика исследований

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

Научная новизна

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

Теоретическая и практическая ценность

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

Апробация работы

Результаты диссертации были представлены на

- Международной конференции АССМБ-2 (Новосибирск, 2004),

- Всероссийском симпозиуме по абелевым группам (Бийск, 2006),

- Международной конференции "Алгебра и ее приложения" (Красноярск, 2007),

- Международной школе "Пограничные вопросы универсальной алгебры и теории моделей" (Эрлагол, 2007),

- Международной конференции "ТЬория функций, алгебра и математическая логика" (Алма-Ата, 2007),

- Международной конференции "Современные проблемы математики, информатики и управления" (Алма-Ата, 2008),

- Международной научно-практической конференции "Использование экономико-математических методов в науке, управлении и образовании" (Новосибирск, 2009),

- семинаре "Эварист Галуа" (НГУ),

- семинаре кафедры алгебры и математической логики (НГТУ).

Публикации

Основные результаты опубликованы в работах [13]-[24|, список которых помещен в конце автореферата. Работа [13] входит в перечень ведущих научных изданий, определенный ВАК.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, списка литературы. В тексте диссертации имеется 8 рисунков и 6 таблиц. Список литературы включает 47 наименований. Объем работы - 110 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Основными результатами работы являются следующие.

1. Доказаны теоремы, описывающие мультипликативную структуру колец ZSь, 2Ае, ZCp в терминах полупрямых произведений и найдены линейные представления групп единиц перечисленных выше колец.

2. На основе целочисленного группового кольца группы £>з построена криптосистема Эль-Гамаля-Росошека.

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

4. Установлено строение групп автоморфизмов точечных кристаллографических групп.

5. Разработаны алгоритмы и программное обеспечение для решения задачи о разбиении гидратного каркаса на полости.

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

В главе 1 описаны алгоритмы для решения задач по теории групп. К ним относятся.

1. Генерация группы, заданной порождающими элементами.

2. Построение таблицы неприводимых характеров.

3. Расчет неприводимых неэквивалентных представлений.

4. Описание групп автоморфизмов точечных кристаллографических групп.

В главе 2 детально описывается строение группы V{20) для групп 5б, Ав и подгруппы конечного индекса дня групп и(2Ср) (р - простое).

Результаты представлены в следующих теоремах.

Теорема 1. Вложение группы А$ в расщепляемо, при

этом нормальное дополнение к группе Аъ является группой без кручения.

Теорема 2. Вложение группы ¿>5 в У^Бь) не расщепляемо.

Пусть <рт : СЬп{2) —> а,п(гт) - гомоморфизм Минковского, где Ът - кольцо вычетов по модулю т.

В группе У(££>(£>5)) рассмотрим инвариантный ряд подгрупп

У(гп(я5)) > В> К5> Вх> Кю > В2> Кб >Вз> К12 >В4>

Тогда справедлива

Теорема 3. У(2[Б(55)])/В £ С2; В/К5 £ С* X (С2 х ¿3(5));

КУВ1 £ Кег^- В,1КЮ £ С* X (С2 х ¿3(5));

К10/В2 £ Кег<рю; В2/К6 = С34 х (С4 X Л8);

Кб/В3 £ Кег<р6; В3/Ки =С6х С| х С33;

Л'12/Я4 = Й4/А20 = С25 х С4 х С,50.

Доказательства этих теорем опубликованы в работах [13] и [15]. Идея построения дополнения и использования теории представлений групп принадлежит научному руководителю диссертанта, а теоретическое обоснование и математическая обработка результатов - автору.

Кроме этого установлены две теоремы о полупрямом разложении группы единиц.

Теорема 4. Вложение группы Ае в У^О(Ав)) не расщепляемо.

В группе рассмотрим инвариантный ряд подгрупп

К(Я£)(Л6)) > А'6 > В > К'6 > > К20 > В2 > К12 >В3> К я.

Тогда справедлива

Теорема 5. У(г[П(А6)))/К6 £ С| X СЬ4(^б);

Ке/В = Кепр6; В/К£ = (С24 X Л8) X С4;

«5/^1 £ Кегщ; ^/Ам = С240 х (С| X 518(5));

= Кегфы; В2/К12 * С2М X (С324 X С/,3(г3(ч/2)));

А12/В3 £ Кегф12\ Вз/А« ^ С325 х Cf х X С73.

Доказательство этих теорем опубликовано в [16]. В этой работе научному руководителю диссертанта принадлежит идея использования теории представлений групп, а теоретическое обоснование использованных далее алгебраических методов и математическая обработка результатов вычислений принадлежит диссертанту.

Данные теоремы полностью описывают строение групп единиц целочисленных групповых колец соответствующих групп.

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

. Рассмотрим конечную группу й и ее целочисленное групповое кольцо 20. Пусть 5 - группа автоморфизмов этого кольца.

Любая криптосистема предполагает наличие не менее двух участников сеанса связи. Участник, который шифрует информацию, и участник, который ее расшифровывает. Пусть В и А такие участники. Создание криптосистемы разобьем на три этапа. Первый этап включает в себя генерацию ключей. Второй этап включает этап шифрования информации и, наконец, третий этап - ее расшифровку.

Этап 1. (Генерация ключей).

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

Этап 2. (Алгоритм шифрования).

После получения открытого ключа участника А, участник В для шифрования своего сообщения действует следующим образом: а) вычисляет случайный сеансовый автоморфизм ф достаточно высокого порядка, который принадлежит централизатору автоморфизма ф\ б) вычисляет ф(х~1) и ф(ф(х))\ в) записывает исходный текст в виде т € ZG и вычисляет тп-ф(ф(х))\ г) в результате участник В отправляет участнику А криптограмму с = (ф(х~1), т-ф(ф(х))). Заметим, что в каждом сеансе связи автоморфизм ф нужно задавать заново.

Этап 3. (Алгоритм расшифрования).

Получив криптограмму с, участник А для расшифрования действует следующим образом: а) используя свой секретный ключ ф, вычисляет 2 = ф{ф(х~1))\ находит тп, вычисляя гя • •ф(ф(х)) • г = гп.

Покажем корректность расшифрования.

т • ф(ф(х)) • г = т • ф(ф(х)) • ф(ф(х~1)) = т-ф • Ф(х) • ф ■ ф(х~1) = тп • ф ■ ф{ х) ■ ф • ф{х~1) = тп-ф • ф(х ■ х-1) = т • ф • ф(1) = т • 1 = т.

Результаты этой главы принадлежат автору диссертации, они опубликованы в работе [14]. Для построения криптосистем на основе целочисленных групповых колец групп S^ и 5/2(3) найдены порождающие и изучено строение групп автоморфизмов этих колец в работах [22] и [24].

В главе 4 изложены алгоритмы решения следующих задач.

1) Разбиение гидратного каркаса на полости.

2) Генерация всех простых многогранников с заданным четным числом вершин.

Остановимся подробнее на первой задаче. Для этого дадим ряд определений.

Определение. Многогранником (полиэдром, полостью) будем называть любой планарный трехсвязный граф. Многогранник будем называть простым, если все его вершины трехвалентны.

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

В графе гидратного каркаса конечный связный подграф б будем называть разбиваемым на многогранники (полости), если его можно представить в виде объединения многогранников й = Рх и Рг II • • • и Р*.

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

1) Все многогранники Р* простые и не содержат треугольных граней.

2) Все вершины четырехвалентны и принадлежат ровно четырем полостям.

3) Все ребра принадлежат трем многогранникам и трем граням.

4) Каждая грань принадлежит двум многогранникам.

5) Пересечение любых двух граней либо пусто, либо состоит го единственного ребра.

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

7) Любые два смежных ребра принадлежат ровно одной грани.

8) Любые две смежных грани принадлежат ровно одному многограннику.

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

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

В рамках второй задачи была разработаны алгебраические методы на основе которой создана программа Cavities. Она позволяет находить все имеющиеся полости в гидратном каркасе. С помощью данной программы было изучено строение шести структур клатратных гидратов. Это кубические структуры I и II, тетрагональные структуры I и II, гексагональная структура III и ромбическая структура I. В диссертации подробно рассмотрено строение тетрагональной структуры I. Данная структура содержит следующие полости: D-полость (многогранник 512), Т-полость (многогранник 51262) и Р-полость (многогранник 51263). В тетрагональной структуре 1 имеются также сдедующие четырехсекци-онные полости: TZD, Т3Р, D3P, D2T2, D2TP, T2DP, P2DT.

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

Алгебраические методы, указанные в этой главе, принадлежат автору диссертации, а химические приложения выполнены его соавторами. Все эти результаты опубликованы в работах [18 - 21] и [23].

В конце диссертации содержится список программ, реализующих предложенные алгоритмы. Все программы являются оригинальными, они разработаны автором диссертации и иллюстрируют возможности использования полученных алгебраическими методами теоретических результатов. Эти программы являются общедоступными, они размещены в интернете на странице НГТУ. Адрес сайта http://ciu.nstu.ru/kaf/persons/27621/?page=182.

СПИСОК ЛИТЕРАТУРЫ

1. Allen P.J., Hobby С. A Characterization of Units in Z[A4] // J. of

Algebra, 1980, Vol 66, P. 534-543.

2. Allen P.J., Hobby С. A note on the unit group of ZS3 // Proc. A.M.S., 1987, Vol 99, P. 9-14.

3. Cliff G.H., Sehgal S.K., Weiss A.R. Units of integral Rroup Rings of Metabelian Groups // J. Algebra, 1981, Vol 73, P. 167-185.

4. Dooms A., Jespers E. Normal Complements of the Trivial Units in the Unit Group of Some Integral Group Rings // Commun. Algebra, 2003, Vol 31, № 1, P. 475-482.

5. Goodaire E.G., Jespers E., Parmenter M.M. Determining units in some integral group rings // Canad Math. Bull. 1990. Vol 33, № 2. P. 242-246.

6. Hertweck M. A. Counter-example to the isomorphism problem for integral group rings // Annals of Mathematics, 2001, Vol 154, P. 115138.

7. Hughers J., Pearson K.R. The group of units of the integral group ring ZS3// Canad Math. Bull., 1972, Vol 15, № 4, P. 529-534.

8. Jespers E., Leal G. Describing units of integral group rings of some 2-groups // Cominun. Algebra, 1991, Vol 19, № 6, P. 1809-1826.

9. Milies P.C. The units of the integral groups ring ZD4 // Doc. Soc. Brazil. Math., 1972, № 4, P. 85-92.

10. Ritter Y., Sehgal S.K. Construction of units in integral group rings of finite nilpotent groups // Trans. Amer. Mat. Soc., 1991, № 324, P. 603621.

11. Sharma R.K., Gangopadhyay S. On congruence subgroups and units in ZS4 // Commun. Algebra, 2004, Vol 32, № 2, P. 663-688.

12. Sehgal S.K. Units in integral group rings // Longman Scientific and Technical Essex, 1993.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

13. Грачев Е.В., Попова A.M. Единицы целочисленного группового кольца группы As // Вестник Красноярского государственного университета. Серия: физ.-мат. науки. 2006. № 4. С. 54-59.

14. Грачев Е.В. Строение группы единиц целочисленного группового кольца циклической группы простого порядка // Algebra and Model Theory 6. Новосибирск. 2007. С. 3840.

15. Грачев Е.В., Попова A.M. Группа единиц целочисленного группового кольца группы S5 // Абелевы группы. Материалы всероссийского симпозиума. Бийск. 2006. С. 13.

16. Грачев Е.В., Попова A.M. Мультипликативная группа кольца ZAg // Международная конференция «Алгебра и ее приложения». Тезисы докладов. Красноярск. 2007. С. 38-39.

17. Грачев Е.В., Попова A.M., Журков С.В. Некоторые алгоритмические вопросы целочисленных групповых колец // Международная конференция «Теория функций, алгебра и математическая логика». Алматы. 2007. С. 76.

18. Грачев Е.В., Дядин Ю.А. Разбиение гидратных каркасов на полости II Кристаллография. 2005. Том 50, № 3. С. 563-567.

19. Грачев Е.В., Дядин Ю.А., Липковски Я. Построение сечений кристаллических структур с использованием пакета программ CLAT // Журнал структурной химии. 1995. Том 36, № 5. С. 956-959.

20. Грачев Е.В., Комаров В.Ю. Генерация простых многогранников // Сборник материалов Международной научно-практической конференции «Использование экономико-математических методов в науке, управлении и образовании». Новосибирск. 2009. С. 112-116.

21. Косяков В.И., Шестаков В. А., Грачев Е.В. О проблеме перечисления фазовых диаграмм. // Журнал физической химии. 2009. Том 83, № 8. С. 1427-1432.

22. Попова A.M., Грачев Е.В. Группа автоморфизмов кольца ZS\ // Материалы Международной научной конференции «Современные проблемы математики, информатики и управления». Алматы. 2008. С. 469-470.

23. Komarov V. Yu., Solodovnikov S.F., Grachev E.V., Kosyakov V.l. Phase formation and structure of hight-pressure gas hydrates and modeling of tetrahedral frameworks with uniform polyhedral cavities // Crystallography Reviews. 2007. Vol 13, N 4. P. 257-297,

24. Popova A.M., Grachev E.V. Authomorphisms Group of Ring ZSL2(3) // Algebra and Model Theory 7. Novosibirsk. 2009. P. 96-103.

25. Косяков В.И., Шестаков В.А., Грачев Е.В. Перечисление диаграмм плавкости трехкомпонентных систем с соединениями постоянного состава // Журнал неорганической химии. 2010, том 55, № 4. С. 1-9 (в печати).

Изд. лиц. ИД 04060 от 20.02.2001 Подписано к печати и в свет 8.12. 2009 Формат G0Y84/1G. Бумаги. № 1. Гарнитур» 'Times New Roman". Печать оперативная. Печ. л. 0,9 Уч.-изд. л. 1,0. Тираж 100. Заказ № 40 Учреждение Российской академии наук Институт неорганической химии им. А. В. Николаеве Сибирского отделения РАН Просп. Акад. Лаврентьева, 3, Новосибирск, 630090.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Грачев, Евгений Владимирович

0.1 Введение.

1 Алгоритмы для решения задач по теории групп.

1.1 Генерация группы, заданной порождающими.

1.2 Построение таблицы неприводимых характеров.

1.3 Расчет неприводимых неэквивалентных представлений.

1.4 Группы автоморфизмов точечных кристаллографических групп.

2 Построение группы единиц целочисленного группового кольца конечной группы.

2.1 Группа U(ZA5).

2.1.1 Алгоритм построения группы единиц кольца Z[D{Ab)].

2.1.2 Теорема о вложении группы Л5 в группу V(Z

§).

2.2 Группа U(ZS5).

2.2.1 Алгоритм построения двусторонних идеалов в целочисленном групповом кольце.

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

2.2.3 Алгоритм построения группы единиц кольца Z[D{Sb)\.

2.3 Группа U(ZAg).

2.3.1 Алгоритм построения группы единиц кольца

Z{D{A&)].

2.4 Группа U(ZCp) (р - простое.)

2.4.1 Алгоритм определения обратимых элементов в кольце ZCp.

2.4.2 Алгоритм построения подгруппы конечного индекса в группе V(ZCp).

3 Алгоритмы построения криптосистем на основе целочисленных групповых колец

3.1 Описание криптосистемы.

3.2 Алгоритмы построения криптосистемы на основе кольца ZS3.

4 Алгоритмы для решения задач по кристаллографии

4.1 Генерация простых многогранников.

4.1.1 Кодировка простых гамильтоновых многогранников.

4.2 Разбиение гидратных каркасов на полости.

Введение диссертация по математике, на тему "Алгоритмы компьютерной алгебры в теории групп, кодировании и кристаллографии"

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

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

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

Напомним определение группового кольца. Пусть G - группа, R- кольцо с единицей. Групповое кольцо RG - это множество конечных формальных сумм вида Ylag9i £ R, д £ G с естественно geG определенными операциями

Е <у.дд + £ Рдд = Е(ад+ Рд)д

ZaggEPg9 = £( £ aff3h)g fh=g кТ,схдд=Т,кадд, к 6 R

Изучение групп единиц целочисленных групповых колец неабе-левых групп началось с их описания для конкретных конечных групп как групп, изоморфных некоторым матричным группам. Здесь типичными являются результаты J. Hughers, K.R. Pearson (1973) [26], которые описали группу единиц кольца ZSz следующим образом: Л а eGL2(Z):a + c = b + d( mod3)

U(ZS3) ^ с d

Аналогичное описание получили P.J. Allen, С.Hobby (1980) [18] для кольца ZA±.

U{ZA4) = {±1} х {X <Е SLz{Z) : X = (жу) удовлетворяет условиям (1),(2)},

X = \г '0 1 0х mod 2), г = 0,1,2;

0 0 1 V1 0

Х\2 + Я23 + = ®i3 + ®2i + Ж32 = 0 (mod 4) (2) В работе E.G. Goodaire, Е. Jespers, M.M.Parmenter [23] описаны единицы кольца ZG в случае, когда G - конечная группа, такая, что G/Z{G) = С2 х С2 и G/G' и Z(G) каждая имеют экспоненту 2,3,4 или 6. В статье J. Ritter, S.K. Sehgal [31] описаны порождающие для подгрупп конечного индекса группы единиц целочисленного группового кольца ZG, где G принадлежит некоторому классу конечных групп, и приводят пример такой группы G =< а, 6, с : а4 = [о, Ь] — [а, с] — 15 а2 = Ъ2 = с2 = [6, с] >. В этом же направлении сделана работа Е. Kleinert (1987) [28]. Кроме того, С.P. Milies [29] описал группы единиц целочисленного группового кольца диэдральной группы восьмого порядка ZD4 и доказал, что в ней существуют только 2 несопряженные максимальные подгруппы порядка 8. Наконец, N. Endo находит фундаментальную систему единиц для группы G = Zp х Zp, где р > 5, и строит пример для р = 5 и р = 7 [22].

Как видим, все эти результаты относятся к описанию порождающих групп единиц целочисленных групповых колец конкретных конечных групп. Такая задача и была сформулирована среди различных проблем в монографии S.K. Sehgal (1993) под номером 17: находить представления мультипликативных групп ZG* для конечных групп G [34].

Нужно сказать, что в самом начале исследований групповых колец естественно возникла проблема изоморфизма: следует ли из изоморфизма групповых колец RG\ = RG2 изоморфизм групп Gi = G<p. Впервые эту проблему обсуждал тоже Г. Хигман для случая R = Z [25]. Понятно, что для групп, групповые кольца которых имеют тривиальную группу единиц, ответ положительный, но Г. Хигман доказал, что и для конечных абелевых групп это так. Приведем результаты, относящиеся к случаю целочисленных групповых колец. Так, С.Д. Берман указал некоторые необходимые условия изоморфизма целочисленных групповых колец [4]. D.S. Passman (1965) доказал, что группы порядка р5(р > 3), а также нильпотентные группы класса 2 определяются своим целочисленным групповым кольцом [30], аналогичный результат получен для разрешимых групп класса 2 в работе А.И. Саксонова [16]. Положительный результат для конечных нильпотентных групп получили K.W. Roggenkamp и L. Scot (1986) [32]. Это результаты, относящиеся к частным случаям. Однако в общем случае ответ отрицательный. Например, М. Hertweck (2001) показал, что существуют две неизоморфные конечные группы G\ и (?2, групповые кольца которых ZG\ и ZG-2 изоморфны [24].

В связи с проблемой изоморфизма для произвольных конечных групп G.H. Cliff, S.K. Sehgal и А.К. Weiss (1981) в работе [20] поставили два вопроса:

1) Расщепляемо ли вложение G —> V(ZG)?

2) Если расщепляемо, то существует ли нормальное дополнение без кручения?

Дадим несколько пояснений. Напомним, что V(ZG) = {Zagg е U(ZG) : £aff = 1}

- нормализованная группа единиц кольца ZG. Очевидно, что U(ZG) = {±1} х V(ZG), поэтому часто вместо группы единиц U{ZG) рассматривают нормализованную группу единиц V(ZG). Вложение группы G в группу Н называется расщепляемым, если Я = N\G, где G = G, N<H: Nf)G = {1}, при этом группу N называют нормальным дополнением группы G. В случае положительных ответов на оба вопроса получаем, что G имеет в V{ZG) нормальное дополнение без кручения, а отсюда следует, что всякая конечная подгруппа группы V{ZG) изоморфна подгруппе G, что ведет к решению проблемы изоморфизма для ZG. Теперь понятен интерес к нормальным дополнениям группы G в группе V(ZG).

G.H. Cliff, S.K. Sehgal, А.К. Weiss доказали, что G имеет нормальное дополнение без кручения в V(ZG), если G обладает абеле-вым нормальным делителем А и G/А - абелева, нечетного порядка или экспоненты, делящей 4 или 6.

P. J. Allen и С. Hobby (1987) находят два нормальных дополнения для 5з в V{ZSz)\ одно без кручения, второе содержит элемент порядка 2. Дополнение без кручения является свободной группой ранга 3 [19].

Е. Jespers и G. Leal (1991) описывают метод вычисления группы единиц кольца ZG, где G - конечная 2-группа с условием, что G/Z{G) - четверная группа Клейна [27]. Этот класс групп содержит две группы порядка 8, кватернионов и диэдральную D^, и четыре группы порядка 16.

A. Dooms и Е. Jespers (2003) описывают четыре нормальных дополнения к 5з в V(ZS3), три из которых изоморфны свободной группе ранга 3, а одно содержит периодические элементы [21]. При этом они доказывают, что других нормальных дополнений нет. Отметим в заключение, что в работах Р.Ж. Алеева и его учеников изучены центральные единицы целочисленных групповых колец различных конечных групп.

R.K. Sharma и S. Gangopadhyay (2004) доказали, что в группе V{ZS^) имеется подгруппа конечного индекса без кручения, но оставили открытым вопрос о существовании нормального дополнения без кручения к S4 в группе V(ZS4) [33].

A.M. Попова с соавторами дали положительный ответ на этот вопрос [14].

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

Результаты о строении групп единиц могут быть применены при создании устойчивых криптосистем, являющихся обобщением криптосистемы Эль-Гамаля с открытым ключом и развитых Росошеком (г. Томск) [15]. Например, в работе автора [36] разработаны быстрые алгоритмы для выполнения операций в целочисленном групповом кольце конечной циклической группы.

Перейдем к задачам, возникающим в кристаллографии. Известен широкий класс гидратных соединений включения, в которых молекулы воды на основе водородных связей образуют трехмерный каркас, имеющий полости различного типа. На данный момент известны следующие типы гидратных каркасов: кубические структуры I, II; гексагональные структуры I, II, III; тетрагональные структуры I, II, III; ромбическая структура. Анализ этих структур показал наличие в них полостей D, D', Т, Н, Р и Е -типов. Подробно данные структуры, с описанием имеющихся в них полостей, рассмотрены в работе [6]. В 2001 году была открыта тетрагональная структура IV с ранее неизвестным типом полости [8]. Строение таких каркасов сложное и разбиение каркаса на полости является довольно трудоемким процессом для исследователя. Поскольку процесс получения новых гидратных структур продолжается, перед исследователем постоянно возникает проблема их анализа. В связи с этим для эффективного анализа строения гидратных каркасов были поставлены следующие задачи, решённые автором и опубликованные в указанных работах.

1) Генерация всех простых многогранников с заданным четным числом вершин [42].

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

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

Цели работы.

Целями нашей работы являются:

1) разработать математический аппарат и алгоритмы для описания строения группы V(ZG) для G = Л5, S5, Aq, Ср, где Ср - циклическая группа простого порядка р;

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

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

Методы исследования.

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

Научная новизна.

Практическая ценность.

Структура и объем работы.

Диссертация состоит из введения, четырех глав основного текста. Список литературы состоит из 47 наименований. Работа изложе

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Грачев, Евгений Владимирович, Новосибирск

1. Басс Дж., Милнор Ж., Серр П. Решение конгруэнц-проблемы для Sln(n > 3) и Sp2n(n > 2) // Математика. 1970. Том 14, № 6. С. 64-128.

2. Белоногов В.А., Фомин А.Н. Матричные представления в теории конечных групп. М. 1976. 126 с.

3. Березин И.С., Жидков Н.П. Методы вычислений. М.: Государственное издательство физико-математической литературы. 1959. 620 с.

4. Берман С.Д. О некоторых свойствах целочисленных групповых колец // Доклады АН СССР. 1953. Том 91, № 1. С. 7-9.

5. Берман С.Д., Грушко И.И. К теории обработки дискретных сигналов // Проблемы передачи информации. 1983. Том XIX, Вып. 4. С. 43-49.

6. Дядин Ю.А., Удачин К.А. Клатратные полигидраты пералкилоние-вых солей и их аналогов // Журнал структурной химии. 1987. Том 28, №3. С. 75-116.

7. Жаров О.А., Казарин JI.C. К теории групповой свертки // Проблемы передачи информации. 1993. Том 29, Вып. 3. С. 104-106.

8. Курносов А.В., Манаков А.Ю., Комаров В.Ю., Воронин В.И., Теплых А.Е., Дядин Ю.А. Новая газогидратная структура // Доклады академии наук. 2001. Том 381, № 5. С. 649-651.

9. Кэртис Ч., Райнер И. Теория представлений конечных групп и ассоциативных алгебр. М. 1969. 668 с.

10. Мерзляков Ю.И. Рациональные группы. М. 1980. 464 с.И. Мерзляков Ю.И. Матричные представления свободных групп // ДАН. 1978. Т.238, №3. С.527-583.

11. Попова A.M. Группы обратимых элементов матричных колец // Сиб. матем. журн. 1999. Том 40, № 5, С. 1127-1136.

12. Попова A.M., Порошенко Е.Н. Группы единиц целочисленных групповых колец конечных групп // Algebra and Model Theory 4. Новосибирск. 2003. С. 99-106.

13. Попова A.M., Журков С.В. Обратимые элементы целочисленных групповых колец // Международная алгебраическая конференция. Тезисы докладов. Екатеринбург. 2005. С. 69-70.

14. Росошек С.К. Криптосистемы в группах автоморфизмов групповых колец абелевых групп // Фундаментальная и прикладная математика. М. 2007. Том. 13, № 8. С. 157-164.

15. Саксонов А.И. О некоторых целочисленных кольцах, ассоциированных с конечной группой // Доклады АН СССР. 1966. № 171. С. 529-532.

16. Супруненко Д.А. Группы матриц. М.: Наука, 1972. 351 с.

17. Allen P.J., Hobby С. A Characterization of Units in ZA4. // J. of Algebra. 1980. Vol 66. P. 534-543.

18. Allen P.J., Hobby C. A note on the unit group of ZS3 // Proc. A.M.S. 1987. Vol 99. P. 9-14.

19. Cliff G.H., Sehgal S.K., Weiss A.R. Units of integral Group Rings of Metabelian Groups // J. Algebra. 1981. Vol 73. P. 167-185.

20. Dooms A., Jespers E. Normal Complements of the Trivial Units in the Unit Group of Some Integral Group Rings // Commun. Algebra. 2003. Vol 31, № 1. P. 475-482.

21. Endo N. On the unit group of the group ring ZG. // Tokyo J. Math. 2002. Vol 25, № 2. P. 335-351.

22. Goodaire E.G., Jespers E., Parmenter M.M. Determining units in some integral group rings // Canad Math. Bull. 1990. Vol 33, № 2. P. 242-246.

23. Hertweck M. A. Counter-example to the isomorphism problem for integral group rings // Annals of Mathematics. 2001. Vol 154. P. 115-138.

24. Higman G. The units of group rings // Proc. London Math. Soc. 1940. Vol 46, № 2. P. 231-248.

25. Hughers J., Pearson K.R. The group of units of the integral group ring ZSzll Canad Math. Bull. 1972. Vol 15, № 4. P. 529-534.

26. Jespers E., Leal G. Describing units of integral group rings of some 2-groups // Commun. Algebra. 1991. Vol 19, № 6. P. 1809-1826.

27. Kleinert E. A Theorem on units of integral groups rings //J. Pure Appl. Algebra. 1987. Vol 49, № 1-2. P. 161-171.

28. Milies P.C. The units of the integral groups ring ZD4 // Doc. Soc. Brazil. Math. 1972. № 4. P. 85-92.

29. Passman D.S. Isomorphic groups and group rings // Pacif. J. Math. 1965. Vol 15, № 2. P. 561-583.

30. Ritter Y., Sehgal S.K. Construction of units in integral group rings of finite nilpotent groups // Trans. Amer. Mat. Soc. 1991. № 324.P. 603-621.

31. Roggenkamp K.W., Scott L. The isomorphism problem for integral group rings of finite nilpotent groups // Proceedings of groups. St. Andrews. 1985. P. 291-299.; Cambridge: Cambridge Univ. Press. 1986. (London Math. Soc. Lecture Note Ser. № 121).

32. Sharma R.K., Gangopadhyay S. On congruence subgroups and units in ZS4 // Commun. Algebra. 2004. Vol 32, № 2. P. 663-688.

33. Sehgal S.K. Units in integral group rings. Longman Scientific and Technical Essex. 1993.ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

34. Грачев Е.В., Попова A.M. Единицы целочисленного группового кольца группы // Вестник Красноярского государственного университета. Серия: физ.-мат. науки. 2006. № 4. С. 54-59.

35. Грачев Е.В. Строение группы единиц целочисленного группового кольца циклической группы простого порядка // Algebra and Model Theory 6. Новосибирск. 2007. С. 38-40.

36. Грачев Е.В., Попова A.M. Группа единиц целочисленного группового кольца группы // Абелевы группы. Материалы всероссийского симпозиума. Бийск. 2006. С. 13.

37. Грачев Е.В., Попова A.M. Мультипликативная группа кольца ZAq // Международная конференция «Алгебра и ее приложения». Тезисы докладов. Красноярск. 2007. С. 38-39.

38. Грачев Е.В., Попова A.M., Журков С.В. Некоторые алгоритмические вопросы целочисленных групповых колец // Международная конференция «Теория функций, алгебра и математическая логика». Алматы. 2007. С. 76.

39. Грачев Е.В., Дядин Ю.А. Разбиение гидратных каркасов на полости // Кристаллография. 2005. Том 50, № 3. С. 563-567.

40. Грачев Е.В., Дядин Ю.А., Липковски Я. Построение сечений кристаллических структур с использованием пакета программ CLAT // Журнал структурной химии. 1995. Том 36, № 5. С. 956-959.

41. Грачев Е.В., Комаров В.Ю. Генерация простых многогранников // Сборник материалов Международной научно-практической конференции «Использование экономико-математических методов в науке, управлении и образовании». Новосибирск. 2009. С. 112-116.

42. Косяков В.И., Шестаков В.А., Грачев Е.В. О проблеме перечисления фазовых диаграмм // Журнал физической химии. 2009. Том 83, № 8. С. 1427-1432.

43. Попова A.M., Грачев Е.В. Группа автоморфизмов кольца ZS& // Материалы Международной научной конференции «Современные проблемы математики, информатики и управления». Алматы. 2008. С. 469-470.

44. Popova A.M., Grachev E.V. Authomorphisms Group of Ring ZSX2(3)Algebra and Model Theory 7. Novosibirsk. 2009. P. 96-103.

45. Косяков В.И., Шестаков В.А., Грачев Е.В. Перечисление диаграмм плавкости трехкомпонентных систем с соединениями постоянного состава // Журнал неорганической химии. 2010, том 55, № 4. С. 1-9 (в печати).