# Checking whether a particular group has an efficient, faithful representation as a matrix group

There are cryptographic protocols being developed for non-abelian groups. For some protocols it is necessary to know whether the group has an efficient representation as a matrix group (say, a matrix group over a field $$\mathbb{F}$$).

What should I do to find out whether a semidirect product of finite groups can be represented as a matrix group efficiently?

Particularly, say semidirect products of the form $$(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$$, where $$p,q$$ are distinct primes, $$(\mathbb{Z}_5 \times \mathbb{Z}_5) \rtimes_{\theta} \mathbb{Z}_3$$. How can I check whether they have efficient, faithful representations as matrix groups (provided that I know $$\phi,\theta$$)?

• Well, they don't need to be computed at all. There is a generic presentation of them. The elements of the base group act as diagonal matrices with various pth roots of unity along the diagonal, and the elements of the acting group are permutation matrices, with $q$th roots of unity as the entries. I guess what I mean is there is a constant time algorithm to determine the (i,j)th entry of the matrices of the generators. Commented Jul 16, 2021 at 12:22
The semidirect products under discussion all embed into $${\rm GL}(3,p)$$, so they all have exceedingly efficient faithful matrix representations of degree $$3$$ over the field $${\mathbb F}_p$$.
• @DavidA.Craven Not really, my immediate reaction to the question was to look for representations over finite fields, given that the poster seemed to want this for computational work. And the field ${\mathbb F}$ was left unpsecified in the question. Commented Jul 17, 2021 at 7:49