Probar que un estándar criptográfico ruso está demasiado estructurado

92

El objetivo de este desafío es encontrar una implementación imposiblemente corta de la siguiente función p, en el idioma que elija. Aquí está el código C que lo implementa (vea este enlace TIO que también imprime sus resultados) y una página de Wikipedia que lo contiene.

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];
}

Que es p

pes un componente de dos estándares criptográficos rusos, a saber, la función hash Streebog y el cifrado de bloque Kuznyechik . En este artículo (y durante las reuniones de ISO), los diseñadores de estos algoritmos afirmaron que generaron la matriz piseleccionando permutaciones aleatorias de 8 bits.

Implementaciones "imposibles"

Hay permutaciones en 8 bits. Por lo tanto, para una permutación aleatoria dada, no se espera que un programa que la implemente necesite menos de 1683 bits.256!21684

Sin embargo, hemos encontrado múltiples implementaciones anormalmente pequeñas (que enumeramos aquí ), por ejemplo, el siguiente programa en C:

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;}

que contiene solo 158 caracteres y, por lo tanto, cabe en 1264 bits. Haga clic aquí para ver que funciona.

Hablamos de una implementación corta "imposiblemente" porque, si la permutación fuera el resultado de un proceso aleatorio (como afirman sus diseñadores), entonces no existiría un programa tan corto (consulte esta página para obtener más detalles).

Implementación de referencia

Una versión más legible del código C anterior es:

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;
}

La tabla kes tal que k[x] = L(16-x), donde Les lineal en el sentido de que L(x^y)==L(x)^L(y), y donde, como en C, ^denota el XOR. Sin embargo, no logramos aprovechar esta propiedad para acortar nuestra implementación. No conocemos ninguna estructura sque pueda permitir una implementación más simple, aunque su salida siempre está en el subcampo, es decir donde la exponenciación se realiza en el campo finito. ¡Por supuesto, usted es absolutamente libre de usar una expresión más simple de si encuentra una!s[X]dieciséis=s[X]s

El ciclo while corresponde a la evaluación de un logaritmo discreto en el campo finito con 256 elementos. Funciona a través de una simple búsqueda de fuerza bruta: la variable ficticia aestá configurada para ser un generador del campo finito, y se multiplica por este generador hasta que el resultado sea igual a x. Cuando es el caso, tenemos que les el registro discreto de x. Esta función no está definida en 0, de ahí el caso especial correspondiente a la ifdeclaración.

La multiplicación por el generador puede verse como una multiplicación por en que luego se reduce el módulo del polinomio . El papel de la es garantizar que la variable permanezca en 8 bits. Alternativamente, podríamos usar , en cuyo caso podría ser un (o cualquier otro tipo de entero). Por otro lado, es necesario comenzar con lo que necesitamos tener cuando es igual a 1.XF2[X]X8+X4 4+X3+X2+1unsigned charaa=(a<<1)^(a>>7)*(256^29)aintl=1,a=2l=255x

En nuestro documentop se presentan más detalles sobre las propiedades de , con un resumen de la mayoría de nuestras optimizaciones para obtener la implementación breve anterior.

Reglas

Proponga un programa que implemente la función pen menos de 1683 bits. Mientras más corto sea el programa, más anormal es, para un idioma dado, más corto es mejor. Si su idioma tiene Kuznyechik, Streebog o pcomo incorporado, no puede usarlos.

La métrica que usamos para determinar la mejor implementación es la longitud del programa en bytes. Usamos la longitud de bits en nuestro trabajo académico, pero nos quedamos con los bytes aquí por simplicidad.

Si su lenguaje no tiene una noción clara de función, argumento o salida, la codificación depende de usted para definir, pero trucos como codificar el valor pi[x]como xobviamente están prohibidos.

Ya hemos presentado un trabajo de investigación con nuestros hallazgos sobre este tema. Está disponible aquí . Sin embargo, si se publica en un lugar científico, con gusto reconoceremos a los autores de las mejores implementaciones.

Por cierto, ¡gracias a xnor por su ayuda al redactar esta pregunta!

picarresursix
fuente
12
Espero que alguien envíe una respuesta en Seed.
Robin Ryder
66
Del mismo modo, ¿se puede calificar, por ejemplo, el código brainfuck a 3 bits por carácter si no tiene nops? ¿Y es la 1683 bits at mostrestricción estricta [sic?] O la meta?
alguien el
31
" Si la permutación fuera el resultado de un proceso aleatorio (como afirman sus diseñadores), entonces un programa tan corto no existiría " No estoy de acuerdo (aunque no importa para el desafío). Si fuera el resultado de un proceso aleatorio, sería poco probable que dicho programa existiera; o sería difícil de encontrar
Luis Mendo
8
@Grimy La afirmación de que un programa tan corto no existiría es conceptual (no de programación). Usando sus términos, pertenece al mundo de las matemáticas puras, no al mundo de la programación
Luis Mendo
77
Puede que ya se haya notado, pero por si acaso: da como resultado solo 8 valores distintos: (comenzando con y suponiendo ) . 1 , 10 , 68 , 79 , 146 , 153 , 220 , 221 i = 1 s 0 = 0syo XOR syo-11,10,68,79,146,153,220,221yo=1s0 0=0 0
Arnauld

Respuestas:

35

Conjunto AMD64 (78 bytes o 624 bits de código de máquina)

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};

    si (x) {
      para (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];
    }
    retorno x ^ 252;
}

Conjunto x86 de 64 bits

    ; 78 bytes de ensamblaje AMD64
    ; odzhan
    bits 64

    % ifndef BIN
      SubBytex global
    %terminara si

SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    llamar a L0
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 ++
    agregar al, al; y = y + y
    jnc $ + 4; omita XOR si no lleva
    xor al, 29;
    cmp al, cl; if (y! = x) pasa a 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]
    prueba dl, dl; si (x == 0) pasa a L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2
    jubilado

Código de 64 bits desmontado

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 llamada qword 0x2a
; 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 prueba dl, dl
00000047 7404 jz 0x4d
00000049 92 xchg eax, edx
0000004A D7 xlatb
0000004B 30C8 xor al, cl
0000004D C3 ret

Ensamblado x86 de 32 bits

    ; 72 bytes de ensamblaje x86
    ; odzhan
    bits 32

    % ifndef BIN
      SubBytex global
      global _SubBytex
    %terminara si

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    llamar a L0
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 ++
    agregar al, al; y = y + y
    jnc $ + 4; omita XOR si no lleva
    xor al, 29;
    cmp al, cl; if (y! = x) pasa a 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; si (x == 0) al = z más al = x
    xlatb; al = k [z] o k [x]
    jz L2; si (x == 0) pasa a L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2
    jubilado

Código de 32 bits desmontado

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 llamada dword 0x29
; 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
fuente
1
¡Buena respuesta! Como el OP buscaba un recuento de bits, este (85 bytes) llega a 680 bits , usando 8 bits por byte, o 595 bits usando 7 bits por byte (posible ya que todos los caracteres son ASCII). Probablemente podría acortarse si se comprime a un conjunto de caracteres aún más restrictivo.
Cullub
1
Bienvenido a PPCG; Buena primera solución.
Shaggy
99
@Cullub Mi punto fue que el código en esta respuesta es solo C / Assembler que se compila, por lo que el recuento de bytes no es el del código dado, sino el código compilado. Y eso no es ASCII.
ArBo
77
Solo para aclarar, ¿los 84 bytes son el tamaño del código de la máquina después de que se haya ensamblado? Si es así, el título debe actualizarse para reflejar que esta es una respuesta de código de máquina en lugar de una respuesta de ensamblaje.
Patata44
1
Y, por cierto, no tiene que usar una convención de llamadas estándar; puede usar una convención personalizada en la que RBX recibe llamadas, ahorrando 2 bytes para push / pop. (Y donde los uint8_targumentos son extendidos a cero a 64 bits para JRCXZ). Además, si escribe código dependiente de la posición, puede colocar la dirección de la tabla en un registro con 5 bytes en mov ebx, imm32lugar de 6 bytes call/ pop. O utilizarlo como disp32en mov al, [table + rax], pero que podría perder ya que tiene dos xlatby una movya. Sin embargo, el truco call + pop shellcode gana vs. LEA relativo a RIP de 7 bytes con los datos después del 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* repite algo con la marca de tiempo actual, que es un gran número, y tardaría demasiado en terminar.

Versión realmente comprobable, 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

Pruébalo en línea!

¡Prueba todo en línea!

Para ejecutar este código (en una máquina Linux), es necesario agregar la línea en_US.ISO-8859-1 ISO-8859-1en /etc/locale.geny ejecutar locale-gen. Entonces podrías usar:

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

O puede probar esta versión equivalente de 72 bytes UTF-8:

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

Explicación

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.

Los caracteres en la cadena son:

  • 221. Ver abajo.
  • 48, 36, 38, 18. Es la descomposición lineal de k basada en las características de L en la pregunta.
  • 220, el valor de relleno de la matriz s cuando solo se usa la matriz k.
  • La matriz s xor 220 está invertida, excepto el último elemento, o el primer elemento antes invertido, que es el 221 al comienzo de la cadena.
jimmy23013
fuente
¿Qué harías con el set de potencia? PD: Probablemente voy a robar ese truco de hacer la operación de campo finito a la inversa. Muy aseado.
Peter Taylor
@PeterTaylor Puede obtener la matriz k usando el conjunto de potencia de [48 36 38 18] (o su reverso) con el orden más directo y reducir cada uno en xor. Pero en los idiomas de golf utilizados en esta pregunta hasta ahora, solo 05AB1E tenía el orden correcto. Jelly y Stax aparentemente tenían una idea diferente sobre lo que pensé que debería ser sencillo.
jimmy23013
Actualmente estoy en el proceso de jugar golf en su respuesta a 05AB1E. ¿Cuáles son los valores enteros para su cadena "Ý0$&Ü™ÖD�’\n˜×EO“N"?
Kevin Cruijssen
@KevinCruijssen ¿Estás preguntando qué significan o sus valores numéricos (que puedes ver en el volcado hexadecimal)?
jimmy23013
@ jimmy23013 Ah, por supuesto ... Olvidé el volcado hexadecimal ...
Kevin Cruijssen
19

Jalea 71 59 bytes

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

Pruébalo en línea!

Verificar todas las posibilidades

Ahora reescrito usando una versión reelaborada de la inteligente respuesta CJam de jimmy23013, ¡ así que asegúrese de votar esa también! Utiliza solo 472 bits (28.0% del enfoque ingenuo). ¡@ jimmy23013 también ha guardado otro byte!

Explicación

Nivel 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

Etapa 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

Etapa 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

Enfoque original

Gelatina , 71 66 bytes

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

Pruébalo en línea!

Verificar todas las posibilidades

Un enlace monádico o programa completo que toma un solo argumento y devuelve el valor relevante de pi[x]. Esto es 536 bits, por lo tanto, debajo de un tercio del almacenamiento ingenuo de pi.

Guardado 3 bytes utilizando el método para encontrar lde respuesta Cjam de jimmy23013 así que asegúrese de upvote que uno también!

Explicación

Nivel 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

Etapa 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

Etapa 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
fuente
1
59 bytes , otra versión .
jimmy23013
15

C (gcc) , 157148140139 bytes

Mejora modesta sobre el ejemplo C.

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;}

Pruébalo en línea!

C (gcc) , 150 142 127 126 bytes

Este depende de las peculiaridades de gcc y x86 y UTF-8.

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;}

Pruébalo en línea!

