# 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$$)?

• I think you will find more experts on this topic on math.stackexchange.com, so maybe try asking there (and add links between both questions). The answer will also depend on the characteristic of your field $\mathbb F$, in particular, if it is $p$, $q$, another prime or $0$. (Faithful representations exist always for finite groups, but the sizes of the matrices will heavily depend on the characteristic.)
• That's not what I meant. If your field has $p$-th roots of unity (i.e., in case your field has prime order $r$ this is equivalent to $p$ divides $r-1$) the product $Z_p\times Z_p$ of two cyclic groups of order $p$ can be realized as diagonal $2\times 2$ matrices. If you work over the field $\mathbb{F}_p$, $Z_p\times Z_p$ can be realized as upper triangular $3\times 3$ matrices. This two types of matrices behave completely differently. ...
• ... If you let additionally a cyclic group $Z_q$ act upon them, I expect the extensions to look quite different ($q$ being the characteristic of your field $\mathbb{F}$ will changes things, too). But better ask the experts over at math.stackexchange.com about it.