Fifty Shades of Black

Abstract

The paper proposes a new and systematic approach to the so-called black box group methods in computational group theory. As the starting point of our programme, we construct Frobenius maps on black box groups of untwisted Lie type in odd characteristic and then apply them to black box groupsXencrypting groups (P)SL2(q) in small odd characteristics. We propose an algorithm constructing a black box fieldKisomorphic toFq, and an isomorphism from (P)SL2(K) toX. The algorithm runs in time quadratic in the characteristic of the underlying field and polynomial in logq.Due to the nature of our work we also have to discuss a few methodological issues of the black box group theory.