Adjoint representations of black box groups PSL2(F-q)
JOURNAL OF ALGEBRA, vol.506, pp.540-591, 2018 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 506
- Publication Date: 2018
- Doi Number: 10.1016/j.jalgebra.2018.02.022
- Journal Name: JOURNAL OF ALGEBRA
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Page Numbers: pp.540-591
- Keywords: Black box groups, Unipotent elements, PRODUCT REPLACEMENT ALGORITHM, RELATIVISTIC QUANTUM-THEORY, FAST CONSTRUCTIVE RECOGNITION, FORMALISM, SPACE, PROBABILITY, FIELDS
- Istanbul University Affiliated: Yes
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.