Definieren Sie ein Feld mit 256 Elementen

14

Ein Feld in der Mathematik ist eine Menge von Zahlen, auf denen Additions- und Multiplikationsoperationen so definiert sind, dass sie bestimmte Axiome erfüllen (beschrieben in Wikipedia; siehe auch unten).

Ein endliches Feld kann p n -Elemente haben, wobei pes sich um eine Primzahl und neine natürliche Zahl handelt. Nehmen wir in dieser Herausforderung p = 2und n = 8und erstellen ein Feld mit 256 Elementen.

Die Elemente des Feldes sollten aufeinanderfolgende ganze Zahlen in einem Bereich liegen, enthält 0und 1:

  • -128 ... 127
  • 0 ... 255
  • oder irgendein anderer solcher Bereich

Definieren Sie zwei Funktionen (oder Programme, falls dies einfacher ist) a(x,y)für abstrakte "Addition" und m(x,y)für abstrakte "Multiplikation", so dass sie die Feldaxiome erfüllen:

  • Konsistenz: a(x,y)und m(x,y)erzeugen dasselbe Ergebnis, wenn sie mit denselben Argumenten aufgerufen werden
  • Closedness: Das Ergebnis von aund mist eine ganze Zahl im relevanten Bereich
  • Assoziativität: für jeden x, yund zin dem Bereich, a(a(x,y),z)gleich ist a(x,a(y,z)); das gleiche fürm
  • Kommutativität: für jede xund yim Bereich a(x,y)ist gleich a(y,x); das gleiche fürm
  • Distributivity: für jeden x, yund zim Bereich, m(x,a(y,z))ist gleicha(m(x,y),m(x,z))
  • Neutrale Elemente: für alle xim Bereich a(0,x)ist gleich xund m(1,x)gleichx
  • Negierung: für jede xim Bereich, gibt es solche , ydie a(x,y)ist0
  • Invers: für jede x≠0im Bereich gibt es solche , ydie m(x,y)ist1

Die Namen aund msind nur Beispiele; Sie können andere Namen oder unbenannte Funktionen verwenden. Die Punktzahl Ihrer Antwort ist die Summe der Byte-Längen für aund m.

Wenn Sie eine eingebaute Funktion verwenden, beschreiben Sie bitte auch in Worten, welches Ergebnis sie liefert (z. B. eine Multiplikationstabelle).

anatolyg
quelle
3
@LeakyNun "addition" ist hier nur eine abstrakte Operation, die die obigen Eigenschaften erfüllt. Es besteht keine Notwendigkeit a(2,1) = 3, die Sie haben könnten, a(2,1) = 5solange die obigen Axiome erfüllt sind. aMit dem üblichen Zusatz, den man zB aus dem Bereich der rationalen Zahlen kennt, muss man nichts anfangen.
Martin Ender
2
Ein kommutativer Ring ist trivial. Ein Feld ... nicht so einfach.
Neil
Stimmt etwas nicht a=+ m=×?
Adám
4
@ Adám Ja - 2 hätte keine Umkehrung, wennm=×
Sp3000
2
Related
Peter Taylor

Antworten:

4

Hoon , 22 Bytes

[dif pro]:(ga 8 283 3)

Hoon hat bereits eine Funktion ++ga, die Galois-Felder für die Verwendung in der AES-Implementierung erstellt. Dies gibt ein Tupel von zwei Funktionen zurück, anstatt zwei Programme zu verwenden.

