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

作者：Borovik Alexandre^*; Yalcinkaya Sukru

来源：Journal of Algebra, 2018, 506: 540-591.

DOI：10.1016/j.jalgebra.2018.02.022

• Black box groups
• Unipotent elements

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.
Furthermore, we construct, in time polynomial in log E,
a black box group X encrypting PGL(2)(F) congruent to SO3(F) over the same field as Y, its subgroup Y degrees of index 2 isomorphic to Y and a polynomial in log E time isomorphism Y degrees -> Y
a black box field K, and
polynomial time, in log E, isomorphisms
SO3 (K) -> X -> SO3 (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 log E, isomorphism
SO3(F-q) -> SO3 (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 SL2-oracle in the black box group theory.
We implemented our algorithms in GAP and tested them for groups such as PSL2(F) for
vertical bar F vertical bar = 115756986668303657898962467957
(a prime number).

• 出版日期2018-7-15