Multiplication in Galois Fields using Matlab

Question

I want to multiply two elements of $GF(2^4)$ with $P(x)=x^4+x+1$ being the irreducible polynomial.
I know how it is done on paper, for example:
$$(0110).(1000)=(x^2+x).(x^3)=x^5+x^4=x^4(x+1)=(x+1)^2=x^2+1=(0101)$$ Equivalently, in Matlab or Mathematica I should multiply 6 by 8 and get 5. Can someone help me how to do this in this software?

Answer 1

A first answer (see for example here) is that MATLAB provides the opportunity to work directly in a $GF(2^n)$. For example, the multiplication table

Fig. 1: Multiplication table of polynomials. One retrieves in particular your $6 \times 8 = 5$.

is obtained by the very simple instruction:

V=gf(0:15,4);V'*V

But if your version hasn't this "gf" function available or if you want to work with Galois Fields $GF(p^n)$ with $p \ne 2$, you can reconstitute it ; here is how.

A key fact is that the coefficients of the product of two polynomials are given in Matlab by the convolution operation between the list of their coefficients.

This convolution (taken mod.2) is for ordinary polynomials. In our case, if the list of zeros and ones obtained by convolution has more than 4 elements (it can have up to seven elements), it has to be truncated, the "extra elements" giving rise to different "addings":

$$[1,0,0,0,0] \to \ \text{adding} \ [0,0,1,1]$$ $$\text{which corresponds to} \ x^4 \to x+1$$

and so on for the other cases (all this mod. 2 of course).

Here is a Matlab script for this function

function P3=pro(P1,P2)
c=mod(conv(P1,P2),2);
L=length(c); % max length of c = 7
c=[zeros(1,7-L),c]; % front zero padding in order that length(c)=7
d=c(1:3); % 3 first terms (corresp. to x^7,x^6,x^5) are set apart
c=c(4:7);
c=c+d(1)*[1,1,0,0];
c=c+d(2)*[0,1,1,0];
c=c+d(3)*[0,0,1,1];
P3=mod(c,2);
end; % of function
P3=pro([0,1,1,0],[1,0,0,0]), % your example.

Here is a program which generates the same muultiplication table as in Fig. 1:

s='01';
T=zeros(16);
for p=0:15
   p1=dec2bin(p)-'0';
   for q=0:15
      q1=dec2bin(q)-'0'; result = list of zeros and ones
      r1=pro(p1,q1);
      T(p+1,q+1)=bin2dec(s(r1+1));
   end
end;
T

Edit: An advise has been given to use other software. Mathematica is interesting but very costly! You have a free powerful environment for abstract algebra called SAGE that you can use from your own computer.

Type:

https://sagecell.sagemath.org/

an editor window will open, then copy

F.<x>= GF(2^4,modulus=x^4+x+1)   
LF = list(F)
for i in [0..15]:
    M=[];
    for j in [0..15]:
        G=LF[i]*LF[j];
        M.append(G);
    print(M)

(respect indentations!) and press button "Evaluate"...