Gracias a @XavierBonnetain por -1 y menos comportamiento indefinido.

techo
fuente
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 gracias a @Grimy .

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

Puerto de la función C de Xavier Bonnetain (versión de 1106 bits) desde aquí , con la misma mejora que @ceilingcat hizo en su respuesta C para ahorrar 3 bytes, ¡así que asegúrese de votarlo!

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)

Vea esta sugerencia mía 05AB1E (secciones ¿Cómo comprimir enteros grandes? Y ¿Cómo comprimir listas enteras? ) Para comprender por qué •α">η≠ε∍$<Θγ\&@(Σα•es 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅вes [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹es 285; •¾#kôlb¸ù,-ó"a·ú•es 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅вes [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; y Ƶ∞es 188.

Kevin Cruijssen
fuente
@Grimy Gracias, siempre olvidé ese tipo de golf con las listas enteras comprimidas ... (PD: puede rodear el código que contiene 'en los comentarios con dos de ellos en ambos lados. Es decir, con' en lugar de ':' código 'código' ''.)
Kevin Cruijssen
Vaya, perdón por el formato desordenado. Sé sobre duplicar los backticks, pero no me di cuenta de que la lista comprimida tenía un backtick. También: s^=> ^(XOR es conmutativo). En realidad, ¿no es lo s^_mismo que Q?
Sucio
@ Grimy Gracias! De hecho tienes razón. Básicamente comprobar si una de las siguientes tres cosas es Truthy para salir del bucle: 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ü Ü╕║

Ejecutar y depurarlo

Desafortunadamente, este programa usa algunas instrucciones que usan internamente algunas instrucciones obsoletas obsoletas. Simplemente olvidé actualizar su implementación. Esto hace que aparezca una advertencia espuria, pero los resultados aún son correctos.

Esto está inspirado en la excelente respuesta de jimmy23013 . Algunas partes se han cambiado para adaptarse mejor a Stax.

Los programas Stax escritos en ASCII imprimible tienen una representación alternativa que ahorra un poco más de 1 bit por byte, ya que solo hay 95 caracteres ASCII imprimibles.

Aquí está la representación ascii de este programa formateado para "legibilidad" con comentarios.

{                       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

Ejecute este

Versión modificada para ejecutar todas las entradas 0..255

recursivo
fuente
Stax tiene Spara poder establecer. Puede obtener el conjunto de potencia de [18 38 36 48], indexar y reducir en xor. (No conozco a Stax y no estoy seguro de que sea más corto).
jimmy23013
Creo que el pedido de Stax para subconjuntos producidos por el Soperador no está en el orden correcto para que eso funcione. p "abc"SJ. ej. (conjunto de potencia de "abc" unido con espacios) produce "a ab abc ac b bc c".
recursivo
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

Pruébalo en línea!

Una función que implementa la permutación. El código usa solo caracteres ASCII de 7 bits.

Codifica kcomo una cadena de bytes de Python 3, desplazada ^64al rango imprimible. Por el contrario, sse codifica como los dígitos de base 256 de una constante numérica, y los dígitos se extraen como [number]>>[shift]*8&255. Esto fue más corto que la codificación sen una cadena debido a la cantidad de caracteres de escape que esto requería, incluso con un desplazamiento óptimo ^160para minimizarlos.

El cálculo de registro discreto se realiza al revés. La actualización x=x*2^x//128*285avanza en el grupo cíclico simulando la multiplicación por la generación, hasta que alcanza la identidad x=1. Comenzamos el registro discreto en l=255(la duración del ciclo) y lo disminuimos en cada iteración. Para manejar el x=0caso y hacer que no se repita para siempre, también terminamos cuando l=0, lo que hace que x=0map se l=0especifique.


Python 2 pierde al no tener buenas cadenas de bytes, por lo que debemos hacerlo map(ord,...)(ArBo guardó un byte aquí). Nos permite usar en /lugar de //para la división de enteros.

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

Pruébalo en línea!

xnor
fuente
7

JavaScript (ES6), 139 bytes

Similar a la versión Node.js, pero usando caracteres más allá del rango ASCII.

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

Pruébalo en línea!


JavaScript (Node.js) ,  149  148 bytes

Basado en la implementación C de Xavier Bonnetain (que se presenta aquí ).

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

Pruébalo en línea!

Codificación

En la respuesta original de Xavier, las tablas s[]y k[]se almacenan en la siguiente cadena:

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

Los primeros 17 caracteres son las representaciones ASCII de k[i] XOR 64y los siguientes 15 caracteres son las representaciones ASCII de s[i-17] XOR 173, o s[i-17] XOR 64 XOR 17 XOR 252.

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

Esto es lo que obtenemos:

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: Esta es solo una nota al margen, no relacionada con las respuestas anteriores.

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

Pruébalo en línea!

Arnauld
fuente
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]

Pruébalo en línea!

Python no va a ganar el primer premio aquí, pero este sigue siendo un golf de 10 bytes del mejor programa de Python aquí .

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

Pruébalo en línea!

Como lambda, todavía es seis bytes más corto. Me duele tener que usar if... else, pero no veo otra opción para el cortocircuito, dado que 0 es una respuesta posible.

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

Pruébalo en línea!

Incluso más corto en bytes (aunque no estoy seguro acerca de los bits, porque esto ya no es ASCII puro), cortesía de ovs.

ArBo
fuente
3 bytes más cortas mediante el uso de los caracteres literales en lugar de \x..escapes
ovs
@ovs Gracias! Probablemente aumenta un poco el recuento de bits (no estoy seguro de cuál es el más importante para el OP), por lo que también mantendré mi respuesta anterior.
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]}

