Adjoint representations of black box groups PSL_2(F_q

Alexandre Borovik; Sukru Yalcinkaya

doi:10.1016/j.jalgebra.2018.02.022

Adjoint representations of black box groups PSL_2(F_q

Alexandre Borovik, Sukru Yalcinkaya

Istanbul University

Research output: Contribution to journal › Article › peer-review

3 Downloads (Pure)

Abstract

Given a black box group Y encrypting PSL ₂(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 ₂(F)≅SO ₃(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 ₃(K)⟶X⟶SO ₃(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 ₃(F _q)⟶SO ₃(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 ₂-oracle in the black box group theory. We implemented our algorithms in GAP and tested them for groups such as PSL ₂(F) for |F|=115756986668303657898962467957 (a prime number).

Original language	English
Pages (from-to)	540-591
Number of pages	52
Journal	Journal of Algebra
Volume	506
Early online date	1 Mar 2018
DOIs	https://doi.org/10.1016/j.jalgebra.2018.02.022
Publication status	Published - 1 Mar 2018

Access to Document

10.1016/j.jalgebra.2018.02.022

Cite this

@article{4f033576c1da4464935abcb6e4883ea5,

title = "Adjoint representations of black box groups PSL_2(F_q",

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). ",

author = "Alexandre Borovik and Sukru Yalcinkaya",

note = "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 {\c S}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: {\textcopyright} 2018 The Authors Copyright: Copyright 2018 Elsevier B.V., All rights reserved.",

year = "2018",

month = mar,

day = "1",

doi = "10.1016/j.jalgebra.2018.02.022",

language = "English",

volume = "506",

pages = "540--591",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Elsevier BV",

}

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 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).

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 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).

U2 - 10.1016/j.jalgebra.2018.02.022

DO - 10.1016/j.jalgebra.2018.02.022

M3 - Article

SN - 0021-8693

VL - 506

SP - 540

EP - 591

JO - Journal of Algebra

JF - Journal of Algebra

ER -

Adjoint representations of black box groups PSL_2(F_q

Abstract

Access to Document

Fingerprint

Cite this