3
$\begingroup$

Let me describe my question through an example. Finite field of order (for example) 8 can be constructed as $\mathbb{F}_8 = \mathbb{F}_2[t]/(t^3 + t + 1)$. So one of a natural presentation of the field is the following. $$ \mathbb{F}_8 = \{0, 1, t, t + 1, t^2, t^2 + 1, t^2 + t, t^2 + t + 1\} $$ On the other hand, since the multiplicative group of the field $\langle \zeta \rangle$ is cyclic, the following is also a presentation of the field (as GAP do). $$ \mathbb{F}_8 = \{0, 1, \zeta, \zeta^2, \zeta^3, \zeta^4, \zeta^5, \zeta^6 \} $$ Is there a handy way to get the later presentations from the former ones?

Of course, I can rewrite all the later presentations by relation $t^3 = t + 1$ in advance. But what I would like to do is calculating the later presentation directly when I needed (e.g. when I get the former presentation from matrix multiplication). I would appreciated it if you show me an algorithm for this.

Thank you.

Edit: I rewrite $t$ in the second presentation to $\zeta$. I would also appreciated if you show me a way to find out a primitive $\zeta$ in terms of $t$ (though as DonAntonio already commented, perhaps there is no hope to do so in general).

$\endgroup$
  • 2
    $\begingroup$ I don't think there's a general way to know in general what a primitive element (i.e., generator of the multiplicative group of a finite field) is. The best you can hope for is precisely doingwhat you did...and distinguish between your $\;t$'s ! $\endgroup$ – DonAntonio Apr 2 '14 at 9:37
  • 2
    $\begingroup$ Ok now: in this particular case, @Taro, there is no problem: since $\;|\Bbb F_8^*|=7\;$ is a prime, any non-zero element different of $\;1\;$ is a generator... In the case, for example, of $\;\Bbb F_{16}\;$ you'll already have more options, since $\;\Bbb F_{16}^*\;$ is a group of order $\;15=3\cdot 5\;$ and thus it has only $\;2\cdot 4=8\;$ generators. The fastest, general way I can think of checking is take a non-unit element $\;x\;$ and check whether $\;x^3\neq 1\,,\,\,x^5\neq1\;$...and then you have a generator! :) . For other cases this may take a longer while, of course. $\endgroup$ – DonAntonio Apr 2 '14 at 10:00
  • 2
    $\begingroup$ FWIW: Whenever I run computer calculations involving a finite field, say $\Bbb{F}_{4096}$ or some such, the first thing the program does will be to build look-up-tables going back and forth from one presentation of elements to the other. This is needed e.g. to speed up multiplication in the field. All because this is the easiest way. For all but the smallest fields, in which case I (used to ?) have those table memorized, this is essentially the only way. Probably GAP does it that way, too. $\endgroup$ – Jyrki Lahtonen Apr 3 '14 at 6:11
  • 2
    $\begingroup$ You can get away with using a single look up table, if you use Zech logarithms. Then everything else is reduced to integer arithmetic. I prefer not to do my implementations that way, because with your first presentation addition (in characteristic two) becomes bitwise XOR, which is too efficient to pass up. $\endgroup$ – Jyrki Lahtonen Apr 3 '14 at 6:14
  • 2
    $\begingroup$ Even in the case of a field of prime order $p$, there is no easy way to get from the representation $\{0,1,2,\dots,p-1\}$ to the representation $\{0,1,g,g^2,\dots,g^{p-2}\}$; there no simple formula that gets you $g$ from knowing $p$. This is closely related to the "discrete logarithm problem"; cryptosystems have been based on the difficulty of solving this problem. $\endgroup$ – Gerry Myerson Apr 3 '14 at 11:40
1
$\begingroup$

You can directly check that, talking of the multiplcative group of the field $\;\Bbb F_8\;$ ,we have that $\;ord(t+1)=7\;$ , and thus you can define

$$w:=t+1\implies \Bbb F_8=\{0,1,w,w^2,w^3,w^4,w^4,w^6\}$$

Again, in your post: the first $\;t\;$ (4th line) and the second $\;t\;$ (7-th line) are not necessarily the same, though in this case, passing from one representation to the other, works.

$\endgroup$
  • $\begingroup$ Though I casually ask this question (because the former presentations are a bit space consuming), hoping if there are some nice algorithm, now I understand it is much harder than I expected from comments of you and others. $\endgroup$ – Orat Apr 3 '14 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.