Adjoint representations of black box groups PSL_2(F_q

Alexandre Borovik, Sukru Yalcinkaya

    Research output: Contribution to journalArticlepeer-review

    3 Downloads (Pure)

    Abstract

    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 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)≅SO 3(F) over the same field as Y, its subgroup Y of index 2 isomorphic to Y and a polynomial in log⁡E time isomorphism Y ⟶Y;• a black box field K, and• polynomial time, in log⁡E, 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 log⁡E, 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).

    Original languageEnglish
    Pages (from-to)540-591
    Number of pages52
    JournalJournal of Algebra
    Volume506
    Early online date1 Mar 2018
    DOIs
    Publication statusPublished - 1 Mar 2018

    Fingerprint

    Dive into the research topics of 'Adjoint representations of black box groups PSL_2(F_q'. Together they form a unique fingerprint.

    Cite this