14
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ What exactly does the output have to be? Can we return two functions? Do we have to return the integers we used to represent the field elements? Can we output two tables like iny our example? \$\endgroup\$ – flawr Dec 22 '19 at 11:41
  • \$\begingroup\$ @flawr You have to write two functions or programs for addition and multiplication that take two field elements and return one field element (typically integers). \$\endgroup\$ – nwellnhof Dec 22 '19 at 11:50
  • 2
    \$\begingroup\$ ok then I would suggest clarifying that in your specs - for me at least it was not obvious. \$\endgroup\$ – flawr Dec 22 '19 at 13:24
  • 1
    \$\begingroup\$ The modular operation is equivalent to setting \$x^2+1=0\$, which as we all know has the solution \$x=i\$, so the values \$(-1..1)+(-i..i)\$ form a field GF(9) under balanced modulo 3. \$\endgroup\$ – Neil Dec 22 '19 at 15:40
  • 1
    \$\begingroup\$ Would it be possible to not have links with purely MathJax in them? Using such links stops the default right-click behaviour so opening it in a new tab is annoying. (E.g. consider \$GF(2^8)\$ vs. GF(2⁸).) \$\endgroup\$ – boboquack Dec 22 '19 at 22:55
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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))
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\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.