Membuktikan bahwa standar kriptografi Rusia terlalu terstruktur

92

Tujuan dari tantangan ini adalah untuk menemukan mustahil pelaksanaan singkat dari fungsi berikut p, dalam bahasamu yang Anda pilih. Ini adalah kode C yang mengimplementasikannya (lihat tautan TIO ini yang juga mencetak hasilnya) dan halaman wikipedia yang memuatnya .

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

apa yang p

padalah komponen dari dua standar kriptografi Rusia, yaitu fungsi hash Streebog dan blok cipher Kuznyechik . Dalam artikel ini (dan selama pertemuan ISO), para desainer algoritma ini mengklaim bahwa mereka menghasilkan array pidengan memilih permutasi 8-bit acak.

Implementasi "Tidak Mungkin"

Ada permutasi pada 8 bit. Oleh karena itu, untuk permutasi acak yang diberikan, program yang mengimplementasikannya tidak diharapkan membutuhkan kurang dari 1683 bit.256!21684

Namun, kami telah menemukan beberapa implementasi kecil yang tidak normal (yang kami sebutkan di sini ), misalnya program C berikut:

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

yang hanya berisi 158 karakter dan dengan demikian cocok dalam 1264 bit. Klik di sini untuk melihat bahwa itu berfungsi.

Kami berbicara tentang implementasi pendek yang "tidak mungkin" karena, jika permutasi adalah output dari proses acak (seperti yang diklaim oleh perancang), maka program yang singkat ini tidak akan ada (lihat halaman ini untuk lebih jelasnya).

Implementasi referensi

Versi yang lebih mudah dibaca dari kode C sebelumnya adalah:

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

Tabelnya ksedemikian sehingga k[x] = L(16-x), di mana Llinear dalam arti itu L(x^y)==L(x)^L(y), dan di mana, seperti dalam C, ^menunjukkan XOR. Namun, kami tidak berhasil memanfaatkan properti ini untuk mempersingkat implementasi kami. Kami tidak mengetahui adanya struktur di smana dapat memungkinkan implementasi yang lebih sederhana --- outputnya selalu di subfield, yaitu mana eksponensial dilakukan di bidang hingga. Tentu saja, Anda benar-benar bebas menggunakan ekspresi yang lebih sederhana jika Anda menemukannya!s[x]16=s[x]s

Loop sementara sesuai dengan evaluasi logaritma diskrit di bidang hingga dengan 256 elemen. Ini bekerja melalui pencarian brute-force sederhana: variabel dummy adiatur untuk menjadi generator dari bidang yang terbatas, dan itu dikalikan dengan generator ini hingga hasilnya sama dengan x. Ketika itu terjadi, kita memiliki itu ladalah log diskrit x. Fungsi ini tidak didefinisikan dalam 0, maka kasus khusus sesuai dengan ifpernyataan tersebut.

Perkalian oleh generator dapat dilihat sebagai perkalian oleh dalam yang kemudian direduksi modulo polinomial . Peran dari ini adalah untuk memastikan bahwa variabel tetap pada 8 bit. Atau, kita bisa menggunakan , dalam hal ini bisa menjadi (atau tipe integer lainnya). Di sisi lain, perlu untuk memulai karena kita perlu memiliki ketika sama dengan 1.XF2[X]X8+X4+X3+X2+1unsigned charaa=(a<<1)^(a>>7)*(256^29)aintl=1,a=2l=255x

Rincian lebih lanjut tentang sifat-sifat pdisajikan dalam makalah kami , dengan penulisan sebagian besar optimasi kami untuk mendapatkan implementasi singkat sebelumnya.

Aturan

Usulkan program yang mengimplementasikan fungsi pdalam waktu kurang dari 1683 bit. Semakin pendek program, semakin abnormal, untuk bahasa tertentu, semakin pendek lebih baik. Jika bahasa Anda memiliki Kuznyechik, Streebog atau psebagai builtin, Anda tidak dapat menggunakannya.

Metrik yang kami gunakan untuk menentukan implementasi terbaik adalah panjang program dalam byte. Kami menggunakan bit-length dalam makalah akademis kami, tetapi kami tetap pada byte di sini demi kesederhanaan.

Jika bahasa Anda tidak memiliki gagasan yang jelas tentang fungsi, argumen, atau keluaran, penyandian terserah Anda untuk menentukan, tetapi trik seperti penyandian nilai pi[x]seperti xyang jelas-jelas dilarang.

