-1
$\begingroup$

I understood, how this works for arbitrary n and p = 2, but I am struggling with higher prime numbers as a base. In the following, I wanted to use the irreducible polynomial r(x) = x²+1 = 101.

static const __flash uint8_t lookup[9][9] = {
  // 0,  1,  2, 10, 11, 12, 20, 21, 22  

     0,  0,  0,  0,  0,  0,  0,  0,  0,   // 0
     0,  1,  2, 10, 11, 12, 20, 21, 22,   // 1
     0,  2,  ?,  ?,  ?, ...               // 2
     ...

};

In this case the entry of 2 * 2 would be 4 which is equivalent to 10 using a base of 3. 10 mod 101 to the base of 3 would be -21 and that would be equivalent to 2 because -21 + 10 + 10 + 10 = 2 (10 is equivalent to 3 in a base of 3). So the actual final result for this entry would be 2.
Is that correct or completely wrong?
I am struggling because if you would write these entries as polynomials, you would have:
0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2
and if my guess from above is correct, then 2 * 2 = x and x mod x²+1 = 2 and this looks kind of wrong.

$\endgroup$
2
$\begingroup$

if my guess from above is correct, then 2 * 2 = x and x mod x²+1 = 2 and this looks kind of wrong.

Not only does it look wrong, it is wrong.

If $GF(3)$, 2 * 2 = 1, and that continues to be true even if you extend the field to $GF(3^2)$.

In general, multiplying by 2 is easy; we can just use the identity $2 \times a = (1 + 1) \times a = 1 \times a + 1 \times a = a + a$, for any $a$.

The one slighty tricky part is 10 * 10; however, if we just use the polynomial reduction, we get $x \times x = x^2 \bmod x^2 + 1 = x^2 - (x^2 + 1) = 2$, so 10 * 10 = 2.

With that in mind, we can complete every other multiplication operation using the distributive law, for example, $(x + 2) \times (2x + 1) = (x \times 2x) + (x \times 1) + (2 \times 2x) + (2 \times 1) = (2\cdot 2) + (x) + (x) + 2 = 2x$, that is, 12 * 21 = 20

$\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.