TY - JOUR

T1 - Adjoint representations of black box groups PSL_2(F_q

AU - Borovik, Alexandre

AU - Yalcinkaya, Sukru

N1 - Funding Information:
This paper would have never been written if the authors did not enjoy the warm hospitality offered to them at the Nesin Mathematics Village in Şirince, Izmir Province, Turkey, in Summers 2011–17; our thanks go to Ali Nesin and to all volunteers, staff, and students who have made the Village a mathematical paradise. We thank Adrien Deloro and Roman Kossak for many fruitful discussions, and Alexander Konovalov and Chris Stephenson who helped us to clarify links with the computer science. We thank the anonymous referee for many useful comments and corrections. Our work was partially supported by the Marie Curie FP7 Initial Training Network MALOA (PITN-GA-2008-MALOA no. 238381 ) and by CoDiMa (CCP in the area of Computational Discrete Mathematics; EPSRC grant EP/M022641/1 ), and by The Dame Kathleen Ollerenshaw Trust . In the project, we were using the GAP software package by The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.8.4; 2016 ( http://www.gap-system.org ). Our text uses the Commutative Diagrams package by Paul Taylor, http://www.paultaylor.eu/diagrams/ .
Publisher Copyright:
© 2018 The Authors
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2018/3/1

Y1 - 2018/3/1

N2 - Given a black box group Y encrypting PSL
2(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∈Y), we present a Las Vegas algorithm which constructs a unipotent element in Y. The running time of our algorithm is polynomial in logE. This answers the question posed by Babai and Beals in 1999. We also find the characteristic of the underlying field in time polynomial in logE and linear in p. All our algorithms are randomized. Furthermore, we construct, in time polynomial in logE, • a black box group X encrypting PGL
2(F)≅SO
3(F) over the same field as Y, its subgroup Y
∘ of index 2 isomorphic to Y and a polynomial in logE time isomorphism Y
∘⟶Y;• a black box field K, and• polynomial time, in logE, isomorphisms SO
3(K)⟶X⟶SO
3(K).If, in addition, we know p and the standard explicitly given finite field F
q isomorphic to the field on which Y is defined then we construct, in time polynomial in logE, isomorphism SO
3(F
q)⟶SO
3(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 SL
2-oracle in the black box group theory. We implemented our algorithms in GAP and tested them for groups such as PSL
2(F) for |F|=115756986668303657898962467957 (a prime number).

AB - Given a black box group Y encrypting PSL
2(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∈Y), we present a Las Vegas algorithm which constructs a unipotent element in Y. The running time of our algorithm is polynomial in logE. This answers the question posed by Babai and Beals in 1999. We also find the characteristic of the underlying field in time polynomial in logE and linear in p. All our algorithms are randomized. Furthermore, we construct, in time polynomial in logE, • a black box group X encrypting PGL
2(F)≅SO
3(F) over the same field as Y, its subgroup Y
∘ of index 2 isomorphic to Y and a polynomial in logE time isomorphism Y
∘⟶Y;• a black box field K, and• polynomial time, in logE, isomorphisms SO
3(K)⟶X⟶SO
3(K).If, in addition, we know p and the standard explicitly given finite field F
q isomorphic to the field on which Y is defined then we construct, in time polynomial in logE, isomorphism SO
3(F
q)⟶SO
3(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 SL
2-oracle in the black box group theory. We implemented our algorithms in GAP and tested them for groups such as PSL
2(F) for |F|=115756986668303657898962467957 (a prime number).

U2 - 10.1016/j.jalgebra.2018.02.022

DO - 10.1016/j.jalgebra.2018.02.022

M3 - Article

VL - 506

SP - 540

EP - 591

JO - Journal of Algebra

JF - Journal of Algebra

SN - 0021-8693

ER -