Join Log in
Score:0
Buddhini Angelika avatar Crypto

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

us flag
Buddhini Angelika

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.

27
0 + 5
cn flag
j.p.
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.)
1
Reply
Buddhini Angelika avatar
us flag
Buddhini Angelika
Okay, thanks @j.p. one more question. Depends on the characteristic means like if it is a large prime then obtaining matrix representation is more difficult but if it is a small prime then it will be easier, is it like that?
0
Reply
cn flag
j.p.
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. ...
1
Reply
cn flag
j.p.
... 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.
1
Reply
Buddhini Angelika avatar
us flag
Buddhini Angelika
Okay, thank you very very much @j.p.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.