A field in mathematics is a set of numbers, with addition and multiplication operations defined on it, such that they satisfy certain axioms (described in Wikipedia; see also below).

A finite field can have pn elements, where p is a prime number, and n is a natural number. In this challenge, let's take p = 2 and n = 8, so let's make a field with 256 elements.

The elements of the field should be consecutive integers in a range that contains 0 and 1:

  • -128 ... 127
  • 0 ... 255
  • or any other such range

Define two functions (or programs, if that is easier), a(x,y) for abstract "addition", and m(x,y) for abstract "multiplication", such that they satisfy the field axioms:

  • Consistency: a(x,y) and m(x,y) produce the same result when called with same arguments
  • Closedness: The result of a and m is an integer in the relevant range
  • Associativity: for any x, y and z in the range, a(a(x,y),z) is equal to a(x,a(y,z)); the same for m
  • Commutativity: for any x and y in the range, a(x,y) is equal to a(y,x); the same for m
  • Distributivity: for any x, y and z in the range, m(x,a(y,z)) is equal to a(m(x,y),m(x,z))
  • Neutral elements: for any x in the range, a(0,x) is equal to x, and m(1,x) is equal to x
  • Negation: for any x in the range, there exists such y that a(x,y) is 0
  • Inverse: for any x≠0 in the range, there exists such y that m(x,y) is 1

The names a and m are just examples; you can use other names, or unnamed functions. The score of your answer is the sum of byte-lengths for a and m.

If you use a built-in function, please also describe in words which result it produces (e.g. provide a multiplication table).

  • 3
    \$\begingroup\$ @LeakyNun "addition" is just an abstract operation here that satisfies the above properties. There is no need for a(2,1) = 3, you could have a(2,1) = 5 as long as the above axioms are satisfied. a doesn't have to do anything with the usual addition you're used to e.g. from the field of rational numbers. \$\endgroup\$ Commented Jun 14, 2016 at 7:41
  • 2
    \$\begingroup\$ A commutative ring is trivial. A field... not so easy. \$\endgroup\$
    – Neil
    Commented Jun 14, 2016 at 7:50
  • \$\begingroup\$ Is there anything wrong with a=+ m=×? \$\endgroup\$
    – Adám
    Commented Jun 14, 2016 at 8:01
  • 4
    \$\begingroup\$ @Adám Yes - 2 wouldn't have an inverse if m=× \$\endgroup\$
    – Sp3000
    Commented Jun 14, 2016 at 8:02
  • 2
    \$\begingroup\$ Related \$\endgroup\$ Commented Jun 14, 2016 at 9:48

6 Answers 6


Python 2, 11 + 45 = 56 bytes

Addition (11 bytes):


Multiplication (45 bytes):

m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

Takes input numbers in the range [0 ... 255]. Addition is just bitwise XOR, multiplication is multiplication of polynomials with coefficients in GF2 with Russian peasant.

And for checking:

m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

for x in range(256):
    assert a(0,x) == a(x,0) == x
    assert m(1,x) == m(x,1) == x

    assert any(a(x,y) == 0 for y in range(256))

    if x != 0:
        assert any(m(x,y) == 1 for y in range(256))

    for y in range(256):
        assert 0 <= a(x,y) < 256
        assert 0 <= m(x,y) < 256
        assert a(x,y) == a(y,x)
        assert m(x,y) == m(y,x)

        for z in range(256):
            assert a(a(x,y),z) == a(x,a(y,z))
            assert m(m(x,y),z) == m(x,m(y,z))
            assert m(x,a(y,z)) == a(m(x,y), m(x,z))
  • \$\begingroup\$ One of us is going to have to change :P \$\endgroup\$
    – user45941
    Commented Jun 14, 2016 at 8:29
  • \$\begingroup\$ @Mego Hah, well... I'll try and see if I can find any other approaches. Might be hard to beat though. \$\endgroup\$
    – Sp3000
    Commented Jun 14, 2016 at 8:32
  • 1
    \$\begingroup\$ Which polynomial is it based on? \$\endgroup\$
    – feersum
    Commented Jun 14, 2016 at 18:56
  • 1
    \$\begingroup\$ @LSpice Now I realize that I can easily find the polynomial by running m(2,128) which results in 27 = 283 - 256, so you are correct and the polynomial is x^8 + x^4 + x^3 + x + 1. \$\endgroup\$
    – feersum
    Commented Jun 14, 2016 at 21:21
  • 1
    \$\begingroup\$ @LSpice In Neil's answer he gives a Wikipedia page as a source for the algorithm, so maybe everyone read that. But it is anyway the most obvious choice for code golf since it the smallest irreducible polynomial of degree 8 in this representation. \$\endgroup\$
    – feersum
    Commented Jun 14, 2016 at 21:29

Intel x86-64 + AVX-512 + GFNI, 11 bytes

    C5 F0 57 C0     # vxorps     xmm0, xmm1, xmm0
    C3              # ret
    C4 E2 79 CF C1  # vgf2p8mulb xmm0, xmm0, xmm1
    C3              # ret

