14
\$\begingroup\$

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

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

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

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))
\$\endgroup\$
  • \$\begingroup\$ One of us is going to have to change :P \$\endgroup\$ – Mego Jun 14 '16 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 Jun 14 '16 at 8:32
  • 1
    \$\begingroup\$ Which polynomial is it based on? \$\endgroup\$ – feersum Jun 14 '16 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 Jun 14 '16 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 Jun 14 '16 at 21:29
6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You should probably specify the range you're using. \$\endgroup\$ – Martin Ender Jun 14 '16 at 9:26
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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\$ – Martin Ender Jun 15 '16 at 7:51
  • \$\begingroup\$ @MartinEnder not quite sure how to implement your suggestion \$\endgroup\$ – martin Jun 15 '16 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\$ – Martin Ender Jun 15 '16 at 9:39
  • \$\begingroup\$ @MartinEnder can get ± to work same as f, but not p ... not sure where I am going wrong \$\endgroup\$ – martin Jun 15 '16 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\$ – Martin Ender Jun 15 '16 at 11:13
-1
\$\begingroup\$

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

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