Definir un campo con 256 elementos.

15

Un campo en matemáticas es un conjunto de números, con operaciones de suma y multiplicación definidas en él, de modo que satisfacen ciertos axiomas (descritos en Wikipedia; ver también a continuación).

Un campo finito puede tener p n elementos, donde pes un número primo y nes un número natural. En este desafío, tomemos p = 2y n = 8, entonces, hagamos un campo con 256 elementos.

Los elementos del campo deben ser enteros consecutivos en un rango que contenga 0y 1:

  • -128 ... 127
  • 0 ... 255
  • o cualquier otro rango

Defina dos funciones (o programas, si eso es más fácil), a(x,y)para la "suma" m(x,y)abstracta y para la "multiplicación" abstracta, de modo que satisfagan los axiomas del campo:

  • Consistencia: a(x,y)y m(x,y)produce el mismo resultado cuando se llama con los mismos argumentos
  • Cerrado: el resultado de ay mes un número entero en el rango relevante
  • Asociatividad: para cualquier x, yy zen el rango, a(a(x,y),z)es igual a a(x,a(y,z)); lo mismo param
  • Conmutatividad: para cualquiera xy yen el rango, a(x,y)es igual a a(y,x); lo mismo param
  • Distributividad: para cualquier x, yy zen el rango, m(x,a(y,z))es igual aa(m(x,y),m(x,z))
  • Elementos neutros: para cualquiera xen el rango, a(0,x)es igual a x, y m(1,x)es igual ax
  • Negación: para cualquiera xen el rango, existe tal yque a(x,y)es0
  • Inversa: para cualquiera x≠0en el rango, existe tal yque m(x,y)es1

Los nombres ay mson solo ejemplos; puede usar otros nombres o funciones sin nombre. La puntuación de su respuesta es la suma de las longitudes de bytes para ay m.

Si usa una función incorporada, describa también en palabras el resultado que produce (por ejemplo, proporcione una tabla de multiplicación).

anatolyg
fuente
3
La "adición" de @LeakyNun es solo una operación abstracta que satisface las propiedades anteriores. No hay necesidad de hacerlo a(2,1) = 3, a(2,1) = 5siempre y cuando se cumplan los axiomas anteriores. ano tiene que hacer nada con la adición habitual a la que está acostumbrado, por ejemplo, desde el campo de los números racionales.
Martin Ender
2
Un anillo conmutativo es trivial. Un campo ... no tan fácil.
Neil
¿Hay algo malo con esto a=+ m=×?
Adám
44
@ Adám Sí - 2 no tendría un inverso sim=×
Sp3000
2
Relacionado
Peter Taylor

Respuestas:

4

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

Utiliza la nueva GF2P8MULBinstrucción en las CPU de Ice Lake.

La instrucción multiplica elementos en el campo finito GF (2 8 ), operando en un byte (elemento de campo) en el primer operando fuente y el byte correspondiente en un segundo operando fuente. El campo GF (2 8 ) se representa en representación polinómica con el polinomio de reducción x 8 + x 4 + x 3 + x + 1.

nwellnhof
fuente
13

Python 2, 11 + 45 = 56 bytes

Adición (11 bytes):

int.__xor__

Multiplicación (45 bytes):

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

Toma los números de entrada en el rango [0 ... 255]. La suma es simplemente XOR bit a bit, la multiplicación es la multiplicación de polinomios con coeficientes en GF2 con campesinos rusos .

Y para verificar:

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))
Sp3000
fuente
Uno de nosotros tendrá que cambiar: P
Mego
@Mego Hah, bueno ... Trataré de ver si puedo encontrar otros enfoques. Sin embargo, podría ser difícil de superar.
Sp3000
1
¿En qué polinomio se basa?
feersum
1
@LSpice Ahora me doy cuenta de que puedo encontrar fácilmente el polinomio ejecutando lo m(2,128)que resulta en 27 = 283 - 256, por lo que está correcto y el polinomio es x^8 + x^4 + x^3 + x + 1.
feersum
1
@LSpice En la respuesta de Neil, él da una página de Wikipedia como fuente del algoritmo, así que tal vez todos lo lean. Pero de todos modos es la opción más obvia para el golf de código, ya que es el polinomio irreducible más pequeño de grado 8 en esta representación.
feersum
6

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

El dominio es 0 ... 255. Fuente .

Neil
fuente
2
Probablemente debería especificar el rango que está utilizando.
Martin Ender
4

Hoon , 22 bytes

[dif pro]:(ga 8 283 3)

Hoon ya tiene una función ++gaque crea Galois Fields, para usar en la implementación de AES. Esto devuelve una tupla de dos funciones, en lugar de usar dos programas.

Opera en el dominio [0...255]

Banco de pruebas:

=+  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"

Publicar una tabla de multiplicar sería gigantesco, así que aquí hay algunos casos de prueba al azar:

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

Código de máquina IA-32, 22 bytes

"Multiplicación", 18 bytes:

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

"Adición", 4 bytes:

92 33 c1 c3

Esto estira las reglas un poco: el código de "multiplicación" carece de código de salida de función; se basa en el código de "adición" que está en la memoria inmediatamente después, por lo que puede "caerse". Lo hice para disminuir el tamaño del código en 1 byte.

Código fuente (puede ser ensamblado por mlMS 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

El algoritmo es el estándar, involucrando el polinomio usual x^8 + x^4 + x^3 + x + 1, representado por el número hexadecimal 1b. El código de "multiplicación" acumula el resultado en edx. Cuando se hace, pasa al código de adición, que lo mueve a eax(registro convencional para mantener el valor de retorno); el xorwith ecxes un no-op, porque en ese punto ecxse borra.

Una característica peculiar es el bucle. En lugar de verificar cero

cmp ecx, 0
jne myloop

Utiliza la loopinstrucción dedicada . Pero esta instrucción disminuye el "contador" del bucle antes de compararlo con 0. Para compensar esto, el código lo aumenta antes de usar la loopinstrucción.

anatolyg
fuente
0

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]

Implementación

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

verificación de adición:

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

Más:

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

NB Debe poder usar cualquiera de {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}en lugar de 283.

martín
fuente
Bueno, aquí hay 13 bytes menos: ±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](se supone que la fuente está codificada en ISO 8859-1)
Martin Ender
@MartinEnder no está muy seguro de cómo implementar su sugerencia
martin
@martin Puedes usarlo exactamente como antes, acabo de usarlo en ±lugar de fy en plugar de o(por supuesto, puedes guardarlo como o, solo lo usé ppara poder probarlos a ambos), y luego guardé algunos bytes más con el estándar trucos de azúcar sintácticos.
Martin Ender
@MartinEnder puede ponerse ±a trabajar igual que f, pero no p... no estoy seguro de dónde me estoy equivocando
martin
Si lo copia directamente del comentario, puede haber algunos caracteres no imprimibles donde su navegador muestre el salto de línea en el comentario. Elimine los caracteres alrededor de esa posición después de copiar y vuelva a escribirlos. Si eso no lo hace, no estoy seguro de dónde está el problema ...
Martin Ender
-1

Brainfuck, 28 personajes

Afortunadamente, Brainfuck estándar hace todo el módulo 256.

Adición: [->+<]supone que las entradas están en las dos primeras posiciones de la cinta, coloca la salida en la posición 0

Multiplicación: [->[->+>+<<]>[-<+>]<<]supone que las entradas están en las dos primeras posiciones de la cinta, coloca la salida en la posición 3

ymbirtt
fuente