Kami telah mengirimkan makalah penelitian dengan temuan kami tentang topik ini. Ini tersedia di sini . Namun, jika diterbitkan di tempat ilmiah, kami dengan senang hati akan mengakui penulis implementasi terbaik.

Omong-omong, terima kasih kepada xnor atas bantuannya saat menyusun pertanyaan ini!

picarresursix
sumber
12
Saya harap seseorang mengirimkan jawaban di Seed.
Robin Ryder
6
Demikian pula, dapatkah, misalnya, kode brainfuck dinilai 3 bit per karakter jika tidak ada nops? Dan apakah 1683 bits at mostpembatasan ketat atau tujuan?
seseorang
31
" Jika permutasi adalah hasil dari proses acak (seperti yang diklaim oleh desainernya), maka program yang singkat ini tidak akan ada " Saya tidak setuju (meskipun tidak masalah untuk tantangan). Jika itu adalah hasil dari proses acak, kemungkinan besar program seperti itu tidak ada; atau akan sulit ditemukan
Luis Mendo
8
@Grimy Pernyataan yang menyatakan bahwa program yang singkat ini tidak ada adalah yang konseptual (bukan pemrograman). Menggunakan istilah Anda, itu milik dunia matematika murni, bukan ke dunia pemrograman
Luis Mendo
7
Mungkin sudah diketahui, tetapi untuk berjaga-jaga: hanya menghasilkan 8 nilai berbeda: (dimulai dengan dan dengan asumsi ) . 1 , 10 , 68 , 79 , 146 , 153 , 220 , 221 i = 1 s 0 = 0ssaya XOR ssaya-11,10,68,79,146,153,220,221i=1s0=0
Arnauld

Jawaban:

35

