Une implémentation des morphismes $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$

Informations fondamentales

• Identifiant de l'article : 2510.14569
• Titre : An implementation of the morphisms $SL_2(\mathbb{F}) \rightarrow SL_2(\mathsf{K}) \rightarrow \mathsf{X}$
• Auteurs : Alexandre Borovik, Şükrü Yalçınkaya
• Classification : math.GR (Théorie des groupes)
• Date de publication : 16 octobre 2025
• Lien de l'article : https://arxiv.org/abs/2510.14569

Résumé

Cet article explique brièvement comment implémenter les morphismes présentés dans l'article « Natural representations of black box groups encrypting $SL_2(\mathbb{F})$ » et fournit plusieurs exemples concrets. Les auteurs proposent une implémentation complète en GAP, disponible sur GitHub.

Contexte et motivation de la recherche

Contexte du problème

L'article traite du problème fondamental de la construction et de l'implémentation des morphismes de groupes boîte noire : $SL_2(F) \rightarrow SL_2(K) \rightarrow X$

où :

• $SL_2(F)$ est le groupe des matrices $2 \times 2$ de déterminant 1 sur un corps premier fini $F$ (de caractéristique impaire)
• $X$ est un groupe boîte noire chiffrant $SL_2(F)$
• $SL_2(K)$ est le groupe des matrices $2 \times 2$ de déterminant 1 sur un corps boîte noire $K$ (chiffrant $F$)

Signification de la recherche

1. Applications pratiques de la théorie computationnelle des groupes : Les algorithmes de groupes boîte noire revêtent une importance capitale en cryptographie et en théorie de la complexité computationnelle
2. Transition de la théorie à la pratique : Transformation des constructions abstraites de théorie des groupes en algorithmes exécutables
3. Calcul efficace sur les grands corps : Optimisation particulière pour les groupes sur des corps finis extrêmement grands

Défis techniques

• Traitement de groupes boîte noire de structure inconnue
• Construction d'opérations de corps sans connaître la structure du corps
• Implémentation d'algorithmes de constructions de théorie des groupes complexes

Contributions principales

1. Fourniture d'une implémentation GAP complète : Transformation des algorithmes théoriques en code exécutable
2. Construction d'une implémentation boîte noire de $PGL_2$ : Via plongement diagonal et produit semi-direct
3. Implémentation du calcul explicite des morphismes : Incluant la décomposition d'éléments et la construction de mappages
4. Fourniture d'un cadre de vérification : Vérification de la correction via comparaison d'ordres et relations de commutation de Chevalley

Détails méthodologiques

Définition de la tâche

Étant donné un groupe boîte noire $X \cong SL_2(F)$, où $F$ est un corps premier fini inconnu, construire les morphismes explicites :

• $SL_2(F) \rightarrow SL_2(K)$ : du groupe connu au groupe sur le corps boîte noire
• $SL_2(K) \rightarrow X$ : du groupe sur le corps boîte noire au groupe boîte noire original

Architecture de l'algorithme principal

1. Construction de $PGL_2$

La construction de $PGL_2(F)$ s'effectue selon les étapes suivantes :

1. Construction du tore : Construction de deux tores $S$ et $R$ dans $X$, où l'automorphisme diagonal $\alpha$ centralise $S$ et inverse $R$
2. Plongement diagonal : Définition de $\tilde{X} = \{(x, x^\alpha) | x \in X\}$
3. Produit semi-direct : Construction de $Y = \tilde{X} \rtimes \langle \alpha \rangle \cong PGL_2(F)$

2. Représentation des éléments du groupe

Les éléments de $Y$ se représentent comme :

• $(x, x^\alpha, 0)$ : appartenant à la classe latérale $\tilde{X}$
• $(x, x^\alpha, 1)$ : appartenant à la classe latérale $\tilde{X}\alpha$

Règles de multiplication du groupe :

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

Points d'innovation technique

1. Construction de corps boîte noire : Construction d'opérations de corps par des méthodes de théorie des groupes sans connaître la structure du corps
2. Matrices de changement de base : Implémentation de la transformation de $SO_3^♯$ vers $SO_3^♭$
3. Algorithme de décomposition d'éléments : Décomposition de matrices $2 \times 2$ en produits d'éléments unipotents

Configuration expérimentale

Environnement de test

• Système de calcul : GAP (Groups, Algorithms, Programming)
• Groupes testés : $SL_2(997)$ (997 est un nombre premier)
• Restriction sur la taille du corps : L'algorithme exige que la taille du corps de base soit au moins 13

Interfaces des fonctions principales

1. SetUpForPGL2("S", "Eo")
   • Entrée : ensemble générateur S et partie impaire de l'exposant Eo
   • Sortie : tous les outils nécessaires pour la construction de $PGL_2$
