login
Permutation rank of the initial state S of length n in an RC4-like Key Scheduling Algorithm with key comprising numbers 1 to n.
0

%I #37 Aug 01 2024 08:32:59

%S 0,1,0,4,31,70,3183,39814,261736,3371352,5739969,293929700,4459515314,

%T 7926716167,101442372383,1872646502198,24092766475124,49919329395336,

%U 75900705950969503,882317013876917212,32018280652900418322,883821770134261220212

%N Permutation rank of the initial state S of length n in an RC4-like Key Scheduling Algorithm with key comprising numbers 1 to n.

%C S is a permutation of {0,...,n-1} and a(n) is its rank among such permutations taken in lexicographic order, starting from rank 0 for the identity permutation.

%C S is constructed from the key by the following procedure, and here key[i] = i+1.

%C S[i] := i for i = 0 to n-1

%C j := 0

%C for i = 0 to n-1,

%C j := (j + S[i] + key[i]) mod n

%C swap S[i] and S[j]

%C The normal RC4 algorithm uses a state S of n=256 bytes and a(256) is its initial state rank on this key.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/RC4">RC4</a>.

%e a(8) = 39814 because starting with S=[0,1,2,3,4,5,6,7], the 8 swaps applied are:

%e i | j | S (after i-th swap).

%e --------------------------

%e 0 | 1 | [1, 0, 2, 3, 4, 5, 6, 7]

%e 1 | 3 | [1, 3, 2, 0, 4, 5, 6, 7]

%e 2 | 0 | [2, 3, 1, 0, 4, 5, 6, 7]

%e 3 | 4 | [2, 3, 1, 4, 0, 5, 6, 7]

%e 4 | 1 | [2, 0, 1, 4, 3, 5, 6, 7]

%e 5 | 4 | [2, 0, 1, 4, 5, 3, 6, 7]

%e 6 | 1 | [2, 6, 1, 4, 5, 3, 0, 7]

%e 7 | 0 | [7, 6, 1, 4, 5, 3, 0, 2]

%e And then the Lexicographic rank of S=[7, 6, 1, 4, 5, 3, 0, 2] is 39814.

%o (Python)

%o from sympy.combinatorics.permutations import Permutation

%o def ks(s):

%o j, S = 0, list(range(s))

%o for i in range(s):

%o j = (i + j + 1 + S[i]) % s

%o S[i], S[j] = S[j], S[i]

%o return S

%o def a(n): return Permutation(ks(n)).rank()

%o print([a(n) for n in range(1, 21)])

%K nonn

%O 1,4

%A _DarĂ­o Clavijo_, Jul 17 2024