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

• Автор: Ерофеев, Степан Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Омск
• Количество страниц: 65 с.

Содержание
Введение

Глава 1. О группах унитреугольных автоморфизмов относительно свободных групп

1.1. Введение

1.2. О структуре и матричной представимости групп [/„

1.3. Об оценке длины обратного автоморфизма

Глава 2. Диофантова проблема

2.1. Введение

2.2. Диофантовы множества

2.3. Диофантовость перечислимых множеств

2.4. Диофантово представление показательной функции

2.5. Универсальные диофантовы уравнения
Глава 3. Диофантовы уравнения и односторонние функции
3.1. Односторонние функции. Определения
3.2. Диофантовость дискретного логарифма
3.3. Схемы построения двушагово односторонних функций
3.4. Построение односторонних функций на основе неразрешимости проблемы эндоморфной сводимости в группах
Литература

Введение
Настоящая диссертация посвящена двум основным темам:
1. Исследование структуры и возможности точного представления матрицами (линейности) группы унитреугольных автоморфизмов относительно свободных групп.
2. Построение новых конструкций возможно односторонних функций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах и Диофантовой проблемы.
Группа унитреугольных автоморфизмов. Группам автоморфизмов относительно свободных групп как конечного, так и бесконечного, рангов посвящено немало работ. См., например, обзоры [20, 32, 65].
Обозначим через Тф свободную группу ранга п с базисом Хп = {ац
же обозначим через (?„ относительно свободную группу ранга п некоторого многообразия групп С, через относительно свободную группу бесконечного счетного ранга многообразия С.
Отметим известные результаты о линейности групп автоморфизмов и их подгрупп относительно свободных групп конечного ранга. Почти ниль-потентной называется группа, допускающая нильпотентную подгруппу конечного индекса.
Крамер в работе [50] доказал линейность группы
Форманек и Прочези в работе [39] доказали, что при п > 3 группа АиЛ,Еп не линейна.
Ауслендер и Баумслаг в работе [31] доказали, что группа автоморфизмов любой конечно порожденной почти нильпотентной группы линейна. Более то-

го, голоморф такой группы (значит и ее группа автоморфизмов) допускают точное представление матрицами над кольцом целых чисел 2. Отсюда следует в частности, что группы автоморфизмов относительно свободных групп конечного ранга почти нильпотентных многообразий групп допускают точное представление матрицами.
Ольшанский в работе [61] доказал, что если относительно свободная группа Оп не свободна и не почти нильпотентна, то ее группа автоморфизмов АиЬСп не линейна. В этой же работе отмечалось, что близкие по формулировке результаты содержатся в статьях [10, 15]. Однако, обе эти статьи содержат неточности в формулировках и существенные ошибки в доказательствах.
Заметим также, что группа автоморфизмов АЫСщ для любого нетривиального многообразия С содержит подгруппу, определяемую всеми подстановками бесконечного счетного множества свободных порождающих Уд,, которая изоморфна группе подстановок 5д,. Последняя, как хорошо известно, нелинейна.
Никакие из приведенных работ не дают представление о линейности достаточно естественной подгруппы унитрегольных автоморфизмов.
Новые конструкции возможно односторонних функций. Односторонние (в другой терминологии однонаправленные) функции являются неотъемлемой частью криптографических схем и протоколов. Теоретически их существование при формальном определении до сих пор не установлено. В то же время, односторонние функции являются основным инструментом во многих разделах и приложениях криптографии, в частности, они применяются в электронных подписях, протоколах аутентификации, алгоритмах генерации псевдослучайных последовательностей и т.п. Конечно, используемые с указанной целью функции можно назвать только возможно односторонними.

сел п выполняется неравенство
РгоЪ[Ви(Уп), Г) € Гтп))] < ±
где ип означает случайную величину, равномерно распределенную на {0,1}”.
Заметим, что алгоритму предписан размер его входа. Это объясняется тем, что размер аргумента х может не вычисляться как полиномиальная функция от у. В [40] приводится пример, когда в качестве значения функции /(х) берется |ж|. Заметим, однако, что в данном примере вход х' с условием у = /(х') находится очевидным образом и может быть записан с использованием компрессии полиномиально от у. Это показывает, что определение
3.1.1 возможно нуждается в коррекции. Алгоритмы с компрессионной записью получили в настоящее время существенное развитие в теории вычислений и в теории групп. См. по этому поводу [54, 55, 66].
Определение 3.1.2. Функция / : {0,1}* —> {0,1}* называется слабо односторонней, если выполнены следующие требования.
a) — а) из определения 3.1.1.
b) Существует полином р(-) такой, что для любого вероятностного полиномиального по времени алгоритма В, и всех достаточно больших натуральных чисел п выполняется неравенство
РгоЪ[В{/(ип), 1п) 0 Г1(/((7„))] >
В [40] доказано, что существование слабо односторонней функции влечет существование сильно односторонней функции.
Приведенные определения связаны с бинарным представлением аргументов и значений функции. Для задания возможно односторонней функции,