0
$\begingroup$

In a finite field $F$ of order $2^n$, we know that its additive group is isomorphic to $(\mathbb{Z}_2)^n$. We also know that $(\mathbb{Z}_2)^n$ can be thought of as the set of all $n$-digit binary strings with the operation of XOR. Because of this isomorphism, we can label every element of the additive group of $F$ as an $n$-digit binary string, or in other words an integer in the range $[0,2^n-1]$.

We also know that the multiplicative group of $F$ is isomorphic to the cyclic group of order $2^n-1$. Because of this, we can label every element in $F^*$ as an integer in the range $[0,2^n-2]$.

My question is, is there some way in which we can map the representation of an element as a binary string in $(\mathbb{Z}_2)^n$ to its representation as an integer in $\mathbb{Z}_{2^n-1}$?

I will give an example of the galois field of order 8. On can easily see this as the set of polynomials in $\mathbb{Z}_2[x]$ with degree less than or equal to 3: $\{0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$. It's binary representation is simply the ordered triple of its coefficients (so the set given can be represented as $0...7$ in the order they are given.

We can also write the multiplicative group of this set as $\{1,x,x^2,x^2+1,x^2+x+1,x+1,x^2+x\}$, which, in this order, is isomorphic to the cyclic group of order 7, and so in that order the elements can be relabelled as $0...6$

A mapping from the integer representation of the elements in their additive group (binary strings with xor) to the integer representation of elements in their multiplicative group (integers with addition mod 7) would be:

$$ 1 \mapsto 0$$ $$ 2 \mapsto 1$$ $$ 3 \mapsto 5 $$ $$ 4 \mapsto 2 $$ $$ 5 \mapsto 3 $$ $$ 6 \mapsto 6 $$ $$ 7 \mapsto 4 $$

I made this mapping through brute force, but I was wondering if there is any general form for this mapping or some way to generate it for an arbitrary $n$?

Further clarification: The set $\{0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$ (additive group arranged in order of order of their binary representations) can be written as $\{0,1,2,3,4,5,6,7\}$ and using that correspondence, the set $\{1,x,x^2,x^2+1,x^2+x+1,x+1,x^2+x\}$ (multiplicative group, ordered by their corresponding elements in the cyclic group) can be written as $\{1,2,4,5,7,3,6\}$ and the mapping just maps the integers from the first set to the second set (in the order in which they are represented).

$\endgroup$
  • $\begingroup$ What properties do you want the mapping to have? $\endgroup$ – Mariano Suárez-Álvarez Feb 17 '15 at 22:11
  • $\begingroup$ It takes the representation of an element as a binary string (in additive group) to the representation of the same element as an integer in $\mathbb{Z}_2^n-1$ (in multiplicative group) $\endgroup$ – ASKASK Feb 17 '15 at 22:13
  • $\begingroup$ So in that example, $100=4$ is the representation of $x^2$ as a binary string, and 2 is the representation of $x^2$ as a member of the cyclic group of order 7 $\endgroup$ – ASKASK Feb 17 '15 at 22:14
  • 1
    $\begingroup$ Isn't the multiplicative group just the set of powers $\alpha^k$ of a generator $\alpha$? $\endgroup$ – MPW Feb 17 '15 at 22:24
  • 1
    $\begingroup$ Yes it is, does that have significance though? If we are looking at the binary representation of two elements, the multiplication of them is a completely different multiplication than the multiplication of the two elements themselves $\endgroup$ – ASKASK Feb 17 '15 at 22:27
1
$\begingroup$

No, there is no standard easy way to do this without brute force. Usually when you are using a computer algebra system, this correspondence is computed and saved (as a table of Zech's logarithms) so that multiplication and addition can both be efficiently done in terms of the best representation (addition as vector addition in $\mathbb{F}_{p}^{e}$, where $q = p^{e}$, multiplication as integer multiplication in terms of powers of the generator for $\mathbb{F}^{*}$).

The difficulty of this problem (computing logarithms in a finite field) is the basis for several cryptographic algorithms.

$\endgroup$

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.