For GF(2^4) arithmetic there are two
irreducible polynomials p(x)=x^4+x+1 & r(x)=x^4+x^3+1
we will use p(x)
addition: a+b -> same as a xor b
multiplication: first shift-add to find a(x)*b(x)
example: a(x)=x^3+x and b(x)=x^2+x+1
a(x)*b(x): a: 1010
b: 0111
---------------------
1010
1010
1010
0000
------------------------ xor addition
0110110
= x^5+x^4+x^3+x^2
Now divide this polynomial by p(x) and find the remainder
fast remaindering algorithm:
replace x^4 by x + 1
x^5 by x^2 + x
x^6 by x^3 + x^2
reduction of x^5+x^4+x^3+x^2 = (x^2+x)+(x+1)+x^3+x^2
= x^3+1
Therefore, a(x)*b(x) mod p(x) is found as x^3+1
GF(17) is arithmetic is mod 17 arithmetic
Numbers are 0,1,2, .., 16
they are 4-bit numbers except 16 which is a 5-bit number
a+b mod n example: 7+12=19 mod 17
=2
a*b mod n example: 7*12=84 mod 17
=-1 or +16
We can create tables for multiplication for both GF(17) &
GF(2^4) arithmetic.