AMD64 Assembly (78 byte atau 624 bit kode mesin)

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

    jika (x) {
      untuk (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;
}

Perakitan x86 64-bit

    ; 78 byte perakitan AMD64
    ; odzhan
    bit 64

    % ifndef BIN
      SubBytex global
    %berakhir jika

SubBytex:
    mov al, 252
    jecxz L2; jika (x) {
    hubungi 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 ++
    tambahkan al, al; y = y + y
    jnc $ + 4; lewati XOR jika tidak ada carry
    xor al, 29;
    cmp al, cl; if (y! = x) goto 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]
    tes dl, dl; if (x == 0) goto L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    membasahi

Kode 64-bit dibongkar

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

Perakitan x86 32-bit

    ; 72 byte perakitan x86
    ; odzhan
    bit 32

    % ifndef BIN
      SubBytex global
      global _SubBytex
    %berakhir jika

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; jika (x) {
    hubungi 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 ++
    tambahkan al, al; y = y + y
    jnc $ + 4; lewati XOR jika tidak ada carry
    xor al, 29;
    cmp al, cl; if (y! = x) goto 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; jika (x == 0) al = z lain al = x
    xlatb; al = k [z] atau k [x]
    jz L2; if (x == 0) goto L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    membasahi

Bongkar kode 32-bit

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 memanggil 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 tambahkan 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
sumber
1
Jawaban bagus! Karena OP sedang mencari jumlah bit, ini (85 byte) keluar menjadi 680 bit , menggunakan 8 bit per byte, atau 595 bit menggunakan 7 bit per byte (mungkin karena semua karakter adalah ASCII). Anda mungkin bisa lebih pendek jika Anda mengompres ke set karakter yang lebih ketat.
Cullub
1
Selamat datang di PPCG; solusi pertama yang bagus.
Shaggy
9
@ Cullub Maksud saya adalah, kode dalam jawaban ini hanya C / Assembler yang dikompilasi, jadi jumlah byte bukan dari kode yang diberikan, tetapi dari kode yang dikompilasi. Dan itu bukan ASCII.
ArBo
7
Hanya untuk klarifikasi, 84 byte adalah ukuran kode mesin setelah ini dirakit? Jika demikian, judul harus diperbarui untuk mencerminkan bahwa ini adalah jawaban kode mesin dan bukan jawaban perakitan.
Potato44
1
Dan BTW, Anda tidak harus menggunakan konvensi panggilan standar; Anda dapat menggunakan konvensi khusus di mana RBX dipenuhi panggilan, menghemat 2 byte untuk push / pop. (Dan di mana uint8_targs diperpanjang nol menjadi 64-bit untuk JRCXZ). Juga, jika Anda menulis kode tergantung posisi, Anda dapat memasukkan alamat tabel ke register dengan 5-byte mov ebx, imm32alih - alih 6-byte call/ pop. Atau gunakan itu sebagai disp32di mov al, [table + rax], tetapi itu mungkin hilang karena Anda sudah punya dua xlatbdan movsudah. Trik panggilan + pop shellcode memang menang vs 7 byte RIP-relatif LEA dengan data setelah ret, meskipun.
Peter Cordes
23

CJam ,72 67 66 63 byte

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

es* mengulangi sesuatu dengan cap waktu saat ini, yang merupakan angka besar, dan akan memakan waktu terlalu lama untuk selesai.

Sebenarnya versi yang dapat diuji, 64 byte:

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

Cobalah online!

Coba semua online!

Untuk menjalankan kode ini (pada mesin Linux), Anda perlu menambahkan baris en_US.ISO-8859-1 ISO-8859-1ke /etc/locale.gendan jalankan locale-gen. Maka Anda bisa menggunakan:

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

Atau Anda dapat mencoba versi UTF-8 72 byte yang setara ini:

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

Penjelasan

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.

Karakter dalam string adalah:

  • 221. Lihat di bawah.
  • 48, 36, 38, 18. Ini adalah dekomposisi linear k berdasarkan karakteristik L dalam pertanyaan.
  • 220, nilai pengisi array s ketika hanya array k yang digunakan.
  • Array s xor 220 dibalik, kecuali untuk elemen terakhir, atau elemen pertama sebelum dibalik, yang merupakan 221 pada awal string.
jimmy23013
sumber
Apa yang akan Anda lakukan dengan set daya? PS Saya mungkin akan mencuri trik melakukan operasi lapangan yang terbatas secara terbalik. Sangat rapi.
Peter Taylor
@PeterTaylor Anda bisa mendapatkan larik k menggunakan set daya [48 36 38 18] (atau kebalikannya) dengan pemesanan paling mudah, dan kurangi masing-masing dengan xor. Tetapi dalam bahasa-bahasa golf yang digunakan dalam pertanyaan ini sejauh ini, hanya 05AB1E yang memiliki urutan yang benar. Jelly dan Stax rupanya memiliki gagasan berbeda tentang apa yang menurut saya harus jelas.
jimmy23013
Saat ini saya sedang dalam proses golf jawaban Anda untuk 05AB1E. Apa nilai integer untuk string Anda "Ý0$&Ü™ÖD�’\n˜×EO“N"?
Kevin Cruijssen
@KevinCruijssen Apakah Anda bertanya tentang apa artinya, atau nilai numeriknya (yang bisa Anda lihat dari hex dump)?
jimmy23013
@ jimmy23013 Ah, tentu saja .. Lupa tentang dump-hex ..
Kevin Cruijssen
19

Jelly 71 59 byte

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

Cobalah online!

Verifikasi semua kemungkinan

Sekarang ditulis ulang menggunakan versi CJam pintar jimmy23013 yang dikerjakan ulang jadi pastikan untuk mengunggahnya juga! Hanya menggunakan 472 bit (28,0% dari pendekatan naif). @ jimmy23013 juga menyimpan byte lain!

Penjelasan

Tahap 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

Tahap 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

Tahap 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

Pendekatan asli

Jelly , 71 66 byte

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

Cobalah online!

Verifikasi semua kemungkinan

Tautan monadik atau program lengkap yang mengambil argumen tunggal dan mengembalikan nilai yang relevan pi[x]. Ini adalah 536 bit, jadi di bawah sepertiga penyimpanan pi naif.

Disimpan 3 byte dengan menggunakan metode untuk menemukan ldari jawaban CJam jimmy23013 jadi pastikan untuk meng-upgrade yang juga!

Penjelasan

Tahap 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

Tahap 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

Tahap 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
sumber
1
59 byte , versi lain .
jimmy23013
15

C (gcc) , 157 148 140 139 byte

Perbaikan sederhana dibandingkan contoh 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;}

Cobalah online!

C (gcc) , 150 142 127 126 byte

Yang ini tergantung pada kebiasaan gcc dan x86 dan 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;}

Cobalah online!

Berkat @XavierBonnetain untuk -1 dan perilaku yang kurang terdefinisi.

plafon
sumber
10

05AB1E , 101 100 98 97 95 94 byte

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

-3 byte terima kasih kepada @Grimy .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