Uses the new GF2P8MULB instruction on Ice Lake CPUs.

The instruction multiplies elements in the finite field GF(28), operating on a byte (field element) in the first source operand and the corresponding byte in a second source operand. The field GF(28) is represented in polynomial representation with the reduction polynomial x8 + x4 + x3 + x + 1.


JavaScript (ES6), 10 + 49 = 59 bytes


Domain is 0 ... 255. Source.

  • 2
    \$\begingroup\$ You should probably specify the range you're using. \$\endgroup\$ Commented Jun 14, 2016 at 9:26

Hoon, 22 bytes

[dif pro]:(ga 8 283 3)

Hoon already has a function ++ga that creates Galois Fields, for use in the AES implementation. This returns a tuple of two functions, instead of using two programs.

Operates in the domain [0...255]


=+  f=(ga 8 283 3)
=+  n=(gulf 0 255)

=+  a=dif:f
=+  m=pro:f

=+  %+  turn  n
    |=  x/@
    ?>  =((a 0 x) x)
    ?>  =((m 1 x) x)
    ~&  outer+x

    %+  turn  n
      |=  y/@
      ?>  =((a x y) (a y x))
      ?>  &((lte 0 (a x y)) (lte (a x y) 255))
      ?>  &((lte 0 (m x y)) (lte (m x y) 255))

      %+  turn  n
        |=  z/@
        ?>  =((a (a x y) z) (a x (a y z)))
        ?>  =((m x (a y z)) (a (m x y) (m x z)))

Posting a multiplication table would be gigantic, so here are some random testcases:


IA-32 machine code, 22 bytes

"Multiplication", 18 bytes:

33 c0 92 d1 e9 73 02 33 d0 d0 e0 73 02 34 1b 41
e2 f1

"Addition", 4 bytes:

92 33 c1 c3

This stretches rules a bit: the "multiplication" code lacks function exit code; it relies on the "addition" code being in memory right afterwards, so it can "fall-through". I did it to decrease code size by 1 byte.

Source code (can be assembled by ml of MS Visual Studio):

    TITLE   x


@m@8    PROC
    xor eax, eax;
    xchg eax, edx;
    shr ecx, 1
    jnc sk1
    xor edx, eax
    shl al, 1
    jnc sk2
    xor al, 1bh
    inc ecx
    loop myloop
@m@8 endp

@a@8 proc
    xchg eax, edx;
    xor eax, ecx
@a@8    ENDP
_text ENDS

The algorithm is the standard one, involving the usual polynomial x^8 + x^4 + x^3 + x + 1, represented by the hexadecimal number 1b. The "multiplication" code accumulates the result in edx. When done, it falls through to the addition code, which moves it to eax (conventional register to hold return value); the xor with ecx is a no-op, because at that point ecx is cleared.

One peculiar feature is the loop. Instead of checking for zero

cmp ecx, 0
jne myloop

it uses the dedicated loop instruction. But this instruction decreases the loop "counter" before comparing it to 0. To compensate for this, the code increases it before using the loop instruction.


Mathematica 155 bytes



  in: o[Times, 202, 83]    out: 1
  in: o[Plus, 202, 83]     out: 153

addition check:

  in: BitXor[202, 83]      out: 153


  in: o[Times, #, #2] & @@@ {{20, 148}, {61, 189}, {111, 239}, {163, 36}, {193, 40}}
  out: {229, 143, 181, 29, 1}

NB Should be able to use any of {283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375, 379, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 499, 501, 505} in place of 283.

  • \$\begingroup\$ Well, here's 13 bytes less: ±y_:=Total[#&@@y~RealDigits~2x^Reverse@Range[0,2~Log~y]];p[q_,c_,d_]:=Fold[#+##&,Reverse@CoefficientList[q[±c,±d]~PolynomialMod~±283,x]~Mod~2] (assumes that the source is encoded in ISO 8859-1) \$\endgroup\$ Commented Jun 15, 2016 at 7:51
  • \$\begingroup\$ @MartinEnder not quite sure how to implement your suggestion \$\endgroup\$
    – martin
    Commented Jun 15, 2016 at 9:32
  • \$\begingroup\$ @martin You can use it exactly like before, I've just used ± instead of f and p instead of o (of course you can keep that as o, I just used p so I could test both of them), and then saved a few more bytes with standard syntactic sugar tricks. \$\endgroup\$ Commented Jun 15, 2016 at 9:39
  • \$\begingroup\$ @MartinEnder can get ± to work same as f, but not p ... not sure where I am going wrong \$\endgroup\$
    – martin
    Commented Jun 15, 2016 at 10:35
  • \$\begingroup\$ If you copy it straight from the comment, there might be some unprintable characters wherever your browser displays the line break in the comment. Delete the characters around that position after copying and the retype them. If that doesn't do it, I'm not sure where the problem is.. \$\endgroup\$ Commented Jun 15, 2016 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.