Arbeitet in der Domäne [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"

Das Posten einer Multiplikationstabelle wäre gigantisch. Hier sind einige zufällige Testfälle:

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

Python 2, 11 + 45 = 56 Bytes

Zusatz (11 Bytes):

int.__xor__

Multiplikation (45 Byte):

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

Nimmt Eingabenummern in den Bereich [0 ... 255]. Addition ist nur bitweise XOR, Multiplikation ist Multiplikation von Polynomen mit Koeffizienten in GF2 mit russischen Bauern .

Und zur Kontrolle:

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
quelle
Einer von uns wird sich ändern müssen: P
Mego
@ Mego Hah, na ja ... Ich werde versuchen, andere Ansätze zu finden. Könnte schwer zu schlagen sein.
Sp3000
1
Auf welchem ​​Polynom basiert es?
Feersum
1
@LSpice Jetzt merke ich, dass ich das Polynom leicht finden kann, indem ich laufe m(2,128) was 27 = 283 - 256 ergibt, also sind Sie richtig und das Polynom ist x^8 + x^4 + x^3 + x + 1.
Feersum
1
@LSpice In Neils Antwort gibt er eine Wikipedia-Seite als Quelle für den Algorithmus an. Vielleicht hat das jeder gelesen. Aber es ist auf jeden Fall die naheliegendste Wahl für Codegolf, da es das kleinste irreduzible Polynom von Grad 8 in dieser Darstellung ist.
Feersum
6

JavaScript (ES6), 10 + 49 = 59 Byte

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 ist 0 ... 255. Quelle .

Neil
quelle
2
Sie sollten wahrscheinlich den Bereich angeben, den Sie verwenden.
Martin Ender
4

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

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

Benutzt das Neue GF2P8MULB Anweisung für Ice Lake-CPUs.

Der Befehl multipliziert Elemente im endlichen Feld GF (2 8 ), die mit einem Byte (Feldelement) im ersten Quelloperanden und dem entsprechenden Byte in einem zweiten Quelloperanden arbeiten. Das Feld GF (2 8 ) ist in Polynomdarstellung mit dem Reduktionspolynom x 8 + x 4 + x 3 + x + 1 dargestellt.

nwellnhof
quelle
1

IA-32 Maschinencode, 22 Bytes

"Multiplikation", 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

Dies streckt die Regeln ein wenig: Dem "Multiplikations" -Code fehlt der Funktionsexitcode; Es ist darauf angewiesen, dass sich der Zusatzcode unmittelbar danach im Speicher befindet, sodass er "durchfallen" kann. Ich habe es getan, um die Codegröße um 1 Byte zu verringern.

Quellcode (kann mlvon MS Visual Studio zusammengestellt werden):

    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

Der Algorithmus ist der Standard mit dem üblichen Polynom x^8 + x^4 + x^3 + x + 1, dargestellt durch die Hexadezimalzahl 1b. Der "Multiplikations" -Code akkumuliert das Ergebnis in edx. Wenn dies erledigt ist, gelangt es zum Additionscode, in den es verschoben wird eax(herkömmliches Register, um den Rückgabewert zu halten); die xormitecx ist ein no-op, da an dieser stelle ecxgelöscht wird.

Eine Besonderheit ist die Schleife. Anstatt auf Null zu prüfen

cmp ecx, 0
jne myloop

es verwendet die dedizierte loopAnweisung. Dieser Befehl verringert jedoch den Schleifen- "Zähler", bevor er mit 0 verglichen wird. Um dies zu kompensieren, erhöht der Code ihn, bevor er den loopBefehl verwendet.

anatolyg
quelle
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]

Implementierung

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

Zusatzprüfung:

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

Mehr:

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

NB Sollte in der Lage sein, {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}anstelle von 283.

martin
quelle
Hier sind 13 Bytes weniger: ±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](setzt voraus, dass die Quelle in ISO 8859-1 codiert ist)
Martin Ender,
@ MartinEnder nicht ganz sicher, wie Sie Ihren Vorschlag umsetzen
Martin
@martin Du kannst es genauso verwenden wie vorher, ich habe es nur ±anstelle von fund panstelle von verwendet o(natürlich kannst du das beibehalten, ich habe es nur verwendet o, pdamit ich beide testen kann) und dann ein paar weitere Bytes mit Standard gespeichert syntaktische Zuckertricks.
Martin Ender
@MartinEnder kann ±genauso arbeiten wie f, aber nicht p... nicht sicher, wo ich falsch liege
Martin
Wenn Sie es direkt aus dem Kommentar kopieren, sind möglicherweise einige nicht druckbare Zeichen vorhanden, wenn Ihr Browser den Zeilenumbruch im Kommentar anzeigt. Löschen Sie die Zeichen um diese Position nach dem Kopieren und geben Sie sie erneut ein. Wenn das nicht klappt, bin ich mir nicht sicher, wo das Problem liegt.
Martin Ender
-1

Brainfuck, 28 Zeichen

Glücklicherweise macht Standard Brainfuck alles modulo 256.

Zusatz: [->+<] voraus, dass sich die Eingänge an den ersten beiden Stellen des Bandes befinden, setzt den Ausgang auf Position 0

Multiplikation: Setzt [->[->+>+<<]>[-<+>]<<]voraus, dass sich die Eingänge an den ersten beiden Stellen des Bandes befinden, setzt den Ausgang an Position 3

ymbirtt
quelle