Реализация морфизмов $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$

Основная информация

• ID статьи: 2510.14569
• Название: Реализация морфизмов $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$
• Авторы: Александр Боровик, Шюкрю Ялчинкая
• Классификация: math.GR (теория групп)
• Дата публикации: 16 октября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2510.14569

Аннотация

В данной работе кратко объясняется, как реализовать морфизмы из статьи "Естественные представления чёрных ящиков групп, шифрующих $SL_2(\mathbb{F})$", и приводятся некоторые примеры. Авторы предоставляют полную реализацию на языке GAP, доступную на GitHub.

Исследовательский контекст и мотивация

Постановка проблемы

Основная проблема, рассматриваемая в работе, заключается в конструировании и реализации морфизмов чёрных ящиков групп: $SL_2(F) \rightarrow SL_2(K) \rightarrow X$

где:

• $SL_2(F)$ — группа матриц размера $2 \times 2$ с определителем 1 над конечным простым полем $F$ (нечётной характеристики)
• $X$ — чёрный ящик группы, шифрующей $SL_2(F)$
• $SL_2(K)$ — группа матриц размера $2 \times 2$ с определителем 1 над чёрным ящиком поля $K$ (шифрующим $F$)

Научная значимость

1. Практическое применение в вычислительной теории групп: алгоритмы чёрных ящиков групп имеют важное значение в криптографии и теории вычислительной сложности
2. Трансформация теории в практику: преобразование абстрактных групповых конструкций в исполняемые алгоритмы
3. Эффективные вычисления над большими полями: оптимизация для групп над очень большими конечными полями

Технические вызовы

• Работа с чёрными ящиками групп неизвестной структуры
• Конструирование операций поля без знания его структуры
• Реализация сложных групповых конструкций

Основные вклады

1. Полная реализация на GAP: преобразование теоретических алгоритмов в исполняемый код
2. Конструирование чёрного ящика $PGL_2$: через диагональное вложение и полупрямое произведение
3. Реализация явных вычислений морфизмов: включая разложение элементов и конструирование отображений
4. Разработка фреймворка верификации: через сравнение порядков и проверку соотношений Шевалле

Детальное описание методов

Определение задачи

Дана чёрная ящик группа $X \cong SL_2(F)$, где $F$ — неизвестное конечное простое поле. Требуется конструировать явные морфизмы:

• $SL_2(F) \rightarrow SL_2(K)$: из известной группы в группу над чёрным ящиком поля
• $SL_2(K) \rightarrow X$: из группы над чёрным ящиком поля в исходную чёрную ящик группу

Архитектура основного алгоритма

1. Конструирование $PGL_2$

Сначала конструируется $PGL_2(F)$ следующим образом:

1. Конструирование тора: в $X$ конструируются два тора $S$ и $R$, где диагональный автоморфизм $\alpha$ централизует $S$ и инвертирует $R$
2. Диагональное вложение: определяется $\tilde{X} = \{(x, x^\alpha) | x \in X\}$
3. Полупрямое произведение: конструируется $Y = \tilde{X} \rtimes \langle \alpha \rangle \cong PGL_2(F)$

2. Представление элементов группы

Элементы в $Y$ представляются как:

• $(x, x^\alpha, 0)$: принадлежащие смежному классу $\tilde{X}$
• $(x, x^\alpha, 1)$: принадлежащие смежному классу $\tilde{X}\alpha$

Правила группового умножения:

• $(x, x^\alpha, 0) \circ (y, y^\alpha, 0) = (xy, x^\alpha y^\alpha, 0)$
• $(x, x^\alpha, 0) \circ (y, y^\alpha, 1) = (xy, x^\alpha y^\alpha, 1)$
• $(x, x^\alpha, 1) \circ (y, y^\alpha, 0) = (xy^\alpha, x^\alpha y, 1)$
• $(x, x^\alpha, 1) \circ (y, y^\alpha, 1) = (xy^\alpha, x^\alpha y, 0)$

Технические инновации

1. Конструирование чёрного ящика поля: построение операций поля методами теории групп без знания структуры поля
2. Матрицы замены базиса: реализация преобразования из $SO_3^♯$ в $SO_3^♭$
3. Алгоритмы разложения элементов: разложение матриц размера $2 \times 2$ в произведение унипотентных элементов

Экспериментальная установка

Окружение тестирования

• Вычислительная система: GAP (Groups, Algorithms, Programming)
• Тестовая группа: $SL_2(997)$ (997 — простое число)
• Ограничение на размер поля: алгоритм требует размер базового поля не менее 13

Основные интерфейсы функций

