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

Basic Information

• Paper ID: 2510.14569
• Title: An implementation of the morphisms $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$
• Authors: Alexandre Borovik, Şükrü Yalçınkaya
• Classification: math.GR (Group Theory)
• Publication Date: October 16, 2025
• Paper Link: https://arxiv.org/abs/2510.14569

Abstract

This paper briefly explains how to implement the morphisms from the paper "Natural representations of black box groups encrypting $SL_2(\mathbb{F})$" and provides several concrete examples. The authors provide a complete GAP implementation code, available on GitHub.

Research Background and Motivation

Problem Background

The core problem addressed in this paper is the construction and implementation of morphisms of black box groups: $SL_2(F) \rightarrow SL_2(K) \rightarrow X$

where:

• $SL_2(F)$ is the group of $2 \times 2$ matrices with determinant 1 over a finite prime field $F$ (odd characteristic)
• $X$ is a black box group encrypting $SL_2(F)$
• $SL_2(K)$ is the group of $2 \times 2$ matrices with determinant 1 over a black box field $K$ (encrypting $F$)

Research Significance

1. Practical applications in computational group theory: Black box group algorithms have important implications in cryptography and computational complexity theory
2. Theory-to-practice conversion: Translating abstract group-theoretic constructions into executable algorithms
3. Efficient computation over large fields: Optimization specifically for groups over very large finite fields

Technical Challenges

• Handling black box groups with unknown structure
• Constructing field operations without knowledge of the field structure
• Implementing complex group-theoretic construction algorithms

Core Contributions

1. Complete GAP implementation: Converting theoretical algorithms into runnable code
2. Black box implementation of $PGL_2$: Construction via diagonal embedding and semidirect product
3. Concrete computation of morphisms: Including element decomposition and map construction
4. Verification framework: Verifying correctness through order comparison and Chevalley commutation relations

Methodology in Detail

Task Definition

Given a black box group $X \cong SL_2(F)$, where $F$ is an unknown finite prime field, construct explicit morphisms:

• $SL_2(F) \rightarrow SL_2(K)$: from a known group to a group over a black box field
• $SL_2(K) \rightarrow X$: from a group over a black box field to the original black box group

Core Algorithm Architecture

1. Construction of $PGL_2$

First, construct $PGL_2(F)$ through the following steps:

1. Torus construction: Construct two tori $S$ and $R$ in $X$, where a diagonal automorphism $\alpha$ centralizes $S$ and inverts $R$
2. Diagonal embedding: Define $\tilde{X} = \{(x, x^\alpha) | x \in X\}$
3. Semidirect product: Construct $Y = \tilde{X} \rtimes \langle \alpha \rangle \cong PGL_2(F)$

2. Group Element Representation

Elements in $Y$ are represented as:

• $(x, x^\alpha, 0)$: belonging to the coset $\tilde{X}$
• $(x, x^\alpha, 1)$: belonging to the coset $\tilde{X}\alpha$

Group multiplication rules:

• $(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)$

Technical Innovations

1. Black box field construction: Constructing field operations through group-theoretic methods without knowledge of the field structure
2. Change of basis matrices: Implementing transformation from $SO_3^♯$ to $SO_3^♭$
3. Element decomposition algorithm: Decomposing $2 \times 2$ matrices into products of unipotent elements

Experimental Setup

Test Environment

• Computing system: GAP (Groups, Algorithms, Programming)
• Test group: $SL_2(997)$ (997 is prime)
• Field size constraint: The algorithm requires the base field size to be at least 13

Main Function Interfaces

1. SetUpForPGL2("S", "Eo")
   • Input: Generator set S and odd part of exponent Eo
   • Output: All tools necessary for constructing $PGL_2$
2. ToolBoxSL2("S", "E")
   • Input: Generator set S and arbitrary exponent E
   • Output: Toolbox list containing 12 items
3. SharpVsFlat("TB")
   • Input: Output of ToolBoxSL2
   • Output: Change of basis matrix

Verification Methods

• Order comparison: Verifying that the original element and its image have the same order
• Chevalley commutation relations: Verifying that Chevalley generators satisfy the correct commutation relations

Experimental Results

Main Results

The paper demonstrates concrete execution examples:

1. Element mapping examples:
   • Input: Random elements in $SL_2(997)$
   • Output: Their images in the black box group $X$
   • Verification: Both have the same order
2. Algorithm efficiency: The algorithm can handle groups over large fields, but certain steps (such as square root computation) may require considerable time

Experimental Findings

1. Correctness verification: Testing with multiple random elements verifies the correctness of the mapping
2. Computational complexity: Construction of the change of basis matrix involves square root computation of black box field elements, which may be time-consuming due to poor random choices
3. Scalability: The algorithm is designed to handle very large finite fields

Related Work

Theoretical Foundation

This implementation is based on the authors' previous theoretical work:

1. 1 Borovik & Yalçınkaya (2018): Adjoint representations of black box groups PSL₂(Fq)
2. 2 Borovik & Yalçınkaya: Natural representations of black box groups encrypting SL₂(F)

Technical Methods

• Utilizing projective geometry and group action theory
• Employing standard construction methods for Chevalley groups
• Combining modern techniques in computational group theory

Conclusions and Discussion

Main Conclusions

1. Successful implementation of theoretical algorithms: Converting complex group-theoretic constructions into practical computational tools
2. Effectiveness of verification framework: Algorithm correctness verified through order comparison and commutation relations
3. Feasibility of large field computation: The algorithm can handle large finite fields in practical applications

Limitations

1. Field size constraint: Requires base field size to be at least 13
2. Computational efficiency: Certain steps may be time-consuming due to randomness
3. Prime field limitation: Current implementation supports only prime fields, not field extensions

Future Directions

1. Implementation of inverse morphisms: Authors promise to release implementation of inverse morphisms
2. Extension field support: Extending the algorithm to support finite field extensions
3. Efficiency optimization: Improving randomized algorithms to reduce computation time

In-Depth Evaluation

Strengths

1. Theory-practice integration: Successfully converting abstract group-theoretic results into executable code
2. Open source contribution: Providing complete GitHub code repository for reproducibility and extension
3. Detailed documentation: Clear usage instructions and examples provided
4. Comprehensive verification: Algorithm correctness verified through multiple methods

Weaknesses

1. Documentation conciseness: As an implementation note, theoretical background introduction is relatively brief
2. Missing performance analysis: Lacks detailed time complexity analysis
3. Limited test coverage: Only limited test cases are demonstrated

Impact

1. Computational group theory field: Providing practical tools for black box group algorithms
2. Cryptographic applications: Potential applications in group-based cryptographic systems
3. Educational value: Providing concrete examples for learning computational group theory

Applicable Scenarios

• Group computation over large finite fields
• Structural analysis of black box groups
• Group-theoretic implementation of cryptographic protocols
• Teaching and research in computational group theory

References

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.

Technical Note: This paper is a technical report of implementation nature, focusing on converting theoretical algorithms into practical tools. Although relatively brief, it provides complete code implementation and usage guidelines, offering significant practical value to the computational group theory field.