1
$\begingroup$

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

Thanks a lot in advance.

$\endgroup$
9
  • 2
    $\begingroup$ How do you define efficient? All representations of the particular groups you are talking about have dimension 1 (not faithful) or q (faithful or not depending on the action phi). $\endgroup$
    – David A. Craven
    Commented Jul 16, 2021 at 12:11
  • 1
    $\begingroup$ For such groups, the minimum degree of a faithful matrix representation is likely to be 2 (when abelian) or q (when Zq acts faithfully) or q+1 (when Zq acts faithfully on only one Zp and centralizes the other). A matrix representation is built from irreducible matrix representations, and for the groups you've given, the dimensions are either 1 or q. $\endgroup$
    – Jack Schmidt
    Commented Jul 16, 2021 at 12:12
  • $\begingroup$ Thank you @DavidA.Craven I think in those cryptographic protocols they mean that representations that can be computed in polynomial time. So, efficiently computed. $\endgroup$
    – Buddhini Angelika
    Commented Jul 16, 2021 at 12:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – David A. Craven
    Commented Jul 16, 2021 at 12:22
  • 1
    $\begingroup$ Degree of matrix representation is the size. A 2x2 matrix has degree 2. Base group is Zp x Zp. Acting group is Zq. David Craven gave the pattern for the degree q representation. A degree 1, or 2, or q+1 representation is also computable in the same (very fast) way. $\endgroup$
    – Jack Schmidt
    Commented Jul 16, 2021 at 12:35

1 Answer 1

Reset to default
3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Using modular representations. Sneaky. $\endgroup$
    – David A. Craven
    Commented Jul 16, 2021 at 22:22
  • $\begingroup$ @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. $\endgroup$
    – Derek Holt
    Commented Jul 17, 2021 at 7:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .