Beweisen, dass ein russischer kryptografischer Standard zu strukturiert ist

92

Das Ziel dieser Herausforderung ist es, eine unglaublich kurze Implementierung der folgenden Funktion pin der Sprache Ihrer Wahl zu finden. Hier ist C-Code, der es implementiert (siehe diesen TIO-Link , der auch seine Ausgaben druckt) und eine Wikipedia-Seite, die es enthält.

unsigned char pi[] = {
    252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,
    233,119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,
    249,24,101,90,226,92,239,33,129,28,60,66,139,1,142,79,
    5,132,2,174,227,106,143,160,6,11,237,152,127,212,211,31,
    235,52,44,81,234,200,72,171,242,42,104,162,253,58,206,204,
    181,112,14,86,8,12,118,18,191,114,19,71,156,183,93,135,
    21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,177,
    50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,
    223,245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,
    224,15,236,222,122,148,176,188,220,232,40,80,78,51,10,74,
    167,151,96,115,30,0,98,68,26,184,56,130,100,159,38,65,
    173,69,70,146,39,94,85,47,140,163,165,125,105,213,149,59,
    7,88,179,64,134,172,29,247,48,55,107,228,136,217,231,137,
    225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,97,
    32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,
    89,166,116,210,230,244,180,192,209,102,175,194,57,75,99,182,
};

unsigned char p(unsigned char x) {
     return pi[x];
}

Was ist p

pist Bestandteil zweier russischer kryptographischer Standards, nämlich der Hash-Funktion Streebog und der Blockchiffre Kuznyechik . In diesem Artikel (und während ISO-Meetings) behaupteten die Entwickler dieser Algorithmen, dass sie das Array pidurch Auswahl zufälliger 8-Bit-Permutationen generierten .

"Unmögliche" Implementierungen

Es gibt Permutationen auf 8 Bits. Für eine gegebene zufällige Permutation wird daher nicht erwartet, dass ein Programm, das sie implementiert, weniger als 1683 Bits benötigt.256!21684

Wir haben jedoch mehrere ungewöhnlich kleine Implementierungen gefunden (die wir hier auflisten ), zum Beispiel das folgende C-Programm:

p(x){unsigned char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",l=0,b=17;while(--l&&x^1)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

die nur 158 Zeichen enthält und somit in 1264 Bit passt. Klicken Sie hier, um zu sehen, dass es funktioniert.

Wir sprechen von einer "unmöglich" kurzen Implementierung, da, wenn die Permutation die Ausgabe eines zufälligen Prozesses wäre (wie von seinen Designern behauptet), ein Programm dieser kurzen Art nicht existieren würde (siehe diese Seite für weitere Details).

Referenzimplementierung

Eine besser lesbare Version des vorherigen C-Codes ist:

unsigned char p(unsigned char x){
     unsigned char
         s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
         k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
     if(x != 0) {
         unsigned char l=1, a=2;
         while(a!=x) {
             a=(a<<1)^(a>>7)*29;
             l++;
         }
         unsigned char i = l % 17, j = l / 17;
         if (i != 0) return 252^k[i]^s[j];
         else return 252^k[j];
     }
     else return 252;
}

Die Tabelle kist so, dass k[x] = L(16-x), wo Lin dem Sinne linear ist L(x^y)==L(x)^L(y), und wo, wie in C, ^das XOR bezeichnet. Es ist uns jedoch nicht gelungen, diese Eigenschaft zu nutzen, um unsere Implementierung zu verkürzen. Wir kennen keine Struktur s, die eine einfachere Implementierung ermöglichen könnte - ihre Ausgabe befindet sich jedoch immer im Unterfeld, dh wobei die Exponentiation im endlichen Feld erfolgt. Natürlich steht es Ihnen frei, einen einfacheren Ausdruck zu verwenden, falls Sie einen finden sollten!s[x]16=s[x]s

Die while-Schleife entspricht der Auswertung eines diskreten Logarithmus im endlichen Feld mit 256 Elementen. Es funktioniert über eine einfache Brute-Force-Suche: Die Dummy-Variable awird als Generator des endlichen Feldes festgelegt und mit diesem Generator multipliziert, bis das Ergebnis gleich ist x. Wenn dies der Fall ist, haben wir ldas diskrete Protokoll von x. Diese Funktion ist nicht in 0 definiert, daher der der ifAnweisung entsprechende Sonderfall .

Die Multiplikation mit dem Generator kann als Multiplikation mit in die dann modulo des Polynoms reduziert wird . Die Aufgabe von ist es sicherzustellen, dass die Variable auf 8 Bits bleibt. Alternativ könnten wir verwenden , in welchem ​​Fall ein (oder ein anderer ganzzahliger) Typ sein könnte. Auf der anderen Seite ist es notwendig, mit zu beginnen, da wir haben müssen, wann gleich 1 ist.XF2[X]X8+X4+X3+X2+1unsigned charaa=(a<<1)^(a>>7)*(256^29)aintl=1,a=2l=255x

Weitere Details zu den Eigenschaften von pfinden Sie in unserem Artikel, in dem die meisten Optimierungen beschrieben werden, um die vorherige kurze Implementierung zu erhalten.

Regeln

Schlagen Sie ein Programm vor, das die Funktion pin weniger als 1683 Bit implementiert . Je kürzer das Programm ist, desto anormaler ist es, je kürzer die Sprache ist, desto besser. Wenn Ihre Sprache Kuznyechik, Streebog oder pein eingebautes hat, können Sie sie nicht verwenden.

Die Metrik, mit der wir die beste Implementierung ermitteln, ist die Programmlänge in Byte. Wir verwenden die Bitlänge in unserer wissenschaftlichen Arbeit, aber der Einfachheit halber halten wir uns hier an Bytes.

Wenn Ihre Sprache nicht über eine klare Vorstellung von Funktion, Argument oder Ausgang, ist die Codierung an Ihnen zu definieren, aber Tricks wie kodieren den Wert pi[x]als xoffensichtlich verboten.

Wir haben bereits ein Forschungspapier mit unseren Ergebnissen zu diesem Thema eingereicht. Es ist hier erhältlich . Sollte es jedoch an einem wissenschaftlichen Ort veröffentlicht werden, werden wir gerne die Autoren der besten Implementierungen auszeichnen.

Übrigens, danke an xnor für seine Hilfe beim Verfassen dieser Frage!

picarresursix
quelle
12
Ich hoffe jemand gibt eine Antwort in Seed.
Robin Ryder
6
Kann Brainfuck-Code zum Beispiel mit 3 Bits pro Zeichen bewertet werden, wenn er keine Nops hat? Und ist das 1683 bits at mosteine strenge Einschränkung oder das Ziel?
Jemand
31
" Wenn die Permutation die Ausgabe eines zufälligen Prozesses wäre (wie von seinen Designern behauptet), gäbe es kein so kurzes Programm ", widerspreche ich (obwohl es für die Herausforderung keine Rolle spielt). Wenn es sich um die Ausgabe eines zufälligen Prozesses handeln würde, wäre es unwahrscheinlich, dass ein solches Programm existiert. oder es wäre schwer zu finden
Luis Mendo
8
@Grimy Die Aussage, dass ein Programm, das so kurz wäre, nicht existieren würde, ist eine konzeptionelle (keine programmierende). Mit Ihren Begriffen gehört es zur Welt der reinen Mathematik, nicht zur Programmierwelt
Luis Mendo,
7
Es wurde möglicherweise bereits bemerkt, aber nur für den Fall: ergibt nur 8 verschiedene Werte: (beginnend mit und unter der Annahme von ) . 1 , 10 , 68 , 79 , 146 , 153 , 220 , 221 i = 1 s 0 = 0si XOR si11,10,68,79,146,153,220,221i=1s0=0
Arnauld

Antworten:

35

AMD64-Assembly (78 Byte oder 624 Bit Maschinencode)

uint8_t SubByte (uint8_t x) {
    uint8_t y, z;
    uint8_t s [] =
      {1,221,146,79,147,153,11,68,214,215,78,220,152,10,69};

    uint8_t k [] =
      {0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};

    if (x) {
      für (y = z = 1; (y = (y << 1) ^ ((y >> 7) * 29))! = x; z ++);
      x = (z% 17);
      z = (z / 17);
      x = (x)? k [x] ^ s [z]: k [z];
    }
    return x ^ 252;
}

64-Bit x86-Assembly

    ; 78 Bytes AMD64-Assembly
    ; odzhan
    Bits 64

    % ifndef BIN
      globaler SubBytex
    % endif

SubBytex:
    mov al, 252
    jecxz L2; if (x) {
    rufe L0 an
k:
    db 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde, 
    db 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
s:
    db 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44, 
    db 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
L0:
    Pop rbx
    mov al, 1; y = 1
    cdq; z = 0
L1:
    inc dl; z ++
    add al, al; y = y + y
    jnc $ + 4; XOR überspringen, wenn kein Übertrag vorhanden ist
    xor al, 29;
    cmp al, cl; if (y! = x) gehe zu L1
    jne L1    

    xchg eax, edx; eax = z
    cdq; edx = 0
    mov cl, 17; al = z / 17, dl = z% 17
    div ecx

    mov cl, [rbx + rax + 17]; cl = s [z]
    xlatb; al = k [z]
    Test dl, dl; if (x == 0) gehe zu L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    ret

Zerlegter 64-Bit-Code

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 qword 0x2a aufrufen
; k [] = 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde,
; 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
; s [] = 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44,
; 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
0000002A 5B pop rbx
0000002B B001 Mov al, 0x1
0000002D 99 cdq
0000002E FEC2 inc dl
00000030 00C0 add al, al
00000032 7302 jnc 0x36
00000034 341D xor al, 0x1d
00000036 38C8 cmp al, cl
00000038 75F4 jnz 0x2e
0000003A 92 xchg eax, edx
0000003B 99 cdq
0000003C B111 mov cl, 0x11
0000003E F7F1 div ecx
00000040 8A4C0311 mov cl, [rbx + rax + 0x11]
00000044 D7 xlatb
00000045 84D2 Test dl, dl
00000047 7404 jz 0x4d
00000049 92 xchg eax, edx
0000004A D7 xlatb
0000004B 30C8 xor al, cl
0000004D C3 ret

32-Bit-x86-Assembly

    ; 72 Byte x86-Assembly
    ; odzhan
    Bits 32

    % ifndef BIN
      globaler SubBytex
      global _SubBytex
    % endif

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; if (x) {
    rufe L0 an
k:
    db 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde, 
    db 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
s:
    db 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44, 
    db 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
L0:
    Pop ebx
    mov al, 1; y = 1
    cdq; z = 0
L1:
    inc edx; z ++
    add al, al; y = y + y
    jnc $ + 4; XOR überspringen, wenn kein Übertrag vorhanden ist
    xor al, 29;
    cmp al, cl; if (y! = x) gehe zu L1
    jne L1    
    xchg eax, edx; al = z
    aam 17; al | x = z% 17, ah | z = z / 17
    mov cl, ah; cl = z
    cmove eax, ecx; if (x == 0) al = z else al = x
    xlatb; al = k [z] oder k [x]
    jz L2; if (x == 0) gehe zu L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    ret

Zerlegter 32-Bit-Code

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 dword 0x29 aufrufen
; k [] = 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde,
; 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
; s [] = 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44,
; 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
00000029 5B Pop ebx
0000002A B001 Mov al, 0x1
0000002C 99 cdq
0000002D 42 inc edx
0000002E 00C0 add al, al
00000030 7302 jnc 0x34
00000032 341D xor al, 0x1d
00000034 38C8 cmp al, cl
00000036 75F5 jnz 0x2d
00000038 92 xchg eax, edx
00000039 D411 aam 0x11
0000003B 88E1 mov cl, ah
0000003D 0F44C1 cmovz eax, ecx
00000040 D7 xlatb
00000041 7404 jz 0x47
00000043 32440B11 xor al, [ebx + ecx + 0x11]
00000047 C3 ret
odzhan
quelle
1
Gute Antwort! Da das OP nach der Anzahl der Bits gesucht hat, ergibt dies (85 Byte) 680 Bit , wobei 8 Bit pro Byte verwendet werden, oder 595 Bit, wobei 7 Bit pro Byte verwendet werden (möglich, da alle Zeichen ASCII-Zeichen sind). Sie könnten wahrscheinlich kürzer werden, wenn Sie auf einen noch restriktiveren Zeichensatz komprimiert würden.
Cullub
1
Willkommen bei PPCG; schöne erste lösung.
Shaggy
9
@Cullub Mein Punkt war, dass der Code in dieser Antwort nur C / Assembler ist, der kompiliert wird, daher ist die Byteanzahl nicht die des angegebenen Codes, sondern des kompilierten Codes. Und das ist kein ASCII.
ArBo
7
Nur zur Verdeutlichung sind die 84 Bytes die Größe des Maschinencodes, nachdem dieser zusammengestellt wurde? In diesem Fall sollte der Titel aktualisiert werden, um darauf hinzuweisen, dass es sich um eine Maschinencode-Antwort und nicht um eine Assembly-Antwort handelt.
Potato44
1
Übrigens müssen Sie keine Standard-Anrufkonvention verwenden. Sie können eine benutzerdefinierte Konvention verwenden, bei der RBX überlastet ist und 2 Bytes für Push / Pop spart. (Und wo uint8_tArgs für JRCXZ auf 64-Bit erweitert werden). Wenn Sie einen positionsabhängigen Code schreiben, können Sie die Tabellenadresse auch in ein Register mit einem 5-Byte-Wert mov ebx, imm32anstelle eines 6-Byte-Werts call/ einfügen pop. Oder benutze es als disp32in mov al, [table + rax], aber das könnte verlieren, da du schon zwei xlatbund ein hast mov. Der Call + Pop-Shellcode-Trick gewinnt gegenüber dem 7-Byte-RIP-relativen LEA mit den Daten nach dem ret.
Peter Cordes
23

CJam ,72 67 66 63 Bytes

ri{_2md142*^}es*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD�’
˜×EO“N".*Lts:^i

es* wiederholt etwas durch den aktuellen Zeitstempel, der eine große Zahl ist, und es würde zu lange dauern, um fertig zu werden.

Aktuell testbare Version, 64 Bytes:

ri{_2md142*^}256*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD�’
˜×EO“N".*Lts:^i
00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22dd 3024 2612 dc99 d644 0092 0b0a  2b".0$&....D....
00000030: 98d7 454f 934e 0122 2e2a 4c74 733a 5e69  ..EO.N.".*Lts:^i

Probieren Sie es online!

Probiere alles online aus!

Um diesen Code auszuführen (auf einem Linux - Rechner), müssen Sie die Zeile hinzufügen en_US.ISO-8859-1 ISO-8859-1in /etc/locale.genund laufen locale-gen. Dann könnten Sie verwenden:

LANG=en_US.ISO-8859-1 java -jar cjam.jar <source file>

Oder versuchen Sie diese äquivalente 72-Byte-UTF-8-Version:

00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22c3 9d30 2426 12c3 9cc2 99c3 9644  2b"..0$&.......D
00000030: 00c2 920b 0ac2 98c3 9745 4fc2 934e 0122  .........EO..N."
00000040: 2e2a 4c74 733a 5e69                      .*Lts:^i

Erläuterung

ri               e# Read input.
{_2md142*^}      e# Copy and divide by 2. If remainder is 1, xor 142.
es*]             e# Repeat a lot of times and wrap all results in an array.
2#               e# Find the first occurrence of 2, -1 if not found.
~                e# Increment and negate.
Hmd              e# Divmod 17. Both the quotient and remainder would be negated.
{5\}e|           e# If remainder = 0, return 5, quotient instead.
Fm2b             e# Subtract 15 from the remainder and expand in base 2.
                 e# In CJam, base conversion only applies to the absolute value.
"...".*          e# Filter 221, 48, 36, 38, 18 by the bits.
                 e# 221, the characters after 18
                 e#   and 18 itself in case quotient - 15 = -15 won't change.
Lt               e# Remove the item s[quotient] xor 220.
                 e# Quotient is 0, 5 or a negative integer from the end,
                 e#   which doesn't overlap with the previously filtered items.
s                e# Flatten, because some characters become strings after the process.
:^i              e# Reduce by xor and make sure the result is an integer.

Die Zeichen in der Zeichenfolge sind:

  • 221. Siehe unten.
  • 48, 36, 38, 18. Es ist die lineare Zerlegung von k auf der Grundlage der Eigenschaften von L in der Frage.
  • 220 ist der Füllwert des Arrays s, wenn nur das Array k verwendet wird.
  • Array s xor 220 ist umgekehrt, mit Ausnahme des letzten Elements oder des ersten Elements vor der Umkehrung, d. H. 221 am Anfang der Zeichenfolge.
jimmy23013
quelle
Was würdest du mit Strom machen? PS: Ich werde wahrscheinlich den Trick stehlen, die Finite-Feld-Operation in umgekehrter Reihenfolge durchzuführen. Sehr gepflegt.
Peter Taylor
@PeterTaylor Sie können Array k mit dem Potenzsatz [48 36 38 18] (oder umgekehrt) mit der einfachsten Reihenfolge erhalten und jeweils um x oder reduzieren. In den Golfsprachen, die bisher in dieser Frage verwendet wurden, hatte nur 05AB1E die richtige Reihenfolge. Jelly und Stax hatten anscheinend eine andere Vorstellung davon, was ich für unkompliziert hielt.
Jimmy23013
Ich bin gerade dabei, Ihre Antwort auf 05AB1E abzuspielen. Was sind die ganzzahligen Werte für Ihre Zeichenfolge "Ý0$&Ü™ÖD�’\n˜×EO“N"?
Kevin Cruijssen
@ KevinCruijssen Fragen Sie, was sie bedeuteten, oder ihre numerischen Werte (die Sie aus dem Hex-Dump sehen konnten)?
Jimmy23013
@ jimmy23013 Ah, natürlich .. Ich habe den Hex-Dump vergessen ..
Kevin Cruijssen
19

Jelly 71 59 Bytes

H^142ƊHḂ?Ƭi2d17U⁸⁴;$Ḣ?$CµṪạ⁴B¬T;;6ị“Œ0$&ØŀWð⁺Ṫ\ḢĠVı⁻¹]°Ẇ‘^/

Probieren Sie es online!

Überprüfen Sie alle Möglichkeiten

Jetzt neu geschrieben eine überarbeitete Version mit Antwort jimmy23013 cleveren CJam so sicher sein , auch , dass man upvote! Verwendet nur 472 Bit (28,0% des naiven Ansatzes). @ jimmy23013 hat auch ein weiteres Byte gespeichert!

Erläuterung

Bühne 1

         Ƭ        | Repeat the following until no new entries:
       Ḃ?         | - If odd:
     Ɗ            |   - Then following as a monad:
H                 |     - Halve
 ^142             |     - Xor 142
      H           |   - Else: Halve
          i2      | Index of 2 in this list

Stufe 2

d17           | Divmod 17
          $   | Following as a monad:
   U          | - Reverse order
        Ḣ?    | - If head (remainder from divmod) non-zero:
    ⁸         |   - Then: left argument [quotient, remainder]
     ⁴;$      |   - Else: [16, quotient]
           C  | Complement (1 minus)
            µ | Start a new monadic chain

Stufe 3

Ṫ                   | Tail (Complement of remainder or quotient from stage 2)
 ạ⁴                 | Absolute difference from 16
   B                | Convert to binary
    ¬               | Not
     T              | Indices of true values
      ;             | Concatenate (to the other value from stage 2)
       ;6           | Concatenate to 6
         ị“Œ...Ẇ‘   | Index into [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]
                 ^/ | Reduce using xor

Ursprünglicher Ansatz

Jelly , 71 66 Bytes

H^142ƊHḂ?Ƭi2d:j@“ÐḌ‘ɗ%?17ị"“p?Ä>4ɼḋ{zẉq5ʂċ¡Ḅ“`rFTDVbpPBvdtfR@‘^ƒ17

Probieren Sie es online!

Überprüfen Sie alle Möglichkeiten

Ein monadischer Link oder ein vollständiges Programm, das ein einzelnes Argument verwendet und den relevanten Wert von zurückgibt pi[x]. Das sind 536 Bit, also weniger als ein Drittel der naiven Speicherung von pi.

3 Bytes gespart, indem die Methode zum Finden laus der CJam-Antwort von jimmy23013 verwendet wurde. Stellen Sie also sicher, dass Sie auch diese positiv bewerten!

Erläuterung

Bühne 1

         Ƭ        | Repeat the following until no new entries:
       Ḃ?         | - If odd:
     Ɗ            |   - Then following as a monad:
H                 |     - Halve
 ^142             |     - Xor 142
      H           |   - Else: Halve
          i2      | Index of 2 in this list

Stufe 2

         %?17  | If not divisible by 17
d              | - Then divmod 17
        ɗ      | - Else following as a dyad (using 17 as right argument)
 :             |   - Integer divide by 17
  j@“ÐḌ‘       |   - Join the list 15,173 by the quotient

Stufe 3

ị"“p...Ḅ“`...@‘     | Index into two compressed lists of integers using the output from stage 2 (separate list for each output from stage 2). The third output from stage 2 will be left untouched
               ^ƒ17 | Finally reduce using Xor and 17 as the first argument
Nick Kennedy
quelle
1
59 Bytes , eine andere Version .
Jimmy23013
15

C (gcc) , 157 148 140 139 Bytes

Bescheidene Verbesserung gegenüber dem C-Beispiel.

l,b=17,*k=L"@`rFTDVbpPBvdtfR@";p(x){for(l=256;--l*~-x;)x=2*x^x/128*285;return l%b?k[l%b]^"\xcer?\4@6\xc8\t{|\3q5\xc7\n"[l/b]-b:k[l/b]^188;}

Probieren Sie es online!

C (GCC) , 150 142 127 126 Bytes

Dieser hängt von den Macken von gcc und x86 und UTF-8 ab.

l,*k=L"@`rFTDVbpPBvdtfR@";p(x){for(l=256;--l*~-x;)x=2*x^x/128*285;x=l%17?k[l%17]^L"½a.ó/%·øjkò`$¶ù"[l/17]:k[l/17]^188;}

Probieren Sie es online!

Vielen Dank an @XavierBonnetain für -1 und weniger undefiniertes Verhalten.

Ceilingcat
quelle
10

05AB1E , 101 100 98 97 95 94 Bytes

U•α">η≠ε∍$<Θγ\&@(Σα•₅вV₁[<ÐX*Q#X·₁%Xžy÷Ƶ¹*₁%^₁%U}D17©%DĀiYsès®÷•¾#kôlb¸ù,-ó"a·ú•₅вë\Ƶ∞s®÷Y}sè^

-3 Bytes dank @Grimy .

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

Port von Xavier Bonnetains C-Funktion (1106-Bit-Version) mit der gleichen Verbesserung, die @ceilingcat in seiner C-Antwort vorgenommen hat , um 3 Bytes zu sparen.

U                    # Store the (implicit) input in variable `X`
•α">η≠ε∍$<Θγ\&@(Σα• "# Push compressed integer 20576992798525946719126649319401629993024
 ₅в                  # Converted to base-255 as list:
                     #  [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]
   V                 # Pop and store this list in variable `Y`
                    # Push `i` = 256
 [                   # Start an infinite loop:
  <                  #  Decrease `i` by 1
   Ð                 #  Triplicate `i`
    X*Q              #  If `i` multiplied by `X` is equal to `i` (i==0 or X==1):
       #             #   Stop the infinite loop
  X·₁%               #  Calculate double(`X`) modulo-256
                     #  (NOTE: all the modulo-256 are to mimic an unsigned char in C)
  Xžy÷               #  Calculate `X` integer-divided by builtin integer 128,
      Ƶ¹*            #  multiplied by compressed integer 285,
         ₁%          #  modulo-256
  ^                  #  Bitwise-XOR those together
   ₁%                #  And take modulo-256 again
  U                  #  Then pop and store it as new `X`
 }D                  # After the loop: Duplicate the resulting `i`
   17©               # Push 17 (and store it in variable `®` without popping)
      %              # Calculate `i` modulo-17
       D             # Duplicate it
        Āi           # If it's NOT 0:
          Ysè        #  Index the duplicated `i` modulo-17 into list `Y`
          s®÷        #  Calculate `i` integer-divided by 17
          •¾#kôlb¸ù,-ó"a·ú•
                    "#  Push compressed integer 930891775969900394811589640717060184
           ₅в        #  Converted to base-255 as list:
                     #   [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]
         ë           # Else (`i` == 0):
          \          #  Discard the duplicated `i` modulo-17, since we don't need it
          Ƶ∞         #  Push compressed integer 188
          s®÷        #  Calculate `i` integer-divided by 17
          Y          #  Push list `Y`
         }s          # After the if-else: swap the integer and list on the stack
           è         # And index the `i` modulo/integer-divided by 17 into the list
            ^        # Then Bitwise-XOR the top two together
                     # (after which the top of the stack is output implicitly as result)

Sehen Sie sich meinen Tipp 05AB1E an (Abschnitte Wie komprimiere ich große Ganzzahlen? Und Wie komprimiere ich Ganzzahlenlisten? ) , Um zu verstehen, warum dies so •α">η≠ε∍$<Θγ\&@(Σα•ist 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅вist [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹ist 285; •¾#kôlb¸ù,-ó"a·ú•ist 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅вist [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; und Ƶ∞ist 188.

Kevin Cruijssen
quelle
@Grimy Danke, ich habe diese Art von Golf immer mit den komprimierten Integer-Listen vergessen ''.)
Kevin Cruijssen
Hoppla, entschuldige die durcheinandergebrachte Formatierung. Ich weiß, wie man Backticks verdoppelt, aber ich wusste nicht, dass die komprimierte Liste einen Backtick enthält. Auch: s^=> ^(XOR ist kommutativ). Ist das nicht s^_dasselbe wie Q?
Schmutziger
@ Grimy Danke! Du hast in der Tat recht. Wir prüfen im Grunde , wenn Sie eine der folgenden drei Dinge truthy ist die Schleife verlassen: i==0 || X==0 || X==1.
Kevin Cruijssen
10

Stax , 65 64 62 59 58 Bytes

ç∙¼≥2▼Uó╤áπ╙º┐╩♫∟öv◘≥δ♦Θ╫»─kRWÑâBG")≥ö0╥kƒg┬^S ΔrΩ►╣Wü Ü╕║

Führen Sie es aus und debuggen Sie es

Leider verwendet dieses Programm einige Anweisungen, die intern einige veraltete stax-Anweisungen verwenden. Ich habe nur vergessen, ihre Implementierung zu aktualisieren. Dies führt dazu, dass eine falsche Warnung angezeigt wird, die Ergebnisse jedoch immer noch korrekt sind.

Dies ist inspiriert von jimmy23013s exzellenter Antwort . Einige Teile wurden geändert, um besser zu stax zu passen.

In druckbarem ASCII geschriebene Stax-Programme haben eine alternative Darstellung, die etwas mehr als 1 Bit pro Byte speichert, da nur 95 druckbare ASCII-Zeichen vorhanden sind.

Hier ist die ASCII-Darstellung dieses Programms, die für "Lesbarkeit" mit Kommentaren formatiert ist.

{                       begin block
  2|%142*S              given n, calculate (n/2)^(n%2*142)
                         - this seems to be the inverse of the operation in the while loop
gu                      use block to generate distinct values until duplicate is found
                         - starting from the input; result will be an array of generated values
2I^                     1-based index of 2 in the generated values
17|%                    divmod 17
c{Us}?                  if the remainder is zero, then use (-1, quotient) instead
~                       push the top of the main stack to the input stack for later use
"i1{%oBTq\z^7pSt+cS4"   ascii string literal; will be transformed into a variant of `s`
./o{H|EF                interpret ascii codes as base-94 integer
                         - this is tolerant of digits that exceed the base
                        then encode big constant as into base 222 digits
                         - this produces an array similar to s
                         - 0 has been appended, and all elements xor 220
@                       use the quotient to index into this array
"jr+R"!                 packed integer array literal [18, 38, 36, 48]
F                       for each, execute the rest of the program
  ;                     peek from the input array, stored earlier
  v                     decrement
  i:@                   get the i-th bit where i is the iteration index 0..3
  *                     multiply the bit by value from the array literal
  S                     xor with result so far
                        after the loop, the top of the stack is printed implicitly

Führen Sie dieses aus

Geänderte Version für alle Eingänge 0..255

rekursiv
quelle
Stax hat Sfür Leistung gesorgt. Sie könnten den Potenzsatz von [18 38 36 48] erhalten, indexieren und durch xor reduzieren. (Ich kenne Stax nicht und ich bin mir nicht sicher, ob es kürzer sein würde.)
jimmy23013
Ich denke, die Bestellung von stax für Teilmengen, die vom SBetreiber erstellt wurden, ist nicht in der richtigen Reihenfolge, damit dies funktioniert. Beispiel "abc"SJ(Powerset von "ABC" mit Räumen verbunden ist ) erzeugt "ein abc ac b bc c ab".
rekursiver
8

Python 3 , 151 Bytes

f=lambda x,l=255,k=b'@`rFTDVbpPBvdtfR@':f(x*2^x//128*285,l-1)if~-x*l else[k[l%17]^(0x450a98dc4ed7d6440b99934f92dd01>>l//17*8&255),k[l//17]][l%17<1]^188

Probieren Sie es online!

Eine Funktion, die die Permutation implementiert. Der Code verwendet nur 7-Bit-ASCII-Zeichen.

Codiert kals Python 3-Bytestring, verschoben ^64in den druckbaren Bereich. Im Gegensatz dazu swird als Basis 256 Ziffern einer numerischen Konstante codiert und die Ziffern werden als extrahiert [number]>>[shift]*8&255. Dies war kürzer als die Codierung sin einer Zeichenfolge, da dies eine Anzahl von Escape-Zeichen erforderte, selbst bei einer optimalen Verschiebung, um diese ^160zu minimieren.

Die Berechnung des diskreten Protokolls erfolgt rückwärts. Das Update durchläuft eine x=x*2^x//128*285Schleife in der zyklischen Gruppe, indem es das Multiplizieren mit dem Erzeuger simuliert, bis es die Identität erreicht x=1. Wir beginnen das diskrete Protokoll bei l=255(der Zykluslänge) und dekrementieren es bei jeder Iteration. Um den x=0Fall zu behandeln und es nicht für immer zu schleifen, beenden wir auch wann l=0, wodurch die x=0Zuordnung zu l=0wie angegeben erfolgt.


Python 2 verliert, weil es keine netten Bytestrings gibt, also müssen wir es tun map(ord,...)(ArBo hat hier ein Byte gespeichert). Es lässt uns /eher als //für die Ganzzahldivision verwenden.

Python 2 , 156 Bytes

f=lambda x,l=255,k=map(ord,'@`rFTDVbpPBvdtfR@'):f(x*2^x/128*285,l-1)if~-x*l else[k[l%17]^(0x450a98dc4ed7d6440b99934f92dd01>>l/17*8&255),k[l/17]][l%17<1]^188

Probieren Sie es online!

xnor
quelle
7

JavaScript (ES6), 139 Byte

Ähnlich wie die Node.js-Version, jedoch mit Zeichen außerhalb des ASCII-Bereichs.

f=(x,l=256,b=17,k=i=>"@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è".charCodeAt(i))=>--l*x^l?f(x+x^(x>>7)*285,l):l%b?k(l%b)^k(b+l/b)^b:k(l/b)^188

Probieren Sie es online!


JavaScript (Node.js) ,  149 bis  148 Byte

Basierend auf Xavier Bonnetain des C - Implementierung (die präsentierte hier ).

f=(x,l=256,b=17,k=i=>Buffer("@`rFTDVbpPBvdtfR@,p?b>4&i{zcq5'h")[~~i]|3302528>>i-b&128)=>--l*x^l?f(x+x^(x>>7)*285,l):l%b?k(l%b)^k(b+l/b)^b:k(l/b)^188

Probieren Sie es online!

Codierung

In der ursprünglichen Antwort von Xavier werden die Tabellen s[]und k[]in der folgenden Zeichenfolge gespeichert:

"@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8"
 \_______________/\__________________________________/
         k                         s

Die ersten 17 Zeichen sind die ASCII-Darstellungen von, k[i] XOR 64und die nächsten 15 Zeichen sind die ASCII-Darstellungen von s[i-17] XOR 173, oder s[i-17] XOR 64 XOR 17 XOR 252.

k[i] XOR 64s[i-17] XOR 173126128

Folgendes bekommen wir:

original value : 172 112  63 226  62  52 166 233 123 122 227 113  53 167 232
subtract 128?  :   1   0   0   1   0   0   1   1   0   0   1   0   0   1   1
result         :  44 112  63  98  62  52  38 105 123 122  99 113  53  39 104
as ASCII       : "," "p" "?" "b" ">" "4" "&" "i" "{" "z" "c" "q" "5" "'" "h"

11001001100100125801

128

| 3302528 >> i - b & 128

s

NB: Dies ist nur eine Randnotiz, die nichts mit den obigen Antworten zu tun hat.

s

{1,11,79,146}

console.log(
  [ 0b0001, 0b1100, 0b1000, 0b0100, 0b1001, 0b1010, 0b0010, 0b0110,
    0b1110, 0b1111, 0b0101, 0b1101, 0b1011, 0b0011, 0b0111
  ].map(x =>
    [ 1, 11, 79, 146 ].reduce((p, c, i) =>
      p ^= x >> i & 1 && c,
      0
    )
  )
)

Probieren Sie es online!

Arnauld
quelle
3

Python 3 , 182 Bytes

def p(x,t=b'@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8',l=255,d=17):
 if x<2:return 252-14*x
 while~-x:x=x*2^(x>>7)*285;l-=1
 return(188^t[l//d],d^t[l%d]^t[d+l//d])[l%d>0]

Probieren Sie es online!

Python wird hier nicht den ersten Preis gewinnen, aber dies ist immer noch ein 10-Byte-Golf des besten Python-Programms hier .

Python 3 , 176 Bytes

p=lambda x,l=255,t=b'@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8',d=17:2>x<l>254and-14*x+252or(p(x*2^(x>>7)*285,l-1)if~-x else(188^t[l//d],d^t[l%d]^t[d+l//d])[l%d>0])

Probieren Sie es online!

Als Lambda ist es noch sechs Bytes kürzer. Es tut mir weh, es zu benutzen if... else, aber ich sehe keine andere Option zum Kurzschließen, wenn man bedenkt, wie 0 eine mögliche Antwort ist.

Python 3 , 173 Bytes

p=lambda x,l=255,t=bytes('@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è','l1'),d=17:2>x<l>254and-14*x+252or(p(x*2^(x>>7)*285,l-1)if~-x else(188^t[l//d],d^t[l%d]^t[d+l//d])[l%d>0])

Probieren Sie es online!

Noch kürzer in Bytes (obwohl ich mir bei Bits nicht sicher bin, weil dies kein reines ASCII mehr ist), mit freundlicher Genehmigung von ovs.

ArBo
quelle
3 Bytes kürzer durch Verwendung der wörtlichen Zeichen anstelle von \x..Escapezeichen
ovs
@ovs Danke! Erhöht wahrscheinlich die Bitanzahl etwas (nicht sicher, was für das OP am wichtigsten ist), daher behalte ich auch meine alte Antwort.
ArBo
2

Rust , 170 163 Bytes

|mut x|{let(k,mut l)=(b"QqcWEUGsaASguewCQ\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",255);while l*x!=l{x=2*x^x/128*285;l-=1}(if l%17>0{l+=289;k[l%17]}else{173})^k[l/17]}

Probieren Sie es online!

Dies ist ein Port meiner Lösung in C mit einer etwas anderen Zeichenfolge, die nicht xor 17 erfordert. Ich gehe davon aus, dass die meisten Lösungen auf der Zeichenfolge "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 basieren {z \ xe3q5 \ xa7 \ xe8 "kann ebenfalls verbessert werden (ändern Sie einfach die Zeichenfolge, entfernen Sie xor 17 und xor 173 anstelle von 188).

Ich habe einen der Lookups entfernt, indem ich ihn bedingt hinzugefügt 17*17habe l, wie wir es (mehr oder weniger) in der ARM-Maschinencodelösung getan haben.

Rust hat Typinferenz und Closures, aber seine Casts (auch für Boolesche Werte oder zwischen ganzen Zahlen) sind immer explizit, die Mutabilität muss markiert werden, es gibt keinen ternären Operator, Ganzzahloperationen, standardmäßig Panik bei Überlauf und Mutationsoperationen ( l+=1) gibt die Einheit zurück. Ich habe es nicht geschafft, mit Iteratoren eine kürzere Lösung zu finden, da Closures + Mapping immer noch ziemlich ausführlich sind.

Dies scheint Rust zu einer ziemlich schlechten Wahl für das Golfen zu machen. Trotzdem sind wir selbst in einer Sprache, in der Lesbarkeit und Sicherheit im Vordergrund stehen, viel zu kurz.

Update: verwendet eine anonyme Funktion, aus manatworks Vorschlag.

Xavier Bonnetain
quelle
1
Außer wenn sie rekursiv aufgerufen werden, sind anonyme Funktionen / Lambdas zulässig, sodass Sie let p=in den Header wechseln und diesen nicht zählen können. Unsicher über die ;, da für anonymen Anruf nicht benötigt wird: Probieren Sie es online! .
Manatwork
1

05AB1E , 74 Bytes

₄FÐ;sÉiƵf^])2k>17‰Dθ_i¦16š}<(Rć16α2в≠ƶ0Kì6ª•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвs<è.«^

Port von @NickKennedys erster Jelly-Antwort . Ich habe an einem Port von @ jimmy23013s CJam-Antwort direkt gearbeitet , aber ich hatte bereits 78 Bytes und musste immer noch einen Fehler beheben, sodass dieser größer gewesen wäre. Das kann man aber definitiv noch ein bisschen spielen.

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

F              # Loop 1000 times:
  Ð             #  Triplicate the current value
                #  (which is the implicit input in the first iteration)
   ;            #  Halve it
    s           #  Swap to take the integer again
     Éi         #  If it's odd:
       Ƶf^      #   Bitwise-XOR it with compressed integer 142
]               # Close the if-statement and loop
 )              # Wrap all values on the stack into a list
  2k            # Get the 0-based index of 2 (or -1 if not found)
    >           # Increase it by 1 to make it 1-based (or 0 if not found)
     17        # Take the divmod-17 of this
Dθ_i    }       # If the remainder of the divmod is 0:
    ¦16š        #  Replace the quotient with 16
         <      # Decrease both values by 1
          (     # And then negate it
R               # Reverse the pair
 ć              # Extract head; push head and remainder-list
  16α           # Get the absolute difference between the head and 16
     2в         # Convert it to binary (as digit-list)
               # Invert booleans (0 becomes 1; 1 becomes 0)
        ƶ       # Multiply all by their 1-based indices
         0K     # And remove all 0s
           ì    # And prepend this in front of the remainder-list
            6ª  # And also append a trailing 6
5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•
                # Push compressed integer 29709448685778434533295690952203992295278432248
  ƵŠв           # Converted to base-239 as list:
                #  [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]
     s          # Swap to take the earlier created list again
      <         # Subtract each by 1 to make them 0-based
       è        # And index them into this list
.«^             # And finally reduce all values by bitwise XOR-ing them
                # (after which the result is output implicitly)

Sehen Sie sich meinen Tipp 05AB1E an (Abschnitte Wie komprimiere ich große Ganzzahlen? Und Wie komprimiere ich Ganzzahlenlisten? ) , Um zu verstehen, warum dies so Ƶfist 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ist 29709448685778434533295690952203992295278432248, ƵŠist 239; und •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвist [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].

Kevin Cruijssen
quelle