Prouver qu'une norme cryptographique russe est trop structurée

92

Le but de ce défi est de trouver une implémentation incroyablement courte de la fonction suivante p, dans le langage de votre choix. Voici le code C l’implémentant (voir ce lien TIO qui affiche également ses sorties) et une page wikipedia le contenant.

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

Quel est p

pest un composant de deux standards cryptographiques russes, à savoir la fonction de hachage Streebog et le chiffrement de bloc Kuznyechik . Dans cet article (et lors des réunions ISO), les concepteurs de ces algorithmes ont affirmé avoir généré le tableau pien choisissant des permutations aléatoires de 8 bits.

Implémentations "impossibles"

Il y en a permutations sur 8 bits. Par conséquent, pour une permutation aléatoire donnée, un programme qui l'implémente ne doit pas nécessiter moins de 1683 bits.256!21684

Cependant, nous avons trouvé plusieurs implémentations anormalement petites (que nous énumérons ici ), par exemple le programme C suivant:

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

qui ne contient que 158 caractères et tient donc dans 1264 bits. Cliquez ici pour voir que cela fonctionne.

Nous parlons d'une implémentation courte "impossible" parce que, si la permutation était la sortie d'un processus aléatoire (comme l'affirment ses concepteurs), un programme de cette durée n'existerait pas (voir cette page pour plus de détails).

Mise en oeuvre de référence

Une version plus lisible du code C précédent est:

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

Le tableau kest tel que k[x] = L(16-x), où Lest linéaire en ce sens L(x^y)==L(x)^L(y)et où, comme en C, ^désigne le XOR. Cependant, nous n'avons pas réussi à tirer parti de cette propriété pour raccourcir notre mise en œuvre. Nous ne connaissons aucune structure squi pourrait permettre une implémentation plus simple - sa sortie est toujours dans le sous-champ, c.-à- où l’exponentiation est effectuée dans le champ fini. Bien sûr, vous êtes absolument libre d'utiliser une expression plus simple de si vous en trouvez une!s[x]16=s[x]s

La boucle while correspond à l'évaluation d'un logarithme discret dans le corps fini à 256 éléments. Cela fonctionne via une recherche simple par force brute: la variable factice aest définie pour être un générateur du corps fini, et elle est multipliée par ce générateur jusqu'à ce que le résultat soit égal à x. Quand c'est le cas, nous avons c'est lle journal discret de x. Cette fonction n'est pas définie à 0, d'où le cas particulier correspondant à l' ifinstruction.

La multiplication par le générateur peut être vue comme une multiplication par dans qui est alors réduite modulo le polynôme . Le rôle de l ' est de s'assurer que la variable reste sur 8 bits. Alternativement, nous pourrions utiliser , auquel cas ce pourrait être un type (ou tout autre type entier). D'autre part, il est nécessaire de commencer par ce que nous devons avoir quand est égal à 1.XF2[X]X8+X4+X3+X2+1unsigned charaa=(a<<1)^(a>>7)*(256^29)aintl=1,a=2l=255x

Plus de détails sur les propriétés de psont présentés dans notre article , avec un résumé de la plupart de nos optimisations pour obtenir la mise en œuvre courte précédente.

Règles

Proposez un programme qui implémente la fonction pen moins de 1683 bits. Plus le programme est court, plus il est anormal, pour une langue donnée, plus c'est court, mieux c'est. Si votre langue est Kuznyechik, Streebog ou pintégrée, vous ne pouvez pas les utiliser.

La métrique que nous utilisons pour déterminer la meilleure implémentation est la longueur du programme en octets. Nous utilisons la longueur de bit dans notre article académique, mais nous nous en tenons aux octets pour des raisons de simplicité.

Si votre langue ne dispose pas d' une notion claire de la fonction, l' argument ou de sortie, le codage est à vous de définir, mais des trucs comme codant pour la valeur pi[x]que xsont évidemment interdites.

Nous avons déjà soumis un document de recherche contenant nos conclusions sur ce sujet. Il est disponible ici . Toutefois, s’il est publié dans un lieu scientifique, nous nous ferons un plaisir de reconnaître les auteurs des meilleures implémentations.

En passant, merci à xnor pour son aide lors de la rédaction de cette question!

picarresursix
la source
12
J'espère que quelqu'un soumet une réponse dans Seed.
Robin Ryder le
6
De même, un code brainfuck, par exemple, peut-il être noté à 3 bits par caractère s'il n'a pas de nops? Et est-ce 1683 bits at mostune restriction stricte [sic?] Ou un objectif?
quelqu'un
31
" Si la permutation était le résultat d'un processus aléatoire (comme le prétendent ses concepteurs), alors un programme aussi court n'existerait pas ". Je ne suis pas d'accord (même si cela n'a pas d'importance pour le défi). S'il s'agissait d'un processus aléatoire, il serait peu probable qu'un tel programme existe; ou il serait difficile à trouver
Luis Mendo
8
@Grimy L'affirmation qu'un programme de ce court-circuit n'existerait pas est un programme conceptuel (et non un programme). Selon vos termes, il appartient au monde des mathématiques pures, pas au monde de la programmation
Luis Mendo
7
Cela a peut-être déjà été remarqué, mais juste au cas où: donne que 8 valeurs distinctes: (commençant par et supposant que ) . 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 le

Réponses:

35

Assemblage AMD64 (78 octets ou 624 bits de code machine)

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) {
      pour (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];
    }
    retour x ^ 252;
}

