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

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

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

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

.

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

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

Е <�у.дд +? Рдд = Е (ад+ Рд) д

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

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

Изучение групп единиц целочисленных групповых колец неабе-левых групп началось с их описания для конкретных конечных групп как групп, изоморфных некоторым матричным группам. Здесь типичными являются результаты 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;

1)

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 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 в группу Н называется расщепляемым, если Я = NG, где G = G, N

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 (в печати).