1. SetUpForPGL2("S", "Eo")
   • Входные данные: порождающее множество S и нечётная часть показателя Eo
   • Выходные данные: все необходимые инструменты для конструирования $PGL_2$
2. ToolBoxSL2("S", "E")
   • Входные данные: порождающее множество S и произвольный показатель E
   • Выходные данные: список инструментов из 12 элементов
3. SharpVsFlat("TB")
   • Входные данные: выходные данные ToolBoxSL2
   • Выходные данные: матрица замены базиса

Методы верификации

• Сравнение порядков: проверка совпадения порядков исходного элемента и его образа
• Соотношения Шевалле: проверка выполнения правильных коммутационных соотношений для образующих Шевалле

Экспериментальные результаты

Основные результаты

Работа демонстрирует конкретные примеры выполнения:

1. Примеры отображения элементов:
   • Входные данные: случайный элемент из $SL_2(997)$
   • Выходные данные: его образ в чёрной ящик группе $X$
   • Верификация: оба элемента имеют одинаковый порядок
2. Эффективность алгоритма: алгоритм способен обрабатывать группы над большими полями, однако некоторые этапы (например, вычисление квадратных корней) могут требовать значительного времени

Экспериментальные выводы

1. Верификация корректности: тестирование на множестве случайных элементов подтверждает правильность отображения
2. Вычислительная сложность: конструирование матрицы замены базиса включает вычисление квадратных корней элементов чёрного ящика поля, что может быть затратным при неудачном случайном выборе
3. Масштабируемость: алгоритм разработан для работы с очень большими конечными полями

Связанные работы

Теоретическая база

Данная реализация основана на предыдущих теоретических работах авторов:

1. 1 Боровик и Ялчинкая (2018): присоединённые представления чёрных ящиков групп $PSL_2(F_q)$
2. 2 Боровик и Ялчинкая: естественные представления чёрных ящиков групп, шифрующих $SL_2(F)$

Технические методы

• Использование проективной геометрии и теории групповых действий
• Применение стандартных методов конструирования групп Шевалле
• Интеграция современных методов вычислительной теории групп

Заключение и обсуждение

Основные выводы

1. Успешная реализация теоретических алгоритмов: преобразование сложных групповых конструкций в практические вычислительные инструменты
2. Эффективность фреймворка верификации: проверка корректности алгоритма через сравнение порядков и коммутационные соотношения
3. Осуществимость вычислений над большими полями: алгоритм способен работать с большими конечными полями в практических приложениях

Ограничения

1. Ограничение на размер поля: требуется размер базового поля не менее 13
2. Вычислительная эффективность: некоторые этапы могут быть затратными из-за случайности
3. Ограничение на простые поля: текущая реализация поддерживает только простые поля, не поддерживает расширения конечных полей

Направления будущих исследований

1. Реализация обратных морфизмов: авторы обещают выпустить реализацию обратных морфизмов
2. Поддержка расширений полей: расширение алгоритма для поддержки расширений конечных полей
3. Оптимизация эффективности: улучшение вероятностных алгоритмов для сокращения времени вычислений

Глубокая оценка

Преимущества

1. Интеграция теории и практики: успешное преобразование абстрактных групповых результатов в исполняемый код
2. Открытый исходный код: предоставление полного репозитория на GitHub для воспроизведения и расширения
3. Подробная документация: ясные инструкции по использованию и примеры
4. Тщательная верификация: проверка корректности алгоритма несколькими методами

Недостатки

1. Краткость документации: как описание реализации, работа содержит относительно краткое введение в теоретический фон
2. Отсутствие анализа производительности: недостаток детального анализа временной сложности
3. Ограниченное покрытие тестами: демонстрация ограниченного числа тестовых случаев

Влияние

1. Область вычислительной теории групп: предоставление практических инструментов для алгоритмов чёрных ящиков групп
2. Приложения в криптографии: потенциальное применение в криптосистемах на основе групп
3. Образовательная ценность: предоставление конкретных примеров для изучения вычислительной теории групп

Области применения

• Вычисления групп над большими конечными полями
• Анализ структуры чёрных ящиков групп
• Реализация групповых протоколов в криптографии
• Обучение и исследования в области вычислительной теории групп

Библиография

1 Alexandre Borovik and Şükrü Yalçınkaya, Adjoint representations of black box groups PSL₂(Fq), J. Algebra 506 (2018), 540–591.

2 Alexandre Borovik and Şükrü Yalçınkaya, Natural representations of black box groups encrypting SL₂(F), arxiv.org/abs/2001.10292.

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