A374720 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, 1, 0, 4, 31, 70, 3183, 39814, 261736, 3371352, 5739969, 293929700, 4459515314, 7926716167, 101442372383, 1872646502198, 24092766475124, 49919329395336, 75900705950969503, 882317013876917212, 32018280652900418322, 883821770134261220212

Offset

1,4

Comments

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.

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

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

j := 0

for i = 0 to n-1,

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

swap S[i] and S[j]

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

Links

Table of n, a(n) for n=1..22.

Wikipedia, RC4.

Example

a(8) = 39814 because starting with S=[0,1,2,3,4,5,6,7], the 8 swaps applied are:
   i | j | S (after i-th swap).
  --------------------------
   0 | 1 | [1, 0, 2, 3, 4, 5, 6, 7]
   1 | 3 | [1, 3, 2, 0, 4, 5, 6, 7]
   2 | 0 | [2, 3, 1, 0, 4, 5, 6, 7]
   3 | 4 | [2, 3, 1, 4, 0, 5, 6, 7]
   4 | 1 | [2, 0, 1, 4, 3, 5, 6, 7]
   5 | 4 | [2, 0, 1, 4, 5, 3, 6, 7]
   6 | 1 | [2, 6, 1, 4, 5, 3, 0, 7]
   7 | 0 | [7, 6, 1, 4, 5, 3, 0, 2]
And then the Lexicographic rank of S=[7, 6, 1, 4, 5, 3, 0, 2] is 39814.

Prog

(Python)
from sympy.combinatorics.permutations import Permutation
def ks(s):
  j, S = 0, list(range(s))
  for i in range(s):
    j = (i + j + 1 + S[i]) % s
    S[i], S[j] = S[j], S[i]
  return S
def a(n): return Permutation(ks(n)).rank()
print([a(n) for n in range(1, 21)])

Crossrefs

Sequence in context: A070522 A087689 A330788 * A210377 A211629 A263760

Adjacent sequences: A374717 A374718 A374719 * A374721 A374722 A374723

Keyword

nonn

Author

Darío Clavijo, Jul 17 2024

Status

approved