Assemblage x86 64 bits

    ; 78 octets d'assemblage AMD64
    ; Odzhan
    bits 64

    % ifndef BIN
      SubBytex global
    %fin si

SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    appelez 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 ++
    ajouter al, al; y = y + y
    jnc $ + 4; sauter XOR si aucun report
    xor al, 29;
    cmp al, cl; si (y! = x) passez à 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; si (x == 0) passe à L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    ret

Code 64 bits désassemblé

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

Assemblage 32 bits x86

    ; 72 octets d'assemblage x86
    ; Odzhan
    bits 32

    % ifndef BIN
      SubBytex global
      global _SubBytex
    %fin si

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; si (x) {
    appelez 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 ++
    ajouter al, al; y = y + y
    jnc $ + 4; sauter XOR si aucun report
    xor al, 29;
    cmp al, cl; si (y! = x) passez à 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 sinon al = x
    xlatb; al = k [z] ou k [x]
    jz L2; si (x == 0) passe à L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    ret

Code 32 bits désassemblé

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 appel 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
la source
1
Bonne réponse! Comme l'OP recherchait le nombre de bits, ce nombre (85 octets) s'élevait à 680 bits , en utilisant 8 bits par octet, ou 595 bits en utilisant 7 bits par octet (possible, tous les caractères étant en ASCII). Vous pourriez probablement aller plus vite si vous comprimiez un jeu de caractères encore plus restrictif.
Cullub
1
Bienvenue chez PPCG; belle première solution.
Shaggy
9
@ Cullub Mon point était que le code dans cette réponse est juste le C / Assembler qui est compilé, donc le nombre d'octets n'est pas celui du code donné, mais celui du code compilé. Et ce n'est pas ASCII.
ArBo
7
Juste pour clarifier, les 84 octets sont la taille du code machine une fois celui-ci assemblé? Si tel est le cas, le titre devrait être mis à jour pour indiquer qu'il s'agit d'une réponse de code machine plutôt que d'une réponse d'ensemble.
Potato44
1
Et BTW, vous n’avez pas à utiliser une convention d’appel standard; vous pouvez utiliser une convention personnalisée selon laquelle RBX est codé en appels, ce qui permet d'économiser 2 octets pour les transferts. (Et où les uint8_targuments sont étendus à 64 bits pour JRCXZ). De plus, si vous écrivez un code dépendant de la position, vous pouvez mettre l'adresse de la table dans un registre avec un 5 octets mov ebx, imm32au lieu d'un 6 octets call/ pop. Ou utilisez-le comme un disp32dans mov al, [table + rax], mais cela pourrait perdre puisque vous avez déjà deux xlatbet un mov. Le piège call + pop shellcode l'emporte sur le LEA relatif relatif au RIP sur 7 octets avec les données qui suivent ret.
Peter Cordes Le
23

CJam ,72 67 66 63 octets

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

es* répète quelque chose en fonction de l'horodatage actuel, ce qui est un grand nombre, et cela prendrait trop de temps.

Version actuellement testable, 64 octets:

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

Essayez-le en ligne!

Essayez tout en ligne!

Pour exécuter ce code (sur une machine Linux), vous devez ajouter la ligne en_US.ISO-8859-1 ISO-8859-1dans /etc/locale.genet exécuter locale-gen. Ensuite, vous pouvez utiliser:

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

Ou vous pouvez essayer cette version équivalente de 72 octets 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

Explication

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.

Les caractères de la chaîne sont:

  • 221. Voir ci-dessous.
  • 48, 36, 38, 18. C'est la décomposition linéaire de k basée sur les caractéristiques de L dans la question.
  • 220, la valeur de remplissage du tableau s lorsque seul le tableau k est utilisé.
  • Le tableau s xor 220 est inversé, sauf pour le dernier élément, ou le premier élément avant inversé, qui correspond au 221 au début de la chaîne.
jimmy23013
la source
Que feriez-vous avec l'ensemble de puissance? PS je vais probablement voler cette astuce de faire l'opération de champ fini à l'envers. Très propre.
Peter Taylor le
@PeterTaylor Vous pouvez obtenir le tableau k en utilisant le jeu de puissances de [48 36 38 18] (ou son inverse) avec l'ordre le plus simple, et les réduire de xor. Mais dans les langues de golf utilisées jusqu'à présent dans cette question, seul le 05AB1E avait la bonne commande. Jelly et Stax avaient apparemment une idée différente de ce que je pensais être simple.
Jimmy23013 le
Je suis actuellement en train de jouer au golf avec votre réponse à 05AB1E. Quelles sont les valeurs entières pour votre chaîne "Ý0$&Ü™ÖD�’\n˜×EO“N"?
Kevin Cruijssen
@KevinCruijssen Demandez-vous ce qu'ils voulaient dire ou leurs valeurs numériques (que vous pouvez voir à partir du vidage hexadécimal)?
jimmy23013
@ jimmy23013 Ah, bien sûr .. J'ai oublié le dump des hexagones ..
Kevin Cruijssen
19

Gelée 71 59 octets

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

Essayez-le en ligne!

Vérifier toutes les possibilités

Maintenant, réécrivez en utilisant une version remaniée de la réponse CJam intelligente de jimmy23013, alors assurez-vous de l'evoter aussi! Utilise seulement 472 bits (28,0% de l'approche naïve). @ jimmy23013 a également enregistré un autre octet!

