Adjoint representations of black box groups PSL2(F-q)

Abstract

Given a black box group Y encrypting PSL2(F) over an unknown field F of unknown odd characteristic p and a global exponent E for Y (that is, an integer E such that y(E) = 1 for all y is an element of Y), we present a Las Vegas algorithm which constructs a unipotent element in 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. All our algorithms are randomized.