17
\$\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\$
6
  • 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
  • 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
  • 1
    \$\begingroup\$ May we produce one function that outputs both the sum and the product? Alternatively, one function that also takes a Boolean parameter that tells it which one to output? \$\endgroup\$
    – xnor
    Jan 4 '20 at 7:56
8
\$\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
\$\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 \bmod 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 \pmod {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!

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

\$\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))
\$\endgroup\$
3
\$\begingroup\$

x86 32-bit machine code, 21 16 bytes

f7 e2 28 e0 01 d0 27 2c 03 a8 08 75 f9 d4 30 c3

-5 with another shorter way to reduce the coefficients modulo 3.

Uses polynomials modulo \$X^2 + 1\$, represented by integers by substituting \$ X = 16 \$. The selected values correspond to canonical forms \$ aX + b\$ for \$a,b \in \{0,1,2\}\$ – hexadecimal 00, 01, 02, 10, 11, 12, 20, 21, 22.

Uses the regparm(2) calling convention – arguments in EAX and EDX, result in AL. The multiplication function begins at the start of the code, and the addition function begins after the first four bytes.

Try it online!

Explanation

gf9_multiply:
    mul edx

Multiply the given polynomials (which are in EAX and EDX). Put the product in EDX:EAX – the value is small enough to fit in EAX, so EDX becomes 0.

    sub al, ah

Subtract AH (the second-lowest byte of EAX) from AL (the lowest byte of EAX). This reduces the polynomial modulo \$ X^2 + 1 \$: AL now represents a polynomial equivalent to the result modulo 3, of the form \$ aX+b \$ for \$ 0 \le a \le 8, -4 \le b \le 4 \$.

gf9_add:
    add eax, edx

Here, the two functions merge.
For gf9_add, this adds EDX and EAX (the arguments), so that AH represents a polynomial equivalent to the result modulo 3, of the form \$ aX+b \$ for \$ 0 \le a \le 4, 0 \le b \le 4 \$.
For gf9_multiply, EDX will be 0 when we get here, and this instruction leaves EAX unchanged.

repeat:
    daa

This is one of several x86 instructions designed for handling numbers in binary-coded decimal.

daa stands for Decimal Adjust (AL) after Addition. "Decimal" in these instruction names refers to packed BCD, which puts one decimal digit in each nybble. As the instruction's name indicates, its intended purpose is to be used after a regular add or similar instruction, to correct the result for BCD.

So what correction is needed?
Consider the simple example of adding 2 (binary 00000010) and 8 (binary 00001000).
The result of regular addition is regular 10 (binary 00001010), but the BCD sum should be BCD 10 (binary 00010000). The result thus has to be increased by 6, to change 10 to 16. That is one of the things that daa does.

But how does it know whether this +6 should be applied? In this case, it is obvious from the value itself, because binary 1010 is not a valid BCD digit. But if the calculation were instead 8 plus 8, the result would be binary 00010000, which is valid BCD for 10, but the correct BCD sum is 16.

This is where the "auxiliary carry flag" (AF) comes in. It is set by the add instruction based on whether it results in a carry across the centre of the byte, which covers the cases where the low nybble reaches 16 or higher and wraps back around to a valid BCD digit. The instruction daa adds 6 to AL if the low nybble of AL is 10 to 15 or AF is 1.

daa also makes a similar adjustment for the high nybble of AL: if the high nybble's original value is 10 to 15, or the carry flag (CF) is 1 (which is based on carries off the top of the number), it adds 6 to the high nybble.

Here, the flags AF and CF come from the preceding add, which always sets them to 0 here. The low nybble is 10 to 15 iff, in the current polynomial \$ aX+b \$ (with \$ 0 \le a \le 8, -4 \le b \le 4 \$), \$ b \$ is -4 to -1, in which case adding 6 results in \$ b \$ being 2 to 5. The high nybble is 10 to 15 only if \$ a \$ is 0 in addition to \$ b \$ being negative, in which case adding 6 to the high nybble makes \$ a \$ 6.

Thus, after the daa, AL still represents a polynomial equivalent to the result modulo 3 of the form \$ aX+b \$, but now with \$ 0 \le a \le 8, 0 \le b \le 5 \$.

    sub al, 3

Subtract 3. Again, AL represents a polynomial equivalent to the result modulo 3 of the form \$ aX+b \$, and this time \$ 0 \le a \le 8, -3 \le b \le 2 \$.

    test al, 8

Look at the eights bit of AL, which is 1 if \$ b \$ is negative and 0 otherwise.

    jnz repeat

Jump back if \$ b \$ is negative (-3 to -1). If that is the case, next daa adds 6 to \$ b \$ while possibly changing \$ a \$ from 0 to 6, similarly to before, and then sub takes 3 from \$ b \$, leaving it with a net +3, which puts it in the range 0 to 2, and then test sees that the eights bit is 0, and the jump does not happen again.

In either case, AL now represents a polynomial equivalent to the result modulo 3 of the form \$ aX+b \$ with \$ 0 \le a \le 8, 0 \le b \le 2 \$.

If it were possible to jump conditionally based on AF, the test could have been omitted for -2 bytes.

    aam 0x30

This is another BCD instruction. In its default form, aam converts a regular number in AL to an unpacked BCD (one byte per decimal digit) number in AH and AL, which is done by setting AH and AL to the quotient and remainder, respectively, of AL divided by 10. However, the instruction allows that number 10 to be changed. We set it to 0x30; the important part is that AL is reduced modulo 0x30, which means \$ a \$ is reduced modulo 3.

At last, the polynomial has been reduced modulo 3 to its canonical form.

    ret

Return.

Previous solution, also 16 bytes

f7 e2 d5 02 01 d0 99 d4 30 c0 c0 04 4a 7a f8 c3

Try it online!

Assembly:

.text
.global gf9_multiply
.global gf9_add
.intel_syntax noprefix

gf9_multiply:
    mul edx     # Multiply EAX by EDX, placing the product in EDX:EAX.
    aad 0x02    # AL := 2 * AH + AL (AL is the low byte of EAX; AH is the next byte.)
                # AH := 0             Reduces the polynomial modulo X^2 - 2.
gf9_add:        # When falling through, EDX=0; the next instruction will do nothing.
    add eax, edx# Add EDX to EAX. Coming from either start point,
                #  this produces in EAX a polynomial equivalent to the result mod 3.
    cdq         # Set each bit of EDX to the high bit of EAX, here 0.
repeat:
    aam 0x30    # (AH, AL) := (quotient, remainder) of AL / 0x30
                # Reduces the coefficient of X modulo 3.
    rol al, 4   # Rotate left by 4 places, swapping the positions of the coefficients.
                #   Next, we need to execute the same two instructions again,
                #    to reduce the other coefficient modulo 3 and swap them back.
                #   Simply repeating those instructions would take 5 bytes.
                #   It is instead done in 4 bytes, including the earlier cdq:
    dec edx     # Decrement EDX, to -1 the first time and -2 the second time.
    jpe repeat  # Jump back if the sum of the eight low bits is even.
                #  This is true for -1 (...11111111) but not for -2 (...11111110).
    ret         # Return.
\$\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!

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