Pruébalo en línea!

Este es un puerto de mi solución en C, con una cadena ligeramente diferente, que no requiere xor 17. Espero que la mayoría de las soluciones basen la cadena "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "también se puede mejorar (simplemente cambie la cadena, elimine xor 17 y xor 173 en lugar de 188).

Quité una de las operaciones de búsqueda mediante la adición de condicionalmente 17*17a l, ya que (más o menos) hicimos en la solución de código de máquina ARM.

Rust tiene inferencia de tipo y cierres, pero sus conversiones (incluso para booleanos o entre enteros) siempre son explícitas, la mutabilidad debe estar marcada, no tiene un operador ternario, operaciones de enteros, por defecto, pánico al desbordarse y operaciones de mutación ( l+=1) devuelve la unidad. No logré obtener una solución más corta con iteradores, ya que los cierres + mapeo siguen siendo bastante detallados.

Esto parece hacer que Rust sea una muy mala elección para jugar al golf. Sin embargo, incluso en un lenguaje que enfatiza la legibilidad y la seguridad sobre la concisión, somos demasiado cortos.

Actualización: se utilizó una función anónima, a partir de la sugerencia de manatwork.

Xavier Bonnetain
fuente
1
Excepto cuando se llama de forma recursiva, las funciones / lambdas anónimas son aceptables, por lo que puede pasar let p=al encabezado y no contarlo. No estoy seguro acerca de ;, ya que no se necesita una llamada anónima: ¡ Pruébelo en línea! .
manatwork
1

05AB1E , 74 bytes

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

Puerto de la primera respuesta de Jelly de @NickKennedy . Estaba trabajando en un puerto de la respuesta CJam de @ jimmy23013 directamente , pero ya tenía 78 bytes y todavía tenía que corregir un error, por lo que habría sido más grande. Sin embargo, esto definitivamente todavía se puede jugar bastante.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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)

Vea esta sugerencia mía 05AB1E (secciones ¿Cómo comprimir enteros grandes? Y ¿Cómo comprimir listas enteras? ) Para comprender por qué Ƶfes 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•es 29709448685778434533295690952203992295278432248, ƵŠes 239; y •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвes [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].

Kevin Cruijssen
fuente