[Question]
  [
The aim of this challenge is to find an *impossibly* short
implementation of the following function `p`, in the langage of your
choosing. Here is C code implementing it (see 
[this TIO link](https://tio.run/##XZTbahtBEETf9RWLQ0DCnTA9t51Bdn4k@MFIsi1IZCNLIAj@duWULgmJ2GVn@1JdXd2rxZfnxeL4ab1Z/NgvV3fvu@X69evLt@N@875@3qyWw@LlcTu8rb8/DPfDr8nAL5ZoMTWL0c1Hi2E092C5Y7FYMPbKM1j0ZqnwOlq2cbRzdkqEE5sV0M0z3mpeMDfykpWME5QmbK5iXSDpkq862Ty4dbyxWhedbsKN@JrVYBVEbKDkaGM/p4KSiIU0FSKsA1GZNCVAChiMdOc4oxOKLfmVdzFcOVtTIAgh2CgwXinC5QFeVRrQBPoAHzGd0p0sB9LJr9ZMR@TR1eUhsxtQXmDSktGuU/FcGnOVC5F1JBlvUYq04JxpDa3cFaUegB11X0Qv8tFTMXBioRPBiwVgoVsTll5FB6yGdMnadWSUi5RIBNdudOgVlTUe0Fy19dTYxC0b6ngj/prOa0Ez5IgSVyqInDrVGjFG5sI@NBRtpg3icBWuqh@GrQmBGSwYVCEg7hCXYFidcXhhDfBddPMxGXxHHBBjHTriF2PhnGJeNXmR52bJokvIbuWyLaM1kaRf6Ksjhq390r5CUkkoIMXUmNRlVTz90QxECmGDBa1WaQhpjY0pMmI/EdMiadPUBWO/pCetByFBHLMhPmOmAXSWiepJ8mtc@ggYF@cWz8manj4AFy@Jy501EurpYwkK1@bqs0LA0TixSi6Aj/lk8t/HP/33/TC7/BFsV7v9dqM/h8PDfPIxmaw3u@Hn43ozvUY8vW6Hv9lyH@7DfDjcxVJ53N7OhlOcfm9b/E/Tm89LuzGKHmYzQI/H3w "C (gcc) – Try It Online") that also prints its outputs) and a [wikipedia page](https://en.wikipedia.org/wiki/Kuznyechik#The_nonlinear_transformation) containing it.
```
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];
}
```
## What is `p`
`p` is a component of two Russian cryptographic standards, namely the hash function [Streebog](https://en.wikipedia.org/wiki/Streebog) and the block cipher [Kuznyechik](https://en.wikipedia.org/wiki/Kuznyechik). In [this article](https://www.vice.com/en_us/article/43j3wm/experts-doubt-russian-encryption-standard-cryptography-backdoor-streebog-kuznyechik) (and during ISO meetings), the designers of these algorithms claimed that they generated the array `pi` by picking random 8-bit permutations.
## "Impossible" implementations
There are \$256! \approx 2^{1684}\$ permutations on 8 bits. Hence, for a given random permutation, a program that implement it shall not be expected to need fewer than 1683 bits. 
However, we have found multiple abnormally small implementations (which we list [here](https://who.paris.inria.fr/Leo.Perrin/short-implem.html)), for
example the following C program:
```
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;}
```
which contains only 158 characters and thus fits in 1264 bits. [Click here](https://tio.run/##XZBLT4NAFIXXzK8gmDYzPGxBaVFK2xjj2hjjppUIA5QJ43Sc0jqR9LfjxcSYuDn3u4/FOZd6O0r7CyYoPxbl4tAWbH9ZL3smWlPiQTWJEZJYk@4oDmwnygLROlN2k1jrN/XwfP@Sy8e7U9FWT@utzqhcbXUZLK@BZ0A33Rfo1UcI/RwoslyeTN088efxZ814iT2Pj8c69YlOAluneuIHkR1EYazK9qgE4qN81WxAX9Nmkzt8ApDfwmQAP4riM0KD0feMCUw6ZFR7hX@9mj8Rkmls6kUQzqA4DkGGIRUsKmyNCtdyzb/zIRqR@N9AE3jCue@/AQ "C (gcc) – Try It Online") to see that it works.
We talk about an "impossibly" short implementation because, if the
permutation was the output of a random process (as claimed by its
designers), then a program this short would not exist (see [this page](https://who.paris.inria.fr/Leo.Perrin/code-golf.html) for more details).
## Reference implementation
A more readable version of the previous C code is:
```
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;
}
```
The table `k` is such that `k[x] = L(16-x)`, where `L` is linear in the sense that `L(x^y)==L(x)^L(y)`, and where, like in C, `^` denotes the XOR. However, we did not manage to leverage this property to shorten our implementation. We are not aware of any structure in `s` that could allow a simpler implementation---its output is always in the subfield though, i.e. \$s[x]^{16}=s[x]\$ where the exponentiation is done in the finite field. Of course, you are absolutely free to use a simpler expression of `s` should you find one!
The while loop corresponds to the evaluation of a discrete logarithm in the finite field with 256 elements. It works via a simple brute-force search: the dummy variable `a` is set to be a generator of the finite field, and it is multiplied by this generator until the result is equal to `x`. When it is the case, we have that `l` is the discrete log of `x`. This function is not defined in 0, hence the special case corresponding to the `if` statement.
The multiplication by the generator can be seen as a multiplication by \$X\$ in \$\mathbb{F}\_2[X]\$ which is then reduced modulo the polynomial \$X^8+X^4+X^3+X^2+1\$. The role of the `unsigned char` is to ensure that the variable `a` stays on 8 bits. Alternatively, we could use `a=(a<<1)^(a>>7)*(256^29)`, in which case `a` could be an `int` (or any other integer type). On the other hand, it is necessary to start with `l=1,a=2` as we need to have `l=255` when `x` is equal to 1.
More details on the properties of `p` are presented in [our paper](https://eprint.iacr.org/2019/528), with a
writeup of most of our optimizations to obtain the previous short
implementation.
## Rules
Propose a program that implements the function `p` in less than 1683
bits. As the shorter the program, the more abnormal it is, for a given
language, shorter is better. If your language happens to have
Kuznyechik, Streebog or `p` as a builtin, you cannot use them.
The metric we use to determine the best implementation is the program length in bytes. We use the bit-length in our academic paper but we stick to bytes here for the sake of simplicity.
If your language does not have a clear notion of function, argument or
output, the encoding is up to you to define, but tricks like encoding
the value `pi[x]` as `x` are obviously forbidden.
We have already submitted a research paper with our findings on this
topic. It is available [here](https://eprint.iacr.org/2019/528). However, should it be published in a scientific venue, we will
gladly acknowledge the authors of the best implementations.
By the way, thanks to xnor for his help when drafting this question!
  
[Answer]
# AMD64 Assembly (78 bytes or 624 bits of machine code)
```
uint8_t SubByte(uint8_t x) {
    uint8_t y,z;
    uint8_t s[]=
      {1,221,146,79,147,153,11,68,214,215,78,220,152,10,69};
    uint8_t k[]=
      {0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
    if(x) {
      for(y=z=1;(y=(y<<1)^((y>>7)*29)) != x;z++);
      x = (z % 17);
      z = (z / 17);
      x = (x) ? k[x] ^ s[z] : k[z];
    }
    return x^252;
}
```
# 64-bit x86 assembly
```
    ; 78 bytes of AMD64 assembly
    ; odzhan
    bits   64
    %ifndef BIN
      global SubBytex
    %endif
SubBytex:
    mov    al, 252
    jecxz  L2                ; if(x) {
    call   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++
    add    al, al            ; y = y + y
    jnc    $+4               ; skip XOR if no 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]
    test   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:
    ret
```
# Disassembled 64-bit code
```
00000000  B0FC              mov al,0xfc
00000002  67E348            jecxz 0x4d
00000005  E820000000        call 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
```
# 32-bit x86 assembly
```
    ; 72 bytes of x86 assembly
    ; odzhan
    bits   32
    %ifndef BIN
      global SubBytex
      global _SubBytex
    %endif
SubBytex:
_SubBytex:
    mov    al, 252
    jecxz  L2                ; if(x) {
    call   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++
    add    al, al            ; y = y + y
    jnc    $+4               ; skip XOR if no 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          ; if(x == 0) al = z else al = x
    xlatb                    ; al = k[z] or k[x]
    jz     L2                ; if(x == 0) goto L2
    xor    al, [ebx+ecx+17]  ; k[x] ^= k[z]
L2:
    ret
```
# Disassembled 32-bit code
```
00000000  B0FC              mov al,0xfc
00000002  E345              jecxz 0x49
00000004  E820000000        call 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
```
[Answer]
# [CJam](https://sourceforge.net/p/cjam), ~~72~~ ~~67~~ ~~66~~ 63 bytes
```
ri{_2md142*^}es*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD’
˜×EO“N".*Lts:^i
```
`es*` repeats something by the current timestamp, which is a big number, and it would take too long to finish.
Actually testable version, 64 bytes:
```
ri{_2md142*^}256*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD’
˜×EO“N".*Lts:^i
```
```
00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22dd 3024 2612 dc99 d644 0092 0b0a  2b".0$&....D....
00000030: 98d7 454f 934e 0122 2e2a 4c74 733a 5e69  ..EO.N.".*Lts:^i
```
[Try it online!](https://tio.run/##AVMArP9jamFt//9yaXtfMm1kMTQyKl59MjU2Kl0yI35IbWR7NVx9ZXxGbTJiIsOdMCQmEsOcwpnDlkQAwpILCsKYw5dFT8KTTgEiLipMdHM6Xmn//zEyMw "CJam – Try It Online")
[Try all online!](https://tio.run/##PZPNilNBEIV1O@58AhlFIRTaVf1zuwV3Ki4GhXE5zog6CiNkIbqLmYdQ8Af0ZZIHi9/JJIZ7Sd/6OXXqVPW7j2/mm6htcbI5vli8jvm5l5idLTHNTuP25bP5@aK@Wr7/@nQebw/Xf9OduzfXf1a/1z8eX1t9u3Gw@rX@@eTF6vvz64f3Z0dfPj88u9gsPxyffrpnD17OTi5PH21u8YsaFrlbhJtPFmky92RlYLGoGEfjP1l4t1z5nKzYNNnBNjtnwoktChjmBW8zr5g7edlqwQlKFzZPtSGQvMtXnWKe3AbeaDZEZ5hwA1@3lqyBiA2UEjaNq1RQMrGQpkLAOhFVSFMCpIDBSHeOM5xQbNn3vKvhKsW6AkFIySaB8UkRHk/watKAJtAH@MC0TXeyHEgnv1k3HZFHz5CHzGFAeYVJz0a7TsWr0pibXIisI8l4q1KkBedCa2jlrij1AOykdyd6lY@eqoETlU4ELxaApWFdWPoUHbA60mXr@5FRLiiRCW7D6NAbKms8oLlq619jE7diqOOd@H06nxXNkCMkrlQQOXWqNWKMzIV96CjaTRvEYS9cUz8MWxMCM1kyqEJA3CEuwbA64/DKGuDb6eZTNvhOOCDGOgzEr8bCOcW8afIiz8uShUvIYXW3LZN1kaRf6Ksjhq390r5CUkkoIMXUmNRlVTz/1wxECmGDBa02aQhpjY0pMmLfEtMiadPUBWPfpWetByFJHIshPmOmAXSWiepZ8mtcugSMi3OPq2RNTxfAxUvi8haNhHq6LEnh2lxdKwScjBOr5AD8Aw "CJam – Try It Online")
To run this code (on a Linux machine), you need to add the line `en_US.ISO-8859-1 ISO-8859-1` into `/etc/locale.gen` and run `locale-gen`. Then you could use:
```
LANG=en_US.ISO-8859-1 java -jar cjam.jar <source file>
```
Or you could try this equivalent 72 byte UTF-8 version:
```
00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22c3 9d30 2426 12c3 9cc2 99c3 9644  2b"..0$&.......D
00000030: 00c2 920b 0ac2 98c3 9745 4fc2 934e 0122  .........EO..N."
00000040: 2e2a 4c74 733a 5e69                      .*Lts:^i
```
### Explanation
```
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.
```
The characters in the string are:
* 221. See below.
* 48, 36, 38, 18. It's the linear decomposition of k based on the characteristics of L in the question.
* 220, the filler value of array s when only array k is used.
* Array s xor 220 reversed, except for the last element, or the first element before reversed, which is the 221 at the beginning of the string.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly) ~~71~~ 59 bytes
```
H^142ƊHḂ?Ƭi2d17U⁸⁴;$Ḣ?$CµṪạ⁴B¬T;;6ị“Œ0$&ØŀWð⁺Ṫ\ḢĠVı⁻¹]°Ẇ‘^/
```
[Try it online!](https://tio.run/##AXIAjf9qZWxsef//SF4xNDLGikjhuII/xqxpMmQxN1XigbjigbQ7JOG4oj8kQ8K14bmq4bqh4oG0QsKsVDs7NuG7i@KAnMWSMCQmw5jFgFfDsOKBuuG5qlzhuKLEoFbEseKBu8K5XcKw4bqG4oCYXi////8xMjM "Jelly – Try It Online")
[Verify all possibilities](https://tio.run/##HVHbTlNBFH33KwhWSBDUIhaTJjaixmIIUUAbRHlQQClEEgIhFUJ6ACFp8UYT2nopvZzWxDRSSikzc5Ame86ZtPzFnh@puz7Mw57sddlrBafn50PNpn/S3derIn5kGz5VnO2dcvc/1QbTRsXrQpb1ue7BCfLfKDL0NQDFMa/Xg1ZUh384ezdcHTLhhAOypA1BSy8IYKef2UfasIC/hBKKbR1OTF5v0jpkkJXrp/4xtROU5yqPPA35K/KL@oo8h@xUJVYWuxuFReAqIbeRfXw3PIXsYHIYRRpMVUbxCcXnGSiMSkKca@OvF9mx265po6p2kH8bRL7ZgYJPLF9ElQlZmuNoRd4HVbJuNs6guroKx4FGWhsc/iCL1A/fyNR0Cx2TW46FIgI1tCo9qqhMFFGVn5UHMoX8O1omGXHCc6/pnjuQCaK1i8xUMWXOvV1bs6N2XCUHZgaR5ZF9QOsEqm3@iygUgdtHfePIk2t2jQCQRV7sDHXJg3XIUThWZan7@TSKmDbOfEuSEW2IgphQeyj2kG0N2fFr7VB2YmTtcRdhITPvhJFn4dfQ@KhdaxxRIP1ELxPaOCUBZDlZWpEFuomIUpI9oFIaZcqdqGfuk@DlRz5tnKPYubo@goK5VERFbtv76qc2TpDttiHbXKUSQ5C5WS8EWr2T7Zod9SzIONniRitTvk8pP6GOydLdHhLrrB8ScGSZ4oGW2n8JhnxDh5Ovem95LtFDVnXOWm1tFF3edsg@bP4D)
Now rewritten using a reworked version of [jimmy23013’s clever CJam answer](https://codegolf.stackexchange.com/a/186513/42248) so be sure to upvote that one too! Uses only 472 bits (28.0% of the naive approach). @jimmy23013 has also saved another byte!
### Explanation
Stage 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
```
Stage 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
```
Stage 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
```
# Original approach
# [Jelly](https://github.com/DennisMitchell/jelly), ~~71~~ 66 bytes
```
H^142ƊHḂ?Ƭi2d:j@“ÐḌ‘ɗ%?17ị"“p?Ä>4ɼḋ{zẉq5ʂċ¡Ḅ“`rFTDVbpPBvdtfR@‘^ƒ17
```
[Try it online!](https://tio.run/##y0rNyan8/98jztDE6FiXx8MdTfbH1mQapVhlOTxqmHN4wsMdPY8aZpycrmpvaP5wd7cSULDA/nCLncnJPQ93dFdXPdzVWWh6qulI96GFD3e0AGUTitxCXMKSCgKcylJK0oKApsyIOzbJ0Pz///8GAA "Jelly – Try It Online")
[Verify all possibilities](https://tio.run/##HZH9T1JRGMd/769wprmZtmEoLTcpZ4XNOUOXMzfWTCiRlTHNIc5xkWRxrQw2gV5480JbY6mYcM69JNs5lzMu/8Vz/xF66IfzwznP@b6cz/G6fb5Ap@NwWawjIuYAEraL8trI6l3vPTP0nR8BOTRDKSPZb7fYQJN78XDDziMTVqMORA7ugPrh7Wg7rMssDySC0@f@hwtTT1c25ibfrW56nOiScom4xdbBWfdOpVVzLIiol1@JItAcK/bzI/EF6AmQmkht@4eMkp9RkeIHQD6@nl0FknXNgppjiqiA@gnUzx5WmueouDKlv@NALix6w5SqIgr06zTQ/Rug0uWttiwUVsB9ErTYjlekW4pRZ9VgkF0sGjlTouw3kFjr9CXPuLvqBI80NVBjrAHan2FRFgqosiiu8SzPAP0GmoJFmqH1F6AeTLC8F7RDIIpICGX91e6uLutJkZ70TAMpAnkP2iWr9jjaMiszqp9bl4Cmd/UGClgBaHkgMMize@yEnWHW5tAzN6gJU6rbNzlB2wCCWBZxUOMIdEZP3upllWYCq80Nopblfc0Q0AL7ObM0rzeMcwRiQ3ueMqUaBgA54WfbvIRvQqMMJw@A/jIqyB2tPVMYeP2x3ZSuQI3e3HOCSvpETMTu6Mfihyld4m/3ANkPAikEWP52q7SI6m7thi6PveFJrEWlLlN6jJSfmJKGle4PY9hA6xSFzi3Ew7pp/yMI0LAZSq@MjI5dwwWk2qx3fytc7hvvZYVHnX8)
A monadic link or full program that takes a single argument and returns the relevant value of `pi[x]`. This is 536 bits, so under a third of the naive storage of pi. 
Saved 3 bytes by using the method for finding `l` from [jimmy23013’s CJam answer](https://codegolf.stackexchange.com/a/186513/42248) so be sure to upvote that one too!
### Explanation
Stage 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
```
Stage 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
```
Stage 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
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~157 148 140~~ 139 bytes
Modest improvement over the C example. 
```
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;}
```
[Try it online!](https://tio.run/##XY5BS8MwAIXP7a8IkUHSNc5WuxWzuCLiyYOIeFlXXNN2C41ZzdIRqPOv19aL4OXx8d6D9zjZcd5fCMVlW5TLoynE4XJ/10s/Z8HC92r2BJN3/fj68JY3z/enwlQvCaQNsrirDhpJFkZzSoj0voml2LLQs5mdBWHshXFEdWlarYCc5Kt6Pegmg6nlpV6lN8l8oDg13Vd6/RkNvEgVXMtZviH5bf0LWRDH9NwLZcDHViiEO9cZR1t1FDtVFmBMLLuiwC7HG8BOp9h1nEYPQYXgpPChD/7qfL/VuEH/DIsxdc/9Dw "C (gcc) – Try It Online")
# [C (gcc)](https://gcc.gnu.org/), ~~150 142 127~~ 126 bytes
This one depends on gcc and x86 and UTF-8 quirks.
```
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;}
```
[Try it online!](https://tio.run/##S9ZNT07@r5yZl5xTmpJqU1ySkpmvl2H3P0dHK9vWR8khocgtxCUsqSDAqSylJC3IQcm6QKNCszotv0gjx9bI1MxaVzdHq063wlqzwtZIqyKuQt/QyELLyMLUusI2R9XQ3D47GkTFxvkoHdqbqHd4s77qoe2Hd2RlH96UoHJo2@GdStE5@kB5q2wIHWdoYWFd@z8zr0QhNzEzT0OzmosTZFlpXnFmel5qigJIpsLWwFqhwgZkvUKFtrYmFydnQRFQIk1DSTVFR0lHAaE8OSOxSLNAA02gQlPTmqv2PwA "C (gcc) – Try It Online")
Thanks to @XavierBonnetain for -1 and less undefined behaviour.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), ~~65~~ ~~64~~ ~~62~~ ~~59~~ 58 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
ç∙¼≥2▼Uó╤áπ╙º┐╩♫∟öv◘≥δ♦Θ╫»─kRWÑâBG")≥ö0╥kƒg┬^S ΔrΩ►╣Wü Ü╕║
```
[Run and debug it](https://staxlang.xyz/#p=87f9acf2321f55a2d1a0e3d3a7bfca0e1c947608f2eb04e9d7afc46b5257a58342472229f29430d26b9f67c25e5320ff72ea10b95781209ab8ba&i=0%0A1%0A2%0A3%0A4%0A5%0A253%0A254%0A255&a=1&m=2)
Unfortunately, this program uses some instructions that internally use some deprecated stax instructions. I just forgot to update their implementation. This causes some spurious warning to appear, but the results are still correct.
This is inspired by jimmy23013's [excellent answer](https://codegolf.stackexchange.com/a/186513/527). Some parts have been changed to suit stax better.
Stax programs written in printable ASCII have an alternative representation that saves slightly more than 1 bit per byte, since there are only 95 printable ASCII characters.
Here's the ascii representation of this program formatted for "readability" with comments.
```
{                       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
```
[Run this one](https://staxlang.xyz/#c=%7B++++++++++++++++++++%09begin+block%0A++2%7C%25142*S+++++++++++%09given+n,+calculate+%28n%2F2%29%5E%28n%252*142%29%0A+++++++++++++++++++++%09+-+this+seems+to+be+the+inverse+of+the+operation+in+the+while+loop%0Agu+++++++++++++++++++%09use+block+to+generate+distinct+values+until+duplicate+is+found%0A+++++++++++++++++++++%09+-+starting+from+the+input%3B+result+will+be+an+array+of+generated+values%0A2I%5E++++++++++++++++++%091-based+index+of+2+in+the+generated+values%0A17%7C%25+++++++++++++++++%09divmod+17%0Ac%7BUs%7D%3F+++++++++++++++%09if+the+remainder+is+zero,+then+use+%28-1,+quotient%29+instead%0A%7E++++++++++++++++++++%09push+the+top+of+the+main+stack+to+the+input+stack+for+later+use%0A%22i1%7B%25oBTq%5Cz%5E7pSt%2BcS4%22%09ascii+string+literal%3B+will+be+transformed+into+a+variant+of+%60s%60%0A.%2Fo%7BH%7CEF+++++++++++++%09interpret+ascii+codes+as+base-94+integer%0A+++++++++++++++++++++%09+-+this+is+tolerant+of+digits+that+exceed+the+base%0A+++++++++++++++++++++%09then+encode+big+constant+as+into+base+222+digits%0A+++++++++++++++++++++%09+-+this+produces+an+array+similar+to+s%0A+++++++++++++++++++++%09+-+0+has+been+appended,+and+all+elements+xor+220%0A%40++++++++++++++++++++%09use+the+quotient+to+index+into+this+array%0A%22jr%2BR%22%21++++++++++++++%09packed+integer+array+literal+[18,+38,+36,+48]%0AF++++++++++++++++++++%09for+each,+execute+the+rest+of+the+program%0A++%3B++++++++++++++++++%09peek+from+the+input+array,+stored+earlier%0A++v++++++++++++++++++%09decrement%0A++i%3A%40++++++++++++++++%09get+the+i-th+bit+where+i+is+the+iteration+index+0..3%0A++*++++++++++++++++++%09multiply+the+bit+by+value+from+the+array+literal%0A++S++++++++++++++++++%09xor+with+result+so+far%0A+++++++++++++++++++++%09after+the+loop,+the+top+of+the+stack+is+printed+implicitly&i=0%0A1%0A2%0A3%0A4%0A5%0A253%0A254%0A255&m=2)
[Modified version to run for all inputs 0..255](https://staxlang.xyz/#p=a6b7ffca69c7f6eb4d48d97161945c2303454528e57dc8b5095ee18e712e22c155ada79bea2adffa5aa35ce10d63191cccae5db51fe50337f6fec143b3&i=)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~101~~ ~~100~~ ~~98~~ ~~97~~ ~~95~~ 94 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
U•α">η≠ε∍$<Θγ\&@(Σα•₅вV₁[<ÐX*Q#X·₁%Xžy÷Ƶ¹*₁%^₁%U}D17©%DĀiYsès®÷•¾#kôlb¸ù,-ó"a·ú•₅вë\Ƶ∞s®÷Y}sè^
```
-3 bytes thanks to *@Grimy*.
[Try it online](https://tio.run/##yy9OTMpM/f8/9FHDonMblezObX/UueDc1kcdvSo252ac2xyj5qBxbvG5jUDpR02tFzaFPWpqjLY5PCFCK1A54tB2IE814ui@ysPbj209tFMLxI0DEaG1Lobmh1aquhxpyIwsPryi@NC6w9uBZhzap5x9eEtO0qEdh3fq6B7erJR4aPvhXTDDD6@OOQa0eh5YdWQtUF/c//@GAA) or [verify all test cases](https://tio.run/##NVF7T5JRGP8qryBKzOYlK5emlZdlEpZXVNQAdVBOGujSyg1IiXSuRG22mSmWYjTlfpHb9vx4/aO2s7ev8H4ROrj1z9k5e87zu9ocRpN1uiS7XV26NoUge3xCv8W2MDslmKbvCIo22elvoPDLG/ex2SVlsQ5fnZhrQER27iKKvW4kDE9k78YIfg2/fUYFShhk50UNskWPUcr14MAke/fZNoUo9byKIoaHVFDXy86vjvH@ycVW2b1SqcWm6ONobAve17J3TYvgZXyZpemIhRHDvux2Y21puE7cwrdeuGtvSjmKFl2NGvouRTgzO0XW3KRX4X21Q4qwcBN8CNFhE07gohRWkZKybJuluSzZGWpD3oYQdsRU0YNEswoJlkHe2En5NzyC8R7K4Bh7Y7Lzy2M6WhS3KDZkt1XikH5QEL6ip1FM0bGYF/PcxME89oouOmueoQh2WFrNMg9QTiXJPdM5zu4iiAwyS484Ny4GWVxfviQogRV4Kri0@Fxt9V83CjNcGUuxuOx@J@VYGqssDi8@0gk@07nSbmlfwC7nIz8F@8nPU0NsEikONkAJCtwa1UgRLZ1q@aB5FD9/@xR1vDbuR4roEOj44@HFGuemBKuj3KiuNMinLKxoZUn5wwFn9W5UtrBdFjVU3VMzHvvV8qoUGeIQYy34pNc8VeopyV8qvZhfQvIyTmlN@TlRPgaXO@pv06mqo@i0jjgQcNAZj8Dpp7zyBWKzJt5CuuY6ogojJXHxHxxBwyWn3r/6PbLM9yZKV1K7de29fX2d7QMVgtlmt0@b5xVKnuY6AgpB/cpiNVu4EQGFa4oaipX@AQ).
**Explanation:**
[Port of Xavier Bonnetain's C function (1106 bits version) from here](https://who.paris.inria.fr/Leo.Perrin/short-implem.html), with the same improvement [*@ceilingcat* made in his C answer](https://codegolf.stackexchange.com/a/186515/52210) to save 3 bytes, so make sure to upvote him!
```
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)
```
[See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*)](https://codegolf.stackexchange.com/a/166851/52210) to understand why `•α">η≠ε∍$<Θγ\&@(Σα•` is `20576992798525946719126649319401629993024`; `•α">η≠ε∍$<Θγ\&@(Σα•₅в` is `[64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]`; `Ƶ¹` is `285`; `•¾#kôlb¸ù,-ó"a·ú•` is `930891775969900394811589640717060184`; `•¾#kôlb¸ù,-ó"a·ú•₅в` is `[189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]`; and `Ƶ∞` is `188`.
[Answer]
# [Python 3](https://docs.python.org/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
```
[Try it online!](https://tio.run/##VZTda1NBEMXf81fcF20SpnRnP@7dFVOKiM8i4ktJMTFJLY1pSaPEF//1@DsVEeFesjsfZ86cmZvHn4evD7t0Om1m28W35WrRHW07i6XY/Wx5dvV5/@7j20/Lx/dvfqwOmw9XZ6824@M03hwvLjzWaazFtuc@udv8Oj9Ot916@7S@vr/evvBhfjMOx1zCotXVl7xeDas@57BsraW8aXG1Cn55uQVmmNaX1JsYebrO58/5r31@47WeDov97frQzbrrWKLFVC1GNx8shsHcg@WGxWLB2Hp@g0WvlgrXwbINRKZEJGFZvmaecfTmBXMlJVnJOAGoguUp1pSfsCrNPLg1HLG3JhLNBBnxVeuD9YBhAyBHG5qRmwiDJbgRmoGATIZioQICRtpxnNEJxZZkLoY1Z6u6kByCDcLhCjSPB9j06hfWaAFylIkEB8hJ7a2ajqigp8lDRDNQvFC/JqM1p5iU7GVFRh3Jw1EUrb45Z3pBEndFiTSIg97BiszwLwaENkZ6JtUGJzSrgtFVJICpKJRMEkcJWywR1zejG@/RUdoD5KqoX81EjLIlNUg8mZygTWaMkk8di4260mYwI5RnzhXhqmkpOEgycWeIkh@kYMHgRlmRhal0weoI7oXx4oPHkAyCAzaYMOGGvMVYH6eE95qo2PIGiSm9mD4ZVsWK3igt9gxR26LFg5XiJQMx6kQiMn1PsoEDPFdq01YvqWCpmTAiRufPdLQb2hvRZpyDJU0cbxCpbMjL@GCMkjJRU/BBs9AiMwvONZqmov11EZF8vFl6U0W7HhSpFdQHgU6DcWI7nNz5aLSf7Re72/U4ln4y2q@fvm@fv9W73WHMP8Vk0m0e9t2xu9t1/@Lmo8e9Av6Gz7o/H/nkP/vk9Bs "Python 3 – Try It Online")
A function that implements the permutation. The code uses only 7-bit ASCII chars.
Encodes `k` as a Python 3 bytestring, shifted `^64` into the printable range. In contrast, `s` is encoded as the base-256 digits of a numerical constant, and the digits are extracted as `[number]>>[shift]*8&255`. This was shorter than encoding `s` in a string due to the number of escape characters this required, even with an optimal shift `^160` to minimize those.
The discrete-log computation is done backwards. The update `x=x*2^x//128*285` loops forward in the cyclic group by simulating multiplying by the generate, until it reaches the identity `x=1`. We start the discrete log at `l=255` (the cycle length), and decrement it each iteration. To handle the `x=0` case and make it not loop forever, we also terminate when `l=0`, which makes `x=0` map to `l=0` as specified.
---
Python 2 loses out on not having nice bytestrings, so we need to do `map(ord,...)` (ArBo saved a byte here). It lets us use `/` rather than `//` for integer division.
**[Python 2](https://docs.python.org/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
```
[Try it online!](https://tio.run/##VZTda1NBEMXf81fcF20SpnRnP@7dFVOKiM8i4ktJMTVJLU3TEKPEF//1@DsVEeFesjsfZ86cmZvdz8PXp208ndazzeLxdrnojraZxVLsYfa42I2f9ks7u/q8f/fx7afb3fs3P5aH9Yers8mr9fg4jTfHC491GmuxzblP7te/zo/TTbfafFtdP1xvXvgwvxmHYy5h0eryS14th2Wfc7htraW8bnG5DH55ubnwYVpfUnVipHGbz5@zX/v8xms9HRb7u9Whm3XXsUSLqVqMbj5YDIO5B8sNi8WCsfX8BoteLRWug2UbiEyJSMKyfM084@jNC@ZKSrKScQJQBctTrCk/YVWaeXBrOGJvTSSaCTLiq9YH6wHDBkCONjQjNxEGS3AjNAMBmQzFQgUEjLTjOKMTii3JXAxrzlZ1ITkEG4TDFWgeD7Dp1S@s0QLkKBMJDpCT2ls1HVFBT5OHiGageKF@TUZrTjEp2cuKjDqSh6MoWn1zzvSCJO6KEmkQB72DFZnhXwwIrY30TKoNTmhWBaOrSABTUSiZJI4Stlgirm9GN96jo7QHyFVRv5qJGGVLapB4MjlBm8wYJZ86Fht1pc1gRijPnCvCVdNScJBk4s4QJT9IwYLBjbIiC1PpgtUR3AvjxQePIRkEB2wwYcINeYuxPk4J7zVRseUNElN6MX0yrIoVvVFa7BmitkWLByvFSwZi1IlEZPqeZAMHeK7Upq1eUsFSM2FEjM6f6Wg3tDeizTgHS5o43iBS2ZCX8cEYJWWipuCDZqFFZhacazRNRfvrIiL5eLP0pop2PShSK6gPAp0G48R2OLnz0Wg/2y@2d6txLP1ktF99@755/lbvt4cxfxOTSbd@2nfH7n7b/Yubj3Z7BfwNn3V/PvLJf/bJ6Tc "Python 2 – Try It Online")
[Answer]
# JavaScript (ES6), 139 bytes
Similar to the Node.js version, but using characters beyond the ASCII range.
```
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
```
[Try it online!](https://tio.run/##PZTrTtRQFIX/8xTNJCYd2WD3aU97iukAIiQm/jAg/jESGS6KTACBTEZ9G028JD4F82Djt2BG0k5P92Xttdfe5dPh@PDm6Prs6nbl4vL4ZDY77fKJjboQaxt23th5d9YNehvvr3deP38zvHr1bHx8e7q7cff3an36fVDd/Zz@@fZ1@uNzvPs1/d1bPfp4eL0F0OZtftbvd4OVldHjycFo/TSfLE8O8slg0PQfhxRt1F8bPRqun@f89g/O8@Hy6AmH4RoWHTyl2Wb3NgsxWCiTheAGnVA05l5Y1WKxEDG2Nc/CgicrI6@NVdY0tpTxF8qScGIrBbTmFd7aPGJO5JUWK5ygJGFzRWsFUs7zVacyL9xavKG2VnRaE27Al6wurAYRGyhVsKZ9SAWlJBbSVAiwLoiqSFMCpIDBSHeOMzih2Epf8I6Gq6osKRCEorBGYLxShMsLeNXSgCbQB/iA6T7dyXIgnfzakumIPLpaechsDShnyp5Ko12n4kNpzLVciKwjyXijUqQF54rW0MpdUeoB2Eb3XPQoHz1FAydEOhG8WABWtJaEpVfRASshXWlpMTLKBUqUBNet0aHXqKzxgOaqrafGJm6VoY6zUIuJaVwRzZAjSFypIHLqVGvEGJkL@5BQNJk2iMNCuFr9MGxNCMzCCoMqBMQd4hIMqzMOj6wBvrlu3pQG3wYHxFiHFvGjsXBOMa81eZHnZsmCS8jW4nxbGksiSb/QV0cMW/ulfYWkklBAiqkxqcuqePlfMxAphA0WtFpLQ0hrbEyREfs9MS2SNk1dMPZ5eqn1IKQQx8oQnzHTADrLRPVS8mtc@ggYF@cUHpI1PX0ALl4Sl7vSSKinj6VQuDZXnxUCNsaJVfIUsndPl5aOLi9uLkcnq6PLD/nm6sn45PpLno8tm/SzbpDxf4Nn12Xjfrae9fb2t7a29/Z62VrW29l88XJ/d7vXn/0D "JavaScript (Node.js) – Try It Online")
---
# [JavaScript (Node.js)](https://nodejs.org), ~~149~~ 148 bytes
Based on Xavier Bonnetain's C implementation (which is presented [here](https://who.paris.inria.fr/Leo.Perrin/short-implem.html)).
```
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
```
[Try it online!](https://tio.run/##PZRtT9RQEIW/8yuaTcQuDti5t7e9xXQRFBITPxhRvxCILOzqykYQdLO@hL@Oz5FF0m5v5@XMmTNTvpwuTm/OrmdX3ze/Xp5P7u6mfbm0eR9SY@PeW7voZ/1o78d0OrkuB88/Xh@8e/lhfPVmb3H@ffr2uV3tjEf1@uz3r7Nv6fHnwfDo9nZ2/CfGKqSQR6PZ5njdQx72o83N@cbyZL4zLZdPliflcjRqhxshJ5sPt@ePxjsXJb/Dk4ty/GT@lMN4G4sOnvPdbn9UAGghZgvBDV6has29srrDYiFh7BqelQXPFhOvrdXWtrZW8BdiJJzYWgGdeY23MU@YM3nRUo0TlCxsrmSdQOIqX3Vq88qtwxsa60SnM@EGfNmayhoQsYFSB2u7@1RQIrGQpkKAdUVUTZoSIAUMRrpznMEJxRb9gXcyXHVtWYEgVJW1AuOVIlxewauRBjSBPsAHTP/SnSwH0slvLJuOyKOrk4fMzoByxu05Gu06Fe9LY27kQmQdScablCItONe0hlbuilIPwLa6V6In@egpGTgh0YngxQKwqrMsLL2KDlgZ6aLlh5FRLlAiEtx0RofeoLLGA5qrtp4am7jVhjrOQj1MTONKaIYcQeJKBZFTp1ojxshc2IeMotm0QRwehGvUD8PWhMCsrDKoQkDcIS7BsDrj8MQa4Fvp5m00@LY4IMY6dIifjIVzinmjyYs8N0sWXEJ2llbb0loWSfqFvjpi2Nov7SsklYQCUkyNSV1WxeN/zUCkEDZY0GojDSGtsTFFRuz/iGmRtGnqgrGv0qPWg5BKHGtDfMZMA@gsE9Wj5Ne49BEwLs453CdrevoAXLwkLnetkVBPH0ulcG2uPisEbI0Tq@Q5FMfP1tbOLr/eXM4nW/PLT@Xu1mQxuf5ZlgsrlsOiHxX83@DZ98ViWOwUg8P3L17sHx4Oiu1icLD76vX7t/uD4d1f "JavaScript (Node.js) – Try It Online")
### Encoding
In Xavier's original answer, the tables `s[]` and `k[]` are stored in the following string:
```
"@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8"
 \_______________/\__________________________________/
         k                         s
```
The first 17 characters are the ASCII representations of `k[i] XOR 64` and the
next 15 characters are the ASCII representations of `s[i-17] XOR 173`, or `s[i-17] XOR 64 XOR 17 XOR 252`.
All the ASCII codes for `k[i] XOR 64` are matching printable characters, but 7 ASCII codes for `s[i-17] XOR 173` are beyond \$126\$ and need to be escaped. We force them into the printable range by subtracting \$128\$.
Here is what we get:
```
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"
```
By reversing the bitmask formed by the 2nd row in the above table, we get `110010011001001` in binary, or \$25801\$ in decimal.
This bitmask is multiplied by \$128\$, so that we can directly perform a bitwise OR with the extracted bit. Hence the formula:
```
| 3302528 >> i - b & 128
```
---
[Answer]
# [C# (Visual C# Interactive Compiler)](http://www.mono-project.com/docs/about-mono/releases/5.0.0/#csc), 141 bytes
```
x=>{var k="@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è";int l=256,b=17;for(;--l*x!=l;)x=2*x^x/128*285;return l%b>0?k[l%b]^k[b+l/b]^b:k[l/b]^188;}
```
Just a port of the example solution, ported to C#.
[Try it online!](https://tio.run/##bZTbbiNFEIav46eYWEJy4op2qufUw6yzywJ7xQVCCC6CV8RZGzkZJcF2FgvLLwMSB4mnSB4sfL8Piy@wPJqeOvz911/VfTU/u5pPn98@3F69nN4ujOd8MnheDs5XHy5nyc2g@/rH2dtvv/hudP/1mw/vF5NvXj/@c//q6bfz/PGPp79Xvz79/nPx@OfTX92G1KQdhKK00cCrZnI36zVnZ@3p8njQNifLQThdvlu@8BBPQyya2XjxMLtN2k9G5@mrmwvew3c3F6N@@4LF6FMsWniMzfq56YB9MUzup8kgWXUSfqEIFrJoIbh5ZSGtzD21vMZiocBYl7xTCx4tK/isLLeqsm12lhFObK6A2jzHW5oXmCN5mRU5TlCisPkXVgsk2@Vrn9w8davxhtJq0alNuAFftDK1EkRsoOTBqnqbCkpGLKTZIcA6JSonTQmQAgYj1TnO4IRiy3zPuzBceW5RgSCkqVUC45NN@HsKr1IaUAT6AB8wbdKdLAfSyS8tmpbIo38tD5m1AeX00GNmlOvsuN0acykXImtJMt5CKdKCdU5paOWuKNUAbKVnJ3ohHzUVBk4oqETwYgFYWlsUlj5FB6yIdJnFfcvYLrBFRnBZGxV6icpqD2iuvfVW28QtN9TxSPw@nc8CzZAjSFypIHKqVGNEG@kL8xBRNJomiMVeuFL10Gx1CMzUUoMqBMQd4hIMq9MOLxgDfDvdvMoMvhUOiDEONeIXxsA5m3mpzos8D0MWXELWVuympbIoktQLfVVEszVfmldIKgkFpJgKk7qMimcfNQORjbDBglJLaQhptY0u0mLfENMgadJUBW3fpWcaD0JSccwN8WkzBaCzTOyeSX61S4eAdrGOYZus7ukAuHhJXJ5cLWE/HZZU4ZpcHSsErIwVo@QxdNb7Az8bzx/axZxTfzv@JZGN62XYdEZ3d21y2baft2MuqUGymD2Mm45uHF1CuiXShtdLromSRb9/wrVxtEO7mA4JmPSmJ03naDpJevdTmY4HyX8Bm/ij72fTxfir6e241/1yeT@@WozfJ6t0bclPd4tk5euuJZtcO8wE9OiA2uSyncPtaN1Zd6aT3t5zkhyAf9a2ycZ63CX9/@rwgzL27uut@3rnvsa959z7yOfUy/71sN/9YSHog4r4Wj//Cw "C# (Visual C# Interactive Compiler) – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/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]
```
[Try it online!](https://tio.run/##JYvRCoIwGIXvfYrdRJsp5nJp1iwiuo6Ibkopm6IgtmTVX0Gvbqtuzvm@A0c@VHGuB20rshxJDJbiaXd2aJabxTaVq/lNqHw928PxJKd7yGjkaR5qGr2eOgcXpt3XFHStilPGLMFdn4QGKnMEExo2mbo2NaKM2q5ngoHuRVllbxtC4GDSBEMU@cSkARtXNncN9D9gNwgStascR8SW@FJHxLpE7zeRr0f9uJVNWSssMSOk/QA "Python 3 – Try It Online")
Python isn't going to win first prize here, but this is still a 10-byte golf of the best Python program [here](https://who.paris.inria.fr/Leo.Perrin/short-implem.html).
# [Python 3](https://docs.python.org/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])
```
[Try it online!](https://tio.run/##nZAxT8MwEIVn/CtuQbXTRMVu04QoCRVCzAghljaBFDutJeMYE8CAxF8PDmJATIjhfO@d5PP7bF77fafnw2AK1dxveQMuVAWL47AvtpPVrT2/OrvemovTZ963l6uNa@7MycYJVi68Xnp1/P7mz/lD7H3iVToJeUGTjJUuVyWLF43mEV0Ebspi1llssAtYjV1ZJiRgaRyqiBLZfkQOhHoUmKZp3a/VbMarkI/qkFe@8enXiIy@PKrIwEULnZU7qRt145eSDMH/MyNQPvbITRMEsgWXs8yK/slq7HOHbJ6StasQvOylEkBrl40fhV2eU/KLBsH3xb@hINR2FiRIDbbRO@HfW3qYA2Ol7vFYBktCIPqJ6wfDJw "Python 3 – Try It Online")
As a lambda, it's six bytes shorter still. It pains me to have to use `if... else`, but I don't see another option for short-circuiting, given how 0 is a possible answer.
# [Python 3](https://docs.python.org/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])
```
[Try it online!](https://tio.run/##jZDfSsMwFMav7VPkRppsLTNZu9XSdkPEaxHxZuu0M@kWiG0Wq2Yb@DAK/gGfYn2wmooXojdenJzvO5CT7xe5rpZl0W8aGYvsZk4zoB0RE993qni@rtgttMdX6uT8@GIuT4/uaZWfjXcfclQ/Jd7upX7fburnlb97rd9sxxbYRg6N8TAkiY5EQnwvK6iLvY7uEp@UCkqoO2QGdZIMUYcEviNcjHj@6GrAxC2DOAhm1UT0ejR1aKv2aWoa7X6NUOuTgxQ1lOWgVHzBi0xcmqUotIAJ/DfrVGfXcjTVjCSe0QOjDrcbc/ZXvvFDowLbAsLEbqHx0AI8BzoioWLVnSqgye2QfoAmOrXAw5ILBvBMh@0vQR1FGP2iscD3xf@hWFZeKsABL4DKigUz7w0MzJ5UvKhgWxJyhID7E9cMmk8 "Python 3 – Try It Online")
Even shorter in bytes (though I'm not sure about bits, because this isn't pure ASCII anymore), courtesy of ovs.
[Answer]
# [Rust](https://www.rust-lang.org/), ~~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]}
```
[Try it online!](https://tio.run/##NY9da8IwFIbv/RXHwiCpndq42LoSZYzhtcjYxZxQJd2Cx0z7gWExv72mA9@Ll/d5rs4pm6puCw3HXGlCwfbAp/gtQYHSQMbDIePTu@9yKpWuUfdJYJ8XLoiAtNdjU4O5WpQ1OUQdIBVkF6zO@4@392WVv6y/G3l5XW1Mvj8tNkay@ZPfU79m9s/35Mw9J36lQcQ4p9nlR6EEDE1foDWChWZrRjFLQ5byDB9F7IgqAB/iZD62OBAsnWWHz46/nMRK2jiZOLr1atSp9n4@JYrS7P8b13PtDQ "Rust – Try It Online")
This is a port of my solution in C, with a slightly different string, that do not require to xor 17. I expect that most of the solutions based the string "@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8" can be improved as well (just change the string, remove the xor 17, and xor 173 instead of 188).
I removed one of the lookups by conditionally adding `17*17` to `l`, as we (more or less) did in the ARM machine code solution.
Rust has type inference and closures, but its casts (even for booleans or between integers) are always explicit, mutability has to be marked, it does not have a ternary operator, integer operations, by default, panic on overflow, and mutating operations (`l+=1`) returns unit. I did not manage to obtain a shorter solution with iterators, as closures+mapping is still fairly verbose.
This seems to make Rust a pretty bad choice for golfing. Nevertheless, even in a language that stresses readability and safety over conciseness, we're far too short.
Update: used an anonymous function, from manatwork's suggestion.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 74 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
₄FÐ;sÉiƵf^])2k>17‰Dθ_i¦16š}<(Rć16α2в≠ƶ0Kì6ª•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвs<è.«^
```
Port of [*@NickKennedy*'s first Jelly answer](https://codegolf.stackexchange.com/a/186516/52210). I was working on a port of [*@jimmy23013*'s CJam answer directly](https://codegolf.stackexchange.com/a/186513/52210), but I was already at 78 bytes and still had to fix a bug, so it would have been larger. This can definitely still be golfed quite a bit, though.
[Try it online](https://tio.run/##AYEAfv9vc2FiaWX//@KChEbDkDtzw4lpxrVmXl0pMms@MTfigLBEzrhfacKoMTbFoX08KFLEhzE2zrEy0LLiiaDGtjBLw6w2wqrigKI14oC6QMK@w4LDjEzDrMOBxZLCqS7DsMedxaHCq1lXx53FoOKAosa1xaDQsnM8w6guwqte//8xMjM) or [verify all test cases](https://tio.run/##HZH9T5JRHMX/FURNdE6BlFyYVr4sk7Cp5Uu@hKiDatJAl1ZsQIqotRK12aYGWoriEh6BHuRt@x4e2mq7e/oXnn/Erv1073bvzvmccxwuy4R96lLxeTvNrWqV4g@q@myOuReTqompmyp1q@LZ11P85fU7WO@Us1hDUCvl9BAUzzbOsdOF1MhDJfBhCKcDb59SgVIjiueiFtmi3yLnuhGaUAJ7bJNiJD67RsLIPSpodIpn1zXaNz7fovgWK0xYl4JcjW0g8FoJrJoQLSXdLE0HLI4E9hSfD6sLA1ppA1974KtvlHN0XvQ21NA3WeDO7BhZa9NgJZarXLLA4k0IIkbhJhzBSyKWIMpZtsnSHEvxxFqRdyCGLUks@pEyViLFMshbOij/hlcw2k0ZHGLnieL58oAO5qUNSjx2OioQpu8URbDob5BEOpTyUp6HCM1ip@ilH8ZpErDF0hqWuYurVn7yzHSGH7cQRQaZhfvcGxePWHLw6pKiFBbhL@NoyZn6qr8@FKY5GRNZUvG9k3MsjSWWRAAf6Qif6azcaWubwzb3o32K9tE@bw2JcYhcrJ9SFDEM18iCiY5N/ME4jJPfQbWWz8bzyIIZkfY/fj6sZWZSZXddLWrmYy924pPRhRV7KTk95nZX65@36G5wiHYmjtspojNIYXezpre4rDOwuJ73vBIqpbTdODXQCZdu5Na3KQ8f3ptwCq8UpOM6xH7tSmGKDg3wM8R/lZJSSBZczYjUUXTs8j9Hl7mtp7e3o62/TGV1OJ1T1ll1Oa9qDRG1SvPKZrfaOKUKhWp1LSUu/wE).
**Explanation:**
```
₄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)
```
[See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*)](https://codegolf.stackexchange.com/a/166851/52210) to understand why `Ƶf` is `142`; `•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•` is `29709448685778434533295690952203992295278432248`, `ƵŠ` is `239`; and `•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠв` is `[19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]`.
]