Define the finite field GF(9)

Question

\$GF(9)\$ or \$GF(3^2)\$ is the smallest finite field whose order isn't a prime or a power of two. Finite fields of prime order aren't particurlarly interesting and there are already challenges for \$GF(2^8)\$ (link) and \$GF(2^{64})\$ (link).

Challenge

First define nine elements of the field. These must be distinct integers from 0 to 255, or the one-byte characters their code points represent. State in your answer which representation you choose.

Then implement two binary operations, addition and multiplication, satisfying the field axioms:

• Both operations must be commutative and associative.
• Addition has the identity element \$0\$ and an additive inverse for each element.
• Multiplication has the identity element \$1\$ and a multiplicative inverse for each element except \$0\$.
• Multiplication distributes over addition: \$a·(b+c) = (a·b)+(a·c)\$

Addition and multiplication can be implemented as functions or programs taking two field elements and producing one field element.

Since the field is really small, you can test the axioms exhaustively to check your implementation or verify the addition and multiplication tables.

Mathematical construction

Elements of \$GF(3^2)\$ can be interpreted as polynomials of the form \$P(x)=a x+b\$ over \$GF(3)\$. (Addition and multiplication in \$GF(3)=\{0,1,2\}\$ are the standard integer operations modulo 3.)

Then addition in \$GF(3^2)\$ is simply the addition of two polynomials. Multiplication is defined by the product of two polynomials, reduced modulo a polynomial of degree 2 which is irreducible over \$GF(3)\$.

Example

Mapping polynomials to integers with \$n=3a+b\$ and using the irreducible polynomial \$x^2+1\$ yields the following addition and multiplication tables. Note that there are other possible isomorphisms of these tables.

+   0 1 2 3 4 5 6 7 8   *   0 1 2 3 4 5 6 7 8
   ------------------      ------------------
0 | 0 1 2 3 4 5 6 7 8   0 | 0 0 0 0 0 0 0 0 0
1 | 1 2 0 4 5 3 7 8 6   1 | 0 1 2 3 4 5 6 7 8
2 | 2 0 1 5 3 4 8 6 7   2 | 0 2 1 6 8 7 3 5 4
3 | 3 4 5 6 7 8 0 1 2   3 | 0 3 6 2 5 8 1 4 7
4 | 4 5 3 7 8 6 1 2 0   4 | 0 4 8 5 6 1 7 2 3
5 | 5 3 4 8 6 7 2 0 1   5 | 0 5 7 8 1 3 4 6 2
6 | 6 7 8 0 1 2 3 4 5   6 | 0 6 3 1 7 4 2 8 5
7 | 7 8 6 1 2 0 4 5 3   7 | 0 7 5 4 2 6 8 3 1
8 | 8 6 7 2 0 1 5 3 4   8 | 0 8 4 7 3 2 5 1 6

Test of distributivity using the tables above:

$$5 · (2 + 7) = 5 · 6 = 4$$ $$(5 · 2) + (5 · 7) = 7 + 6 = 4$$

Note that simply using addition and multiplication modulo 9 won't work.

Scoring

This is code golf. Your score is the sum of bytes of the functions (or programs) for addition and multiplication. Lowest number of bytes wins.

Answer 1

05AB1E, 24 17 16 bytes

Uses 0, 1, 2, 10, 11, 12, 20, 21, 22 as the 9 field elements.

Addition, 5 bytes:

OS3%J

Try it online! or print the entire table.

O             # sum of the inputs
 S            # split to a list of digits
  3%          # mod 3 each digit
    J         # join

Multiplication, 11 bytes:

PƵÈ%98%S3%J

Try it online! or print the entire table.

P             # product of the inputs
 ƵÈ%          # mod 300
    98%       # mod 98
       S3%J   # split, mod 3 each digit, join

Answer 2

Haskell, 118 112 107 bytes

Here I use the numbers \$n= 0,1,2,\ldots,8\$ to represent the field elements. Internally these are converted to a list \$[a,b]\$ that represents a polynomial \$aX+b\$, (using \$a = \lfloor n/3 \rfloor\$ and \$b = n \mod 3 \$, or \$n=3a+b\$), and we then proceed using the usual arithmetic using these polynomials in \$(\mathbb Z / 3\mathbb Z)[X]/(X^2+1)\$. In this case we have

$$(aX+b) + (cX+d) = (a+c)X + (b+d)$$

and similarly

$$\begin{align*} (aX+b) \cdot (cX+d) &= acX^2+(ad+bc)X + bd \\ & \equiv ac(-1) +(ad+bc)X + bd \mod X^2+1\\ & \equiv (ad+bc)X+(bd-ac) \end{align*}$$

Thanks for -6 bytes @WheatWizard!

i x=[div x 3,x]                --conert integer to polynomial/list representation
j[a,b]=mod(a*3+mod b 3)9       --inverse of i
s=(.i).(j.).zipWith(+).i       --"sum"
m[a,b][c,d]=j[a*d+b*c,b*d-a*c] --core function of "product"
p=(.i).m.i                     --"product"

Try it online!

Answer 3

Retina 0.8.2, 53 + 111 = 164 23 + 61 = 84 bytes

Edit: Saved 80 bytes by switching to @Grimmy's I/O format. However, the provided links include a footer which converts the output back to 0-8 format and formats the results into a square.

Addition (53 23 bytes):

\d+
$*
M`1
3$
0
T`34`_1

Try it online! Link includes test suite. Explanation:

\d+
$*

Convert both arguments to unary.

M`1

Take the sum and convert to decimal.

3$
0
T`34`_1

Modulo the last digit by 3, and modulo by 30.

Multiplication (111 61 bytes):

\d+
$*
1(?=1*;(1*))|.
$1
1{300}|1{98}|1{30}

M`1
T`3-8`012012

Try it online! Link includes test suite. Explanation:

\d+
$*

Convert to unary.

1(?=1*;(1*))|.
$1

Take the product.

1{300}|1{98}|1{30}

Modulo by 300, 98 and 30.

M`1

Convert to decimal.

T`3-8`012012

Modulo the last digit by 3.

Answer 4

MATLAB, 106 104 102 bytes

We encode \$\operatorname{GF}(9)\$ as \$\{0,\ldots,8\}\$ and map to \$\mathbb{Z}[i]/\langle 3\rangle\$ in order to add and multiply:

e=@(x)mod(x,3)+i*fix(x/3)
d=@(x)[1 3]*mod([real(x);imag(x)],3)
a=@(x,y)d(e(x)+e(y))
m=@(x,y)d(e(x)*e(y))

@A.Rex pointed out this clever improvement:

e=@(x)mod(x,3)+i*round(x/3)
d=@(x)mod(real(x)^3+3*imag(x),9)
a=@(x,y)d(e(x)+e(y))
m=@(x,y)d(e(x)*e(y))

Answer 5

Pari/GP, 88 bytes

Uses numbers 0 to 8 to represent the elements. Uses Pari/GP's built-in polynomial arithmetic.

f(a)=a%3+a\3*x
g(a)=Vecrev(a%(x^2+1),2)%3*[1,3]~
s(a,b)=g(f(a)+f(b))
p(a,b)=g(f(a)*f(b))

Try it online!

---

Pari/GP, 86 bytes

Inspired by Dustin G. Mixon's answer.

f(a)=a%3+a\3*I
g(a)=[real(a),imag(a)]%3*[1,3]~
s(a,b)=g(f(a)+f(b))
p(a,b)=g(f(a)*f(b))

Try it online!