Explication

Étape 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

Étape 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

Étape 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

Approche originale

Gelée , 71 à 66 octets

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

Essayez-le en ligne!

Vérifier toutes les possibilités

Un lien monadique ou un programme complet qui prend un seul argument et renvoie la valeur pertinente de pi[x]. C'est 536 bits, donc moins d'un tiers de la mémoire naïve de pi.

Sauvegardé de 3 octets en utilisant la méthode de recherche lde la réponse CJam de jimmy23013, assurez-vous donc de l'emporter également!

Explication

Étape 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

Étape 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

Étape 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
la source
1
59 octets , une autre version .
jimmy23013
15

C (gcc) , 157 148 140 139 octets

Amélioration modeste par rapport à l'exemple 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;}

Essayez-le en ligne!

C (gcc) , 150 142 127 126 octets

Celui-ci dépend des bizarreries de gcc, x86 et 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;}

Essayez-le en ligne!

Merci à @XavierBonnetain pour -1 et un comportement moins indéfini.

plafondcat
la source
10

05AB1E , 101 100 98 97 95 94 octets

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

-3 octets grâce à @Grimy .

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

La fonction C du port de Xavier Bonnetain (version 1106 bits) à partir d'ici , avec la même amélioration que @ceilingcat apportée dans sa réponse en C pour économiser 3 octets, alors assurez-vous de l'inverser!

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)

