scientific article; zbMATH DE number 1004932

MaRDI QIDQ4335294zbMATH OpenFDO

Authors Gene Cooperman, Larry Finkelstein, Steve Linton

Publication date 26 May 1998

zbMATH Keywords

black box groupscomputational methodsgeneral linear groupsgenerating setsMonte Carlo algorithmsrandom elements

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Linear algebraic groups over finite fields (20G40)

Review text

The paper describes a Monte Carlo algorithm for the construction of the natural representation of a group \(G\) that is known to be isomorphic to \(\text{GL}(n,2)\). The main result is the following: Given a black box group \(G\) specified by a generating set \(E\) which is known to be isomorphic to \(\text{GL}(n,2)\) for some \(n\). Let \(M\) be a known upper bound on \(n\), let \(\mu\) be the time required to perform a group operation in \(G\), let \(\rho\) be the time required to compute a (nearly) uniform random element in \(G\), and let \(\varepsilon\) be the time for a field operation in \(\text{GF}(2)\). Then a Monte Carlo algorithm exists which in time \(O((M\log^2 M+n^2)\mu+M\rho+n^2\varepsilon)\) can determine the value of \(n\) and produce a data structure that can be used to compute an isomorphism \(\Delta\colon G\to\text{GL}(n,2)\). The computation of \(\Delta(x)\), for \(x\in G\), takes \(O(n^2\mu)\) steps. In particular, if the elements of \(G\) are given by binary strings of length \(N\) then \(M=1+\sqrt N\) is sufficient. For the entire collection see [Zbl 0861.00012].

Recommendations

• Black box groups isomorphic to \(\mathrm{PGL}(2,2^e)\).
• On constructive recognition of a black box \(\text{PSL}(d,q)\).
• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• Black box classical groups.

Cited in

(8)

• Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
• Fast constructive recognition of black box orthogonal groups.
• On constructive recognition of a black box \(\text{PSL}(d,q)\).
• Black box exceptional groups of Lie type.
• Black box groups isomorphic to \(\mathrm{PGL}(2,2^e)\).
• Effective black-box constructive recognition of classical groups.
• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• Fast Constructive Recognition of Black-Box Unitary Groups

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4335294)