2. ToolBoxSL2("S", "E")
   • Entrée : ensemble générateur S et exposant arbitraire E
   • Sortie : liste de boîte à outils contenant 12 éléments
3. SharpVsFlat("TB")
   • Entrée : sortie de ToolBoxSL2
   • Sortie : matrice de changement de base

Méthodes de vérification

• Comparaison d'ordres : Vérification que l'élément original et son image ont le même ordre
• Relations de commutation de Chevalley : Vérification que les générateurs de Chevalley satisfont les relations de commutation correctes

Résultats expérimentaux

Résultats principaux

L'article présente des exemples concrets d'exécution :

1. Exemples de mappage d'éléments :
   • Entrée : éléments aléatoires dans $SL_2(997)$
   • Sortie : leur image dans le groupe boîte noire $X$
   • Vérification : les deux possèdent le même ordre
2. Efficacité de l'algorithme : L'algorithme peut traiter des groupes sur de grands corps, mais certaines étapes (comme le calcul de racines carrées) peuvent nécessiter un temps considérable

Découvertes expérimentales

1. Vérification de la correction : Tests sur plusieurs éléments aléatoires vérifiant la correction du morphisme
2. Complexité computationnelle : La construction de la matrice de changement de base implique le calcul de racines carrées d'éléments de corps boîte noire, pouvant être chronophage en cas de choix aléatoire inadéquat
3. Scalabilité : L'algorithme est conçu pour traiter des corps finis extrêmement grands

Travaux connexes

Fondements théoriques

Cette implémentation s'appuie sur les travaux théoriques antérieurs des auteurs :

1. 1 Borovik & Yalçınkaya (2018) : Représentations adjointes de groupes boîte noire $PSL_2(F_q)$
2. 2 Borovik & Yalçınkaya : Représentations naturelles de groupes boîte noire chiffrant $SL_2(F)$

Méthodes techniques

• Utilisation de la géométrie projective et de la théorie des actions de groupes
• Adoption des méthodes de construction standard des groupes de Chevalley
• Intégration des techniques modernes de théorie computationnelle des groupes

Conclusions et discussion

Conclusions principales

1. Implémentation réussie d'algorithmes théoriques : Transformation de constructions de théorie des groupes complexes en outils computationnels pratiques
2. Efficacité du cadre de vérification : Vérification de la correction de l'algorithme via comparaison d'ordres et relations de commutation
3. Faisabilité du calcul sur les grands corps : L'algorithme peut traiter les corps finis de grande taille rencontrés dans les applications pratiques

Limitations

1. Restriction sur la taille du corps : Exigence que la taille du corps de base soit au moins 13
2. Efficacité computationnelle : Certaines étapes peuvent être chronophages en raison du caractère aléatoire
3. Restriction aux corps premiers : L'implémentation actuelle ne supporte que les corps premiers, pas les extensions de corps finis

Directions futures

1. Implémentation des morphismes inverses : Les auteurs s'engagent à publier l'implémentation des morphismes inverses
2. Support des extensions de corps : Extension de l'algorithme pour supporter les extensions de corps finis
3. Optimisation de l'efficacité : Amélioration des algorithmes aléatoires pour réduire le temps de calcul

Évaluation approfondie

Avantages

1. Intégration théorie-pratique : Transformation réussie de résultats abstraits de théorie des groupes en code exécutable
2. Contribution open source : Fourniture d'un dépôt GitHub complet facilitant la reproduction et l'extension
3. Documentation détaillée : Instructions d'utilisation claires et exemples concrets
4. Vérification complète : Vérification de la correction de l'algorithme par plusieurs méthodes

Insuffisances

1. Concision de la documentation : En tant que rapport d'implémentation, l'introduction du contexte théorique est relativement brève
2. Analyse de performance absente : Manque d'analyse détaillée de la complexité temporelle
3. Couverture de tests limitée : Présentation d'un nombre limité de cas de test

Impact

1. Domaine de la théorie computationnelle des groupes : Fourniture d'outils pratiques pour les algorithmes de groupes boîte noire
2. Applications cryptographiques : Valeur d'application potentielle dans les systèmes cryptographiques basés sur les groupes
3. Valeur pédagogique : Fourniture d'exemples concrets pour l'enseignement et la recherche en théorie computationnelle des groupes

Scénarios d'application

• Calculs de groupes sur les grands corps finis
• Analyse de structure de groupes boîte noire
• Implémentation de protocoles cryptographiques basés sur la théorie des groupes
• Enseignement et recherche en théorie computationnelle des groupes

Références bibliographiques

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.

Note technique : Cet article est un rapport technique de nature implémentatoire, mettant l'accent sur la transformation d'algorithmes théoriques en outils pratiques. Bien que relativement concis, il fournit une implémentation de code complète et un guide d'utilisation, revêtant une importance pratique considérable pour le domaine de la théorie computationnelle des groupes.