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 교환 관계를 통한 정확성 검증

방법론 상세 설명

작업 정의

미지의 유한 소수체 $F$ 에 대해 $X \cong SL_2(F)$ 인 블랙박스 군이 주어졌을 때, 다음의 명시적 태사를 구성한다:

$SL_2(F) \rightarrow SL_2(K)$ : 알려진 군에서 블랙박스 체상의 군으로
$SL_2(K) \rightarrow X$ : 블랙박스 체상의 군에서 원래 블랙박스 군으로

핵심 알고리즘 구조

1. $PGL_2$ 구성

먼저 다음 단계를 통해 $PGL_2(F)$ 를 구성한다:

환면 구성: $X$ 에서 두 개의 환면 $S$ 와 $R$ 을 구성하며, 대각 자기동형 $\alpha$ 는 $S$ 를 중심화하고 $R$ 을 반전시킨다
대각 임베딩: 다음을 정의한다 $\tilde{X} = \{(x, x^\alpha) | x \in X\}$
반직곱: $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)$

기술적 혁신점

블랙박스 체의 구성: 체의 구조를 모르는 상태에서 군론적 방법을 통해 체 연산 구성
기저 변환 행렬: $SO_3^♯$ 에서 $SO_3^♭$ 로의 변환 구현
원소 분해 알고리즘: $2 \times 2$ 행렬을 멱영 원소의 곱으로 분해

실험 설정

테스트 환경

계산 시스템: GAP (Groups, Algorithms, Programming)
테스트 군: $SL_2(997)$ (997은 소수)
체 크기 제한: 알고리즘은 기저 체의 크기가 최소 13 이상을 요구

주요 함수 인터페이스

SetUpForPGL2("S", "Eo")
- 입력: 생성 집합 S 및 지수의 홀수 부분 Eo
- 출력: $PGL_2$ 구성에 필요한 모든 도구
ToolBoxSL2("S", "E")
- 입력: 생성 집합 S 및 임의의 지수 E
- 출력: 12개 항목을 포함하는 도구 상자 리스트
SharpVsFlat("TB")
- 입력: ToolBoxSL2의 출력
- 출력: 기저 변환 행렬

검증 방법

위수 비교: 원래 원소와 그 상의 위수가 동일함을 검증
Chevalley 교환 관계: Chevalley 생성원이 올바른 교환 관계를 만족함을 검증

실험 결과

주요 결과

논문은 구체적인 실행 예시를 제시한다:

원소 매핑 예시:
- 입력: $SL_2(997)$ 의 임의 원소
- 출력: 블랙박스 군 $X$ 에서의 상
- 검증: 두 원소는 동일한 위수를 가짐
알고리즘 효율성: 알고리즘은 대규모 체상의 군을 처리할 수 있으나, 일부 단계(예: 제곱근 계산)는 상당한 시간이 소요될 수 있음