0
$\begingroup$

I am a beginner in the filed theory. So, I have a few questions.

  1. Consider a matrix $A$ whose each element is in $GF(2)$ (i.e. $0$ or $1$) and a matrix $B$, each element of which is of $512$ bits. If I multiply them together, $C = AB$, will the elements of $C$ be of $512$ bits, or just $0$ and $1$?

  2. Similarly, if we consider the elements of $A$ is in $GF(2^{10})$, what would be the elements of $C$?

I am a bit confused. I think for the first question the answer should be $512$ bits and for the second question, the answer should also be the same. Can someone clarify if I am right or not?

$\endgroup$
3
  • $\begingroup$ Welcome to MSE! For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$
    – platty
    Dec 1, 2018 at 1:50
  • $\begingroup$ I don't think we can answer your question as it stands. You need to tell us where $A$ and $B$ come from, and what you want to use $C$ for. $\endgroup$
    – TonyK
    Dec 1, 2018 at 1:53
  • $\begingroup$ I don't quite understand what you meant by where $A$ and $B$ come from? Let me give you an example. If $A$ = [$1$ $0$;$1$ $1$] and $B$ is $[5;3]$ then you can have $C$ as $[5;8]$. Here we can express 5, 3 and 8 in binary. If we consider them as 3 bits, result is also 3 bits. So, my question was does it change for $GF(2)$ or $GF(2^{10})$? $\endgroup$
    – Bikas
    Dec 1, 2018 at 3:42

1 Answer 1

Reset to default
0
$\begingroup$

English languages uses 26 alphabets. But when we read it we have to read them word by word (rather than individual letters). Analogously all Galois Fields $GF(2^n)$ for all $n$ use binary digits 0 and 1 at a primitive level. But words here are "n-bits at a time". So Galois Fields $GF(512)$ and $GF(1024)$ are to be understood as using same alphabet but their word lengths are 9 and 10 respectively.

The theory tells us how to add two $n$-bit string to fetch an $n$-bit string as their sum (bitwise XOR). And also the mathematicians have a rule (somewhat complicated) that specifies how to multiply two $n$-bit strings to yield another $n$-bit string as their product. The "sum" and "product" operations on binary strings obeying the usual conditions of our familiar number system (commutativity, assocoitivity, distributivity etc).

$\endgroup$
6
  • $\begingroup$ If I understand you correctly, for second case, we can do simple matrix multiplication and then use irreducible polynomial to find the mod. Then replace each value with this mod. But if I use this same logic for the first case, doesn't it simply reduce it to 1 and 0? $\endgroup$
    – Bikas
    Dec 1, 2018 at 3:39
  • $\begingroup$ When you do matrix multiplication entry at position (i,j) is: $x_{i1}.y_{1j}+x_{i2}.y_{2j}+\cdots+x_{in}.y_{nj}$ Each entry such as $x_{ik}$ is a 9-bit string. The dot means the multiplication of, e.g., 9-bit strings I mentioned. The plus sign means bitwise XOR. So it WILL reduce to a word of 9-bit string. This is your case 2. For your case 1, each product $x_{ik}y_{kj}$ will be either 0 or 1. So finally it will be 1 if and only odd number of such products are 1. $\endgroup$
    – P Vanchinathan
    Dec 1, 2018 at 4:46
  • $\begingroup$ I think I understand what your are saying. Thanks! $\endgroup$
    – Bikas
    Dec 1, 2018 at 5:00
  • $\begingroup$ So, is it not possible to have multiplication of two matrices while elements of one are in $GF(2)$ and other is in $R$ to result in a matrix in $R$? $\endgroup$
    – Bikas
    Dec 1, 2018 at 5:04
  • $\begingroup$ NO. Nit because some impossibility result. All the existing binary operations take two elements BOTH from same set, and yield an answer in the same set. $\endgroup$
    – P Vanchinathan
    Dec 1, 2018 at 7:32

You must log in to answer this question.

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