2025-11-21T04:07:15.365796

An implementation of the morphisms $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$

Borovik, YalÃ§Ä±nkaya

We briefly explain how to implement the morphisms in our paper ``Natural representations of black box groups encrypting $SL_2(\mathbb{F})$" and provide some examples.

academic

射 $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$ の実装

基本情報

論文ID: 2510.14569
タイトル: An implementation of the morphisms $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$
著者: Alexandre Borovik、Şükrü Yalçınkaya
分類: math.GR（群論）
発表日時: 2025年10月16日
論文リンク: https://arxiv.org/abs/2510.14569

要約

本論文は、論文「Natural representations of black box groups encrypting $SL_2(\mathbb{F})$ 」における射の実装方法を簡潔に説明し、いくつかの具体例を提供するものである。著者は完全なGAP実装コードを提供しており、GitHubで入手可能である。

研究背景と動機

問題背景

本論文が扱う中核的な問題は、ブラックボックス群の射の構成と実装である： $SL_2(F) \rightarrow SL_2(K) \rightarrow X$

ここで：

$SL_2(F)$ は有限素体 $F$ （奇標数）上の行列式が1である $2 \times 2$ 行列群
$X$ は $SL_2(F)$ を暗号化したブラックボックス群
$SL_2(K)$ はブラックボックス体 $K$ （ $F$ を暗号化）上の行列式が1である $2 \times 2$ 行列群

研究の意義

計算群論の実践的応用：ブラックボックス群アルゴリズムは暗号学および計算複雑性理論において重要な意義を持つ
理論から実践への転換：抽象的な群論構成を実行可能なアルゴリズムに変換する
大体上の効率的計算：特に非常に大きな有限体上の群に対する最適化

技術的課題

未知の構造を持つブラックボックス群の処理
体の構造を知らない場合の体演算の構成
複雑な群論構成アルゴリズムの実装

中核的貢献

完全なGAP実装の提供：理論的アルゴリズムを実行可能なコードに変換
$PGL_2$ のブラックボックス実装の構築：対角埋め込みと半直積を通じた構成
射の具体的計算の実装：元素分解と写像構成を含む
検証フレームワークの提供：位数の比較とChevalley交換関係による正確性検証

方法の詳細

タスク定義

ブラックボックス群 $X \cong SL_2(F)$ が与えられたとき（ $F$ は未知の有限素体）、以下の明示的な射を構成する：

$SL_2(F) \rightarrow SL_2(K)$ ：既知の群からブラックボックス体上の群へ
$SL_2(K) \rightarrow X$ ：ブラックボックス体上の群から元のブラックボックス群へ

中核的アルゴリズム構造

1. $PGL_2$ の構成

まず $PGL_2(F)$ を以下の手順で構成する：

トーラスの構成： $X$ 内に2つのトーラス $S$ と $R$ を構成する。ここで対角自己同型 $\alpha$ は $S$ を中心化し $R$ を反転する
対角埋め込み：以下を定義する $\tilde{X} = \{(x, x^\alpha) | x \in X\}$
半直積： $Y = \tilde{X} \rtimes \langle \alpha \rangle \cong PGL_2(F)$ を構成する