8
$\begingroup$

I'm attempting to implement multiplication and division in $GF(2^8)$ using log and exponential tables. I'm using the exponent of 3 as my generator, using instructions from here.

However I'm having trouble getting the expected answer for some of these trivial multiplications.

For $2 · 4$ this works:

$$ \begin{align*} \log_3(2) &= 25 \\ \log_3(4) &= 50 \\ 25 + 50 &= 75 \\ \exp_3(75) &= 8 \Rightarrow \text{ expected answer} \end{align*}$$

However for $7 · 11$ this breaks down:

$$\begin{align*} \log_3(7) &= 198 \\ \log_3(11) &= 104 \\ 198 + 104 &= 302. \\ \text{Mod it by 255, gives us 47.}\\ \exp_3(47) &= 49 \end{align*}$$ instead of the expected 77.

From what I understand, we use modulus 255 because the 3 generator 'wraps around' on the 255th power (so the pattern repeats after that) thus we only need 0~254. Even if I'm wrong in this, $302 \bmod 256$ still doesn't give us $70$, where $\exp_3(70) = 77$ (the expected answer)

My observation for both multiplication and division is that it works fine until the result of addition/subtraction goes out of range of 0~255.

$\endgroup$

1 Answer 1

14
$\begingroup$

In GF(28), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 1112 and 11 = 10112, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      1112 + 11102 + 1110002 = 101012 + 1110002 = 10011012 = 77,

in GF(2n) addition is done bitwise without carries (i.e. GF(2n) addition is the same as bitwise XOR), and thus we get

      1112 + 11102 + 1110002 = 10012 + 1110002 = 1100012 = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)

$\endgroup$
2
  • $\begingroup$ what about division for the same?? $\endgroup$
    – Kaushal28
    Commented Mar 4, 2017 at 10:43
  • $\begingroup$ @Kaushal28: Using discrete logarithms, division works exactly the same as multiplication, except that you subtract the logarithms instead of adding them: $\log(a/b) = \log(a) - \log(b)$. AFAIK, the easiest way to do division in a finite field without logarithms is to first compute the inverse of the divisor (e.g. using the extended Euclidean algorithm, as shown at the end of this answer) and then multiply that with the dividend. $\endgroup$ Commented Mar 4, 2017 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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