# Define a field with 256 elements

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

• @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. Jun 14 '16 at 7:41
• A commutative ring is trivial. A field... not so easy.
– Neil
Jun 14 '16 at 7:50
• Is there anything wrong with a=+ m=×?
Jun 14 '16 at 8:01
• @Adám Yes - 2 wouldn't have an inverse if m=× Jun 14 '16 at 8:02
• Related Jun 14 '16 at 9:48

## Python 2, 11 + 45 = 56 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))

• One of us is going to have to change :P
– user45941
Jun 14 '16 at 8:29
• @Mego Hah, well... I'll try and see if I can find any other approaches. Might be hard to beat though. Jun 14 '16 at 8:32
• Which polynomial is it based on? Jun 14 '16 at 18:56
• @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. Jun 14 '16 at 21:21
• @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. Jun 14 '16 at 21:29

## 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.

• You should probably specify the range you're using. Jun 14 '16 at 9:26

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

## 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


# 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


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.

# Mathematica 155 bytes

f[y_]:=Total[x^Reverse@Range[0,Log[2,y]]*RealDigits[y,2][]];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
*)


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

• 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) Jun 15 '16 at 7:51
• @MartinEnder not quite sure how to implement your suggestion Jun 15 '16 at 9:32
• @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. Jun 15 '16 at 9:39
• @MartinEnder can get ± to work same as f, but not p ... not sure where I am going wrong Jun 15 '16 at 10:35
• 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.. Jun 15 '16 at 11:13

# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8300811,"math_prob":0.9893626,"size":1859,"snap":"2021-43-2021-49","text_gpt3_token_len":555,"char_repetition_ratio":0.12560646,"word_repetition_ratio":0.042424243,"special_character_ratio":0.28617537,"punctuation_ratio":0.17312072,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9976546,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-22T06:24:13Z\",\"WARC-Record-ID\":\"<urn:uuid:1cb46b47-530f-41d7-8239-5902e58102ea>\",\"Content-Length\":\"253150\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:cba09149-86f4-4592-9856-a69501dadaed>\",\"WARC-Concurrent-To\":\"<urn:uuid:d8347209-d8dc-4ea4-a57a-a9b63d1461bc>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://codegolf.stackexchange.com/questions/82867/define-a-field-with-256-elements/82926\",\"WARC-Payload-Digest\":\"sha1:66S24ZNFCH5MARKWOVCJIGDCUM7XEY5F\",\"WARC-Block-Digest\":\"sha1:PP75LLQGNMWZTLKLHD5Z5RKYYGGI6STF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585460.87_warc_CC-MAIN-20211022052742-20211022082742-00365.warc.gz\"}"}