Generating random elements in finite groups.
Software, source code, etc. for problems pertaining to group theory (20-04) Arithmetic and combinatorial problems involving abstract finite groups (20D60) Generators, relations, and presentations of groups (20F05) Probabilistic methods in group theory (20P05) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Randomized algorithms (68W20)
The main result of the paper gives a theoretical justification of an algorithm proposed by Gene Cooperman, for constructing random generators for finite groups. If \(x_1,\dots,x_m\) is a list of elements in \(G\), then the random cube \(\text{Cube}(x_1,\dots,x_m)\) is the probability distribution on \(G\) induced by the map \((\varepsilon_1,\dots,\varepsilon_m)\mapsto x_1^{\varepsilon_1}\cdots x_m^{\varepsilon_m}\) from the uniform distribution on \(\{0,1\}^m\). The author proves the following: let \(x_1,\dots,x_d\) be a list of generators for \(G\) and consider a sequences of cubes \(W_k:=\text{Cube}(x_k^{-1},\dots,x_1^{-1},x_1,\dots,x_k)\), where for \(k>d\), \(x_k\) is chosen at random from \(W_{k-1}\). For each \(\delta>0\) there is a constant \(K_\delta>0\) independent of \(G\) such that, with probability at least \(1-\delta\), the distribution \(W_m\) is 1/4-uniform when \(m\geq d+K_\delta\lg|G|\). The value obtained for the constant \(K_\delta\) and the fact that the number of group operations to construct the random element generator is proportional to \(\log^2|G|\) still means that a direct implementation of an algorithm based on this result may be impractical: in the final part of the paper the author examines some possible ways in which the process may be speeded up and how shorter random element generators might be constructed.
- Generating random elements of finite distributive lattices
- Strong involutions in finite special linear groups of odd characteristic
- \textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments
- Experimental study of the hypothesis on the order of a random element of the matrix modular group
- Black box exceptional groups of Lie type.
- Translation-randomizable distributions via random walks
- Combining random generators by group operation
- Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
- On layers in the system of generators of the subdirect product of subgroups of a finite group.
- scientific article; zbMATH DE number 5012619 (Why is no real title available?)
- The Subgroup Algorithm for Generating Uniform Random Variables
- Black box exceptional groups of Lie type. II.
- Generating random elements of a finite group
- Towards constructing fully homomorphic encryption without ciphertext noise from group theory
- An Implementation of the Neumann–Praeger Algorithm for the Recognition of Special Linear Groups
- Generating random elements of abelian groups
- On generation of random covers for finite groups
- Interactions of computational complexity theory and mathematics
- Random generation of finite and profinite groups and group enumeration.
- The product replacement prospector.
- How (not) to hash into class groups of imaginary quadratic fields?
- A polynomial-time reduction algorithm for groups of semilinear or subfield class.
This page was built for publication: Generating random elements in finite groups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010821)
