Define a field with 256 elements

Question

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 pⁿ 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).

Answer 1

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

add:
    C5 F0 57 C0     # vxorps     xmm0, xmm1, xmm0
    C3              # ret
mul:
    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(2⁸), operating on a byte (field element) in the first source operand and the corresponding byte in a second source operand. The field GF(2⁸) is represented in polynomial representation with the reduction polynomial x⁸ + x⁴ + x³ + x + 1.

Answer 2

Python 2, 11 + 45 = 56 bytes

Addition (11 bytes):

int.__xor__

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:

a=int.__xor__
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))

Answer 3

JavaScript (ES6), 10 + 49 = 59 bytes

a=(x,y)=>x^y
m=(x,y,p=0)=>x?m(x>>1,2*y^283*(y>>7),p^y*(x&1)):p

Domain is 0 ... 255. Source.

Answer 4

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]

Testsuite:

=+  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)))
        ~
"ok"

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

20x148=229
61x189=143
111x239=181
163x36=29
193x40=1

Answer 5

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

PUBLIC @m@8
PUBLIC @a@8

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

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

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.

Answer 6

Mathematica 155 bytes

f[y_]:=Total[x^Reverse@Range[0,Log[2,y]]*RealDigits[y,2][[1]]];o[q_,c_,d_]:=FromDigits[Reverse@Mod[CoefficientList[PolynomialMod[q[f@c,f@d],f@283],x],2],2]

Implementation

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

addition check:

(*
  in: BitXor[202, 83]      out: 153
*)

More:

(*
  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.

Answer 7

Brainfuck, 28 characters

Fortunately, standard Brainfuck does everything modulo 256.

Addition: [->+<], assumes that the inputs are in the first two positions of the tape, places the output in position 0

Multiplication: [->[->+>+<<]>[-<+>]<<], assumes that the inputs are in the first two positions of the tape, places the output in position 3