Voir cette astuce 05AB1E de mes (sections Comment compresser les grands entiers? Et Comment compresser des listes entières? ) Pour comprendre pourquoi •α">η≠ε∍$<Θγ\&@(Σα•est 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅вest [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹est 285; •¾#kôlb¸ù,-ó"a·ú•est 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅вest [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; et Ƶ∞est 188.

Kevin Cruijssen
la source
@ Grimy Merci, j'ai toujours oublié ce genre de golf avec les listes d'entiers compressés .. (PS: Vous pouvez entourer du code contenant `dans les commentaires avec deux d'entre eux des deux côtés. C'est-à-dire avec 'au lieu de': '' code ' ''.)
Kevin Cruijssen
Oups, désolé pour le formatage foiré. Je sais qu'il est possible de doubler les backticks, mais je ne savais pas que la liste compressée avait un backtick. Aussi: s^=> ^(XOR est commutatif). En fait, n'est-ce pas s^_la même chose que Q?
Grimy
@ Grimy Merci! Tu as vraiment raison. Nous vérifions essentiellement si l' une des trois choses suivantes est truthy pour sortir de la boucle: i==0 || X==0 || X==1.
Kevin Cruijssen le
10

Stax , 65 64 62 59 58 octets

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

Exécuter et déboguer

Malheureusement, ce programme utilise des instructions qui utilisent en interne des instructions stax obsolètes. J'ai juste oublié de mettre à jour leur implémentation. Cela fait apparaître des avertissements parasites, mais les résultats sont toujours corrects.

Ceci est inspiré par l' excellente réponse de jimmy23013 . Certaines parties ont été modifiées pour mieux convenir à Stax.

Les programmes Stax écrits en ASCII imprimable ont une représentation alternative qui enregistre un peu plus de 1 bit par octet, car il n’ya que 95 caractères ASCII imprimables.

Voici la représentation ascii de ce programme au format "lisibilité" avec commentaires.

{                       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

Exécuter celui-ci

Version modifiée à exécuter pour toutes les entrées 0..255

récursif
la source
Stax a Spour pouvoir mis. Vous pouvez obtenir le jeu de puissance de [18 38 36 48], index et réduction de xor. (Je ne connais pas Stax et je ne suis pas sûr que ce serait plus court cependant.)
jimmy23013 Le
Je pense que les commandes de stax pour les sous-ensembles produits par l' Sopérateur ne sont pas dans le bon ordre pour que cela fonctionne. par exemple "abc"SJ(un ensemble de "abc" joint à des espaces) produit "a ab abc ac b bc c".
Récursif
8

Python 3 , 151 octets

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

Essayez-le en ligne!

Une fonction qui implémente la permutation. Le code utilise uniquement des caractères ASCII 7 bits.

Encode kcomme une chaîne d’essai Python 3, déplacée ^64dans la plage imprimable. En revanche, il sest codé en tant que base en 256 chiffres d’une constante numérique et les chiffres sont extraits en tant que [number]>>[shift]*8&255. Cela était plus court que l'encodage sdans une chaîne en raison du nombre de caractères d'échappement requis, même avec un décalage optimal ^160pour les minimiser.

Le calcul discret-log est effectué à l'envers. La mise à jour effectue une x=x*2^x//128*285boucle dans le groupe cyclique en simulant la multiplication par la génération, jusqu'à atteindre l'identité x=1. Nous commençons le journal discret à l=255(la longueur du cycle) et le décrémentons à chaque itération. Pour gérer le x=0cas et le faire ne pas boucler indéfiniment, nous terminons également when l=0, ce qui rend la x=0carte conforme à l=0celle spécifiée.


Python 2 perd sur le fait de ne pas avoir de beaux bytestrings, nous devons donc le faire map(ord,...)(ArBo a sauvegardé un octet ici). Cela nous permet d'utiliser /plutôt que //pour la division entière.

Python 2 , 156 octets

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

Essayez-le en ligne!

Xnor
la source
7

JavaScript (ES6), 139 octets

Similaire à la version de Node.js, mais utilisant des caractères au-delà de la plage 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

Essayez-le en ligne!


JavaScript (Node.js) ,  149  148 octets

Basé sur l'implémentation C de Xavier Bonnetain (présentée ici ).

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

Essayez-le en ligne!

Codage

Dans la réponse originale de Xavier, les tables s[]et k[]sont stockées dans la chaîne suivante:

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

Les 17 premiers caractères sont les représentations ASCII de k[i] XOR 64et les 15 suivants sont les représentations ASCII de s[i-17] XOR 173, ou s[i-17] XOR 64 XOR 17 XOR 252.

Tous les codes ASCII k[i] XOR 64correspondent aux caractères imprimables, mais 7 codes ASCII s[i-17] XOR 173dépassent et doivent être échappés. Nous les forçons dans la plage imprimable en soustrayant .126128

Voici ce que nous obtenons:

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"

En inversant le masque binaire formé par la 2 ème ligne du tableau ci-dessus, nous obtenons 110010011001001en binaire ou en décimal.25801

Ce masque binaire est multiplié par , de sorte que nous pouvons directement exécuter un OU au niveau du bit extrait. D'où la formule:128

| 3302528 >> i - b & 128

Bâtiments

NB: Ceci est juste une note de côté, sans rapport avec les réponses ci-dessus.

Ce code montre comment peut être construit en ne mettant XOR que 4 valeurs distinctes ensemble.s

Dans cet exemple, nous utilisons les 15 sous-ensembles non vides de , mais d'autres valeurs peuvent être choisies.{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
    )
  )
)

Essayez-le en ligne!

Arnauld
la source
3

Python 3 , 182 octets

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]

Essayez-le en ligne!

Python ne va pas gagner le premier prix ici, mais il s’agit toujours d’un parcours de golf sur 10 octets du meilleur programme Python ici .

Python 3 , 176 octets

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

Essayez-le en ligne!

En tant que lambda, il est encore six octets plus court. Cela me fait mal d'utiliser if... else, mais je ne vois pas d'autre option de court-circuit, vu que 0 est une réponse possible.

Python 3 , 173 octets

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

Essayez-le en ligne!

Encore plus court en octets (bien que je ne sois pas sûr des bits, car ce n'est plus du pur ASCII), grâce à ovs.

ArBo
la source
3 octets plus courts en utilisant les caractères littérales au lieu de les \x..évasions
OVS
@ovs Merci! Augmente probablement un peu le nombre de bits (je ne sais pas ce qui est le plus important pour le PO), alors je vais garder mon ancienne réponse aussi.
ArBo
2

Rouille , 170 163 octets

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

Essayez-le en ligne!

C’est un port de ma solution en C, avec une chaîne légèrement différente, qui ne nécessite pas de xor 17. Je suppose que la plupart des solutions reposent sur la chaîne "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "peut également être amélioré (changez simplement la chaîne, supprimez le xor 17 et le xor 173 au lieu de 188).

J'ai supprimé l'une des recherches en ajoutant conditionnellement 17*17à l, comme nous l'avons fait (plus ou moins) dans la solution de code machine ARM.

Rust a des inférences de type et des fermetures, mais ses conversions (même pour les booléens ou entre les entiers) sont toujours explicites, la mutabilité doit être marquée, elle n’a pas d’opérateur ternaire, d’opérations sur les entiers, par défaut, de panique lors du débordement et de mutations ( l+=1) renvoie l'unité. Je n'ai pas réussi à obtenir une solution plus courte avec les itérateurs, car closures + mapping est encore assez prolixe.

Cela semble faire de Rust un très mauvais choix pour le golf. Néanmoins, même dans un langage qui met l'accent sur la lisibilité et la sécurité plutôt que sur la concision, nous sommes beaucoup trop courts.

Mise à jour: utilisé une fonction anonyme, suggérée par manatwork.

Xavier Bonnetain
la source
1
Sauf en cas d'appel récursif, les fonctions / lambdas anonymes sont acceptables. Vous pouvez donc passer let p=à l'en-tête et ne pas les compter. Pas sûr du ;, comme pour les appels anonymes n'est pas nécessaire: essayez-le en ligne! .
Manatwork
1

05AB1E , 74 octets

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

La première réponse de Jelly du port de @NickKennedy . Je travaillais directement sur un port de la réponse CJam de @ jimmy23013 , mais j’étais déjà à 78 octets et je devais toujours corriger un bogue, qui aurait donc été plus volumineux. Cela peut certainement encore être joué au golf un peu, cependant.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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)

Voir cette astuce 05AB1E de mes (sections Comment compresser les grands entiers? Et Comment compresser des listes entières? ) Pour comprendre pourquoi Ƶfest 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•est 29709448685778434533295690952203992295278432248, ƵŠest 239; et •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвest [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].

Kevin Cruijssen
la source