Port fungsi Xavier Bonnetain C (versi 1106 bit) dari sini , dengan peningkatan yang sama dengan @ceilingcat yang dibuat dalam jawaban C-nya untuk menghemat 3 byte, jadi pastikan untuk membesarkannya!

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)

Lihat ini ujung 05AB1E saya (bagian Cara kompres bilangan bulat besar? Dan Cara kompres daftar bilangan bulat? ) Untuk memahami mengapa •α">η≠ε∍$<Θγ\&@(Σα•adalah 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅вadalah [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹adalah 285; •¾#kôlb¸ù,-ó"a·ú•adalah 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅вadalah [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; dan Ƶ∞adalah 188.

Kevin Cruijssen
sumber
@Grimy Terima kasih, saya selalu lupa golf seperti itu dengan daftar integer terkompresi .. (PS: Anda dapat mengelilingi kode yang berisi `dalam komentar dengan dua di antaranya di kedua sisi. Yaitu dengan 'bukannya`:' 'code'code ''.)
Kevin Cruijssen
Ups, maaf tentang pemformatan yang kacau. Saya tahu tentang menggandakan backtick, tetapi saya tidak menyadari daftar yang dikompresi memiliki backtick di dalamnya. Juga: s^=> ^(XOR komutatif). Sebenarnya, tidak s^_sama dengan Q?
Grimy
@ Terima kasih kotor! Anda memang benar. Kami pada dasarnya memeriksa apakah salah satu dari tiga hal berikut ini truthy untuk keluar dari loop: i==0 || X==0 || X==1.
Kevin Cruijssen
10

Stax , 65 64 62 59 58 byte

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

Jalankan dan debug itu

Sayangnya, program ini menggunakan beberapa instruksi yang secara internal menggunakan beberapa instruksi stax yang sudah usang. Saya hanya lupa untuk memperbarui implementasinya. Ini menyebabkan beberapa peringatan palsu muncul, tetapi hasilnya masih benar.

Ini terinspirasi oleh jawaban jimmy23013 yang luar biasa . Beberapa bagian telah diubah agar sesuai dengan stax lebih baik.

Program Stax yang ditulis dalam ASCII yang dapat dicetak memiliki representasi alternatif yang menghemat sedikit lebih dari 1 bit per byte, karena hanya ada 95 karakter ASCII yang dapat dicetak.

Berikut representasi ascii dari program ini yang diformat untuk "keterbacaan" dengan komentar.

{                       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

Jalankan yang ini

Versi modifikasi untuk dijalankan untuk semua input 0..255

rekursif
sumber
Stax memiliki Spower set. Anda bisa mendapatkan set daya [18 38 36 48], indeks dan kurangi dengan xor. (Saya tidak tahu Stax dan saya tidak yakin itu akan lebih pendek.)
jimmy23013
Saya pikir pemesanan stax untuk himpunan bagian yang diproduksi oleh Soperator tidak dalam urutan yang tepat untuk itu berfungsi. mis. "abc"SJ(powerset dari "abc" bergabung dengan spasi) menghasilkan "a ab abc ac b bc c".
Rekursif
8

Python 3 , 151 byte

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

Cobalah online!

Fungsi yang mengimplementasikan permutasi. Kode hanya menggunakan karakter ASCII 7-bit.

Dikodekan ksebagai bytestring Python 3, bergeser ^64ke kisaran yang dapat dicetak. Sebaliknya, sdikodekan sebagai basis-256 digit dari konstanta numerik, dan digit diekstraksi sebagai [number]>>[shift]*8&255. Ini lebih pendek daripada penyandian sdalam string karena jumlah karakter melarikan diri yang diperlukan ini, bahkan dengan pergeseran yang optimal ^160untuk meminimalkan mereka.

Perhitungan diskrit-log dilakukan mundur. Pembaruan x=x*2^x//128*285loop maju dalam grup siklik dengan mensimulasikan mengalikan dengan menghasilkan, sampai mencapai identitas x=1. Kami memulai log diskrit di l=255(panjang siklus), dan mengurangi setiap iterasi. Untuk menangani x=0kasing dan membuatnya tidak berulang, kami juga mengakhiri kapan l=0, yang membuat x=0peta menjadi l=0seperti yang ditentukan.


Python 2 kalah karena tidak memiliki bytestrings yang bagus, jadi perlu kita lakukan map(ord,...)(ArBo menyimpan byte di sini). Itu memungkinkan kita menggunakan /daripada //untuk pembagian integer.

Python 2 , 156 byte

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

Cobalah online!

Tidak
sumber
7

JavaScript (ES6), 139 byte

Mirip dengan versi Node.js, tetapi menggunakan karakter di luar rentang 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

Cobalah online!


JavaScript (Node.js) ,  149  148 byte

Berdasarkan implementasi C Xavier Bonnetain (yang disajikan di sini ).

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

Cobalah online!

Pengkodean

Dalam jawaban asli Xavier, tabel s[]dan k[]disimpan dalam string berikut:

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

17 karakter pertama adalah representasi ASCII k[i] XOR 64dan 15 karakter berikutnya adalah representasi ASCII s[i-17] XOR 173, atau s[i-17] XOR 64 XOR 17 XOR 252.

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

Inilah yang kami dapatkan:

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: Ini hanya catatan tambahan, tidak terkait dengan jawaban di atas.

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

Cobalah online!

Arnauld
sumber
3

Python 3 , 182 byte

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]

Cobalah online!

Python tidak akan memenangkan hadiah pertama di sini, tapi ini masih 10 byte golf dari program Python terbaik di sini .

Python 3 , 176 byte

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

Cobalah online!

Sebagai lambda, ini masih enam byte lebih pendek. Sangat menyakitkan saya harus menggunakan if... else, tapi saya tidak melihat opsi lain untuk hubungan arus pendek, mengingat bagaimana 0 adalah jawaban yang mungkin.

Python 3 , 173 byte

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

Cobalah online!

Bahkan lebih pendek dalam byte (meskipun saya tidak yakin tentang bit, karena ini bukan ASCII murni lagi), milik ovs.

ArBo
sumber
3 byte lebih pendek dengan menggunakan karakter literal alih-alih \x..lolos
ovs
@ terima kasih! Mungkin sedikit meningkatkan jumlah bit (tidak yakin mana yang paling penting untuk OP), jadi saya akan menyimpan jawaban lama saya juga.
ArBo
2

Rust , 170 163 byte

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

Cobalah online!

Ini adalah port solusi saya dalam C, dengan string yang sedikit berbeda, yang tidak perlu untuk xor 17. Saya berharap bahwa sebagian besar solusi berdasarkan string "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "dapat ditingkatkan juga (cukup ganti string, hapus xor 17, dan xor 173 alih-alih 188).

Saya dihapus salah satu pencarian dengan kondisional menambahkan 17*17untuk l, seperti yang kita (kurang lebih) lakukan di solusi ARM kode mesin.

Karat memiliki tipe inferensi dan penutup, tetapi gipsnya (bahkan untuk boolean atau antara bilangan bulat) selalu eksplisit, kemampuan berubah harus ditandai, ia tidak memiliki operator ternary, operasi integer, secara default, panik pada overflow, dan operasi bermutasi ( l+=1) mengembalikan unit. Saya tidak berhasil mendapatkan solusi yang lebih pendek dengan iterator, karena penutupan + pemetaan masih cukup bertele-tele.

Ini sepertinya membuat Rust pilihan yang buruk untuk bermain golf. Namun demikian, bahkan dalam bahasa yang menekankan keterbacaan dan keamanan daripada keringkasan, kita terlalu pendek.

Pembaruan: menggunakan fungsi anonim, dari saran manatwork.

Xavier Bonnetain
sumber
1
Kecuali ketika dipanggil secara rekursif, fungsi anonim / lambda dapat diterima, sehingga Anda dapat pindah let p=ke Header dan tidak menghitungnya. Tidak yakin tentang ;, karena untuk panggilan anonim tidak diperlukan: Cobalah online! .
manatwork
1

05AB1E , 74 byte

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

Port jawaban pertama Jelly @NickKennedy . Saya sedang mengerjakan port dari jawaban @ jimmy23013 CJam secara langsung , tetapi saya sudah mencapai 78 byte dan masih harus memperbaiki bug, jadi itu akan lebih besar. Ini pasti masih bisa golf sedikit.

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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)

Lihat ini ujung 05AB1E saya (bagian Cara kompres bilangan bulat besar? Dan Cara kompres daftar bilangan bulat? ) Untuk memahami mengapa Ƶfadalah 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•adalah 29709448685778434533295690952203992295278432248, ƵŠadalah 239; dan •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвadalah [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].

Kevin Cruijssen
sumber