Adjoint representations of black box groups ${\mathrm{PSL}}_2({\mathbb{F}}_q)$

Abstract

Given a black box group $\mathsf{Y}$ encrypting ${\mathrm{PSL}}_2(\mathbb{F})$ over an unknown field $\mathbb{F}$ of unknown odd characteristic $p$ and a global exponent $E$ for $\mathsf{Y}$ (that is, an integer $E$ such that ${\mathsf{y}}^E=1$ for all $\mathsf{y}\in \mathsf{Y}$), we present a Las Vegas algorithm which constructs a unipotent element in $\mathsf{Y}$. The running time of our algorithm is polynomial in $\log E$. This answers the question posed by Babai and Beals in 1999. We also find the characteristic of the underlying field in time polynomial in $\log E$ and linear in $p$. Furthermore, we construct, in probabilistic time polynomial in $\log E$, 1. a black box group $\mathsf{X}$ encrypting ${\mathrm{PGL}}_2(\mathbb{F})\cong {\mathrm{SO}}_3(\mathbb{F})$, its subgroup ${\mathsf{Y}}^{\circ }$ of index $2$ isomorphic to $\mathsf{Y}$ and a probabilistic polynomial in $\log E$ time isomorphism ${\mathsf{Y}}^{\circ }⟶\mathsf{Y}$; 2. a black box field $\mathsf{K}$, and 3. polynomial time, in $\log E$, isomorphisms \[ \rm{SO}_3(\mathsf{K}) \longrightarrow \mathsf{X} \longrightarrow \rm{SO}_3(\mathsf{K}). \] If, in addition, we know $p$ and the standard explicitly given finite field $\mathbb{F}$ isomorphic to $\mathbb{F}$ then we construct, in time polynomial in $\log E$, isomorphism \[ \rm{SO}_3(\mathbb{F})\longrightarrow \rm{SO}_3(\mathsf{K}). \] Unlike many papers on black box groups, our algorithms make no use of additional oracles other than the black box group operations. Moreover, our result acts as an ${\mathrm{SL}}_2$-oracle in the black box group theory. We implemented our algorithms in GAP and tested them for groups such as ${\mathrm{PSL}}_2(\mathbb{F})$ for $|\mathbb{F}|=115756986668303657898962467957$ (a prime number).

41 pages

References in corpus (2)

• Construction of Curtis-Phan-Tits system in black box classical groups
• Steinberg presentations of black box classical groups in small characteristics

Cited by in corpus (5)

• Using Jupyter for reproducible scientific workflows
• Finite group actions on abelian groups of finite Morley rank
• Isomorphism testing of groups of cube-free order
• Natural representations of black box groups encrypting $S{L}_2({\mathbb{F}}_q)$
• Degree of Satisfiability in Heyting Algebras