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

• Автор: Грачев, Евгений Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 110 с. : ил.

Оглавление

0.1 Введение

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

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

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

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

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

2 Построение группы единиц целочисленного группового

кольца конечной группы

2.1 Группа иА$)

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

г[о(А5)
2.1.2 Теорема о вложении группы А5 в группу V(2А5)
2.2 Группа
2.2.1 Алгоритм построения двусторонних идеалов в целочисленном групповом кольце
2.2.2 Алгоритм построения централизатора матричной подгруппы в матричном кольце
2.2.3 Алгоритм построения группы единиц кольца
£[£(55)]

2.3 Группа иАц)
2.3.1 Алгоритм построения группы единиц кольца гЩАб)}
2.4 Группа иСр) (р - простое.)
2.4.1 Алгоритм определения обратимых элементов в кольце 2Ср
2.4.2 Алгоритм построения подгруппы конечного индекса в группе V (ЯСр)
3 Алгоритмы построения криптосистем на основе целочислен-
ных групповых колец
3.1 Описание криптосистемы
3.2 Алгоритмы построения криптосистемы на основе кольца

4 Алгоритмы для решения задач по кристаллографии
4.1 Генерация простых многогранников
4.1.1 Кодировка простых гамильтоновых многогранников
4.2 Разбиение гидратных каркасов на полости
Литература
Публикации автора по теме диссертации

0.1 Введение
В предлагаемой работе с помощью методов компьютерной алгебры исследуются проблемы теории групп, криптографии и кристаллографии. В теории групп методы компьютерной алгебры были применены к изучению строения мультипликативной структуры групповых колец конечных групп малого порядка. Они использованы далее в изучении криптографической проблемы построения защищенных систем связи, основанных на строении конечных групповых колец. Кроме того, в кристаллографии диссертантом были получены новые подходы к изучению строения гидратных каркасов.
Возникающие задачи можно разбить на три класса. К первому относятся задачи, относящиеся к строению конечно порожденных групп, ко второму - задачи построения групп единиц целочисленных групповых колец конечных групп и построения на их основе криптосистем, к третьему - задачи, возникающие в кристаллографии.
Актуальность темы.
Вначале остановимся на групповых кольцах.
Напомним определение группового кольца. Пусть С - группа, В- кольцо с единицей. Групповое кольцо ВС - это множество конечных формальных сумм вида д, а,, £ В, д £ С с естественно

определенными операциями
Е ыдд + Е Рд9 = Е (ад + (5д)д Е ®дд Е 9дд = Е( Е <У/Рп)д

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

зовем полурасклеивающнм числом ненулевое натуральное число к{, для которого йгад(0,
В группе V(Z[D(A5)]) содержится нормальная подгруппа
Ко — {Мад{ 1, Кег(р2, (Кепро), *, *),
где 1— изоморфизм колец Z[T2(A)] и ZГz{A)].
Мы получили некоторый инвариантный ряд группы
у&щм)])'
М(£[Р(А5)]) >К2>В. (2.2)
Обозначим через В такую подгруппу 7(А[/)(А5)]), все элементы которой в первых четырёх клетках имеют единичные матрицы. Так как в матрице (*) на диагонали клетки 16 х 16 стоят числа по модулю равные только 1 и 5, то аналогично предыдущему, получаем, что в группе V([И(Л5)]) содержится нормальная подгруппа К5 = {<Ыад{1,1,1, Кепр5, *)}.
И, наконец, по диагонали клетки 25 X 25 матрицы (*) стоят числа, НОК которых равно 12, откуда следует, что в У[Б{Аь)) содержится нормальная подгруппа Км — {с1гад(1,1,1,1, Кепрм)}-После этого ряд (2.2) можно продолжить:
У(г[0{Аъ)}) > Ко О В > К5 >Ву> К12 (2.3)
Для выяснения строения группы единиц рассмотрим факторы ряда (2.3). Из сказанного выше следует, что для изучения первого фактора ряда (2.3) нужно найти все такие линейные комбинации ви-

да е + <% € {0,1}, у которых верхние клетки размера 3x3

обратимы. Было установлено, что таких линейных комбинаций 2880.