fredag 14 september 2018

Invertible additions, mod 2.


Invertible sums with shifted and/or rotated terms.

Under what conditions is this function bijective?
# 0 < r1 < r2 < w
f(x, w, r1, r2) {
  return x ^ ror(w, x, r1) ^ ror(w, x, r2);
}
Rotates, shifts and xors can all be expressed in terms of (binary) matrix addition and multiplication. So I simply wrote some code for Octave to construct the matrices corresponding to $f()$. Here's the relevant snippet in Octave/Matlab:
function retval = rotateMatrix(w, r)
  rs=eye(w); rs(:,1)=[];rs(:,w)=zeros(w,1);
  rr=rs; rr(1,w)=1;
  retval = mod(rr^r, 2);
endfunction

# Now f can be executed as a vector/matrix multiply with the following matrix:
rorrorxorMatrix = mod(eye(w)+rotateMatrix(w, r1)+rotateMatrix(w, r2), 2);

# If rorrorxorMatrix has an inverse, f is invertible.
If and only if the matrix is invertible for a $\{w, r_1, r_2\}$-triple, $w$ denoting the word length, will $f()$ be bijective on $2^w$.

Table 1: Invertible instances of x ^ ror(w, x, r1) ^ ror(w, x, r2) (f())
$w$ Distinct pairs Invertible
3 1 No.
4 3 All
5 6 All
6 10 All but {1, 2}, {1, 5}, {2, 4}, {4, 5}.
7 15 All but {1, 3}, {1, 5}, {2, 3}, {2, 6},{4, 5}, {4, 6}.
8 21 All
9 28 All but {1, 2}, {1, 5}, {1, 8}, {2, 4}, {2, 7}, {3, 6}, {4, 5}, {4, 8}, {5, 7}, {7, 8}
10 36 All
11 45 All
12 55 All but {1, 2}, {1, 5}, {1, 8}, {1, 11}, {2, 4}, {2, 7}, {2, 10}, {4, 5}, {4, 8}, {4, 11}, {5, 7}, {5, 10}, {7, 8}, {7, 11}, {8, 10}, {10, 11}.
13 66 All
14 78 All but 24 pairs.
15 91 All but 37 pairs.
16 105 All
20 171 All
24 253 All but 64 pairs.
32 465 All
36 595 All but 160 pairs.
40 741 All
48 1081 All but 256 pairs.
56 1485 All but 384 pairs.
64 1953 All

2 shifts.

Somewhat similar are
# 0 < {r1, r2} < w, r1 < r2
f2(x, w, r1, r2) {
  return x ^ (x >> r1) ^ (x >> r2);
}

# 0 < l1 < l2 < w
f4(x, w, l1, l2) {
  return x ^ (x << l1) ^ (x << l2);
}
and
# 0 < {r, l} < w, but r may be equal to l.
f3(x, w, r, l) {
  return x ^ (x >> r) ^ (x << l);
}
$f_2()$ and $f_4()$ are bijective for all {r1, r2} or {l1, l2} as described above. ($f_4()$, with two left shifts, has the same properties w.r.t. inverses as $f_2()$.)
For $f_3()$, we're not so lucky. Only some pairs {r, l} give a bijection on $2^w$:
Table 2: Invertible instances of x ^ (x << l) ^ (x >> r) (f3())
$w$ Distinct pairs Invertible pairs $w$ Distinct pairs Invertible pairs
3 4 1 14 169 108
4 9 5 15 196 135
5 16 4 16 225 165
6 25 14 20 361 266
7 36 18 24 529 422
8 49 33 32 961 769
9 64 34 36 1225 1007
10 81 46 40 1521 1223
11 100 55 48 2209 1880
12 121 88 56 3025 2510
13 144 73 64 3969 3330

3 & 4 shifts.

There are also many triples and quads on $2^w$ for $w = \{16, 32, 64\}$ (the most interesting $w$s if one wants to use these on a computer).
# 0 < {r1, r2, l} < w, r1 < r2
f5(x, w, r1, r2, l) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x << l);
}

# 0 < r1 < r2 < r3 < w
f6(x, w, r1, r2, r3) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x >> r3);
}

# 0 < r1 < r2 < w, 0 < l1 < l2 < w
f7(x, w, r1, r2, l1, l2) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x << l1) ^ (x << l2);
}

# 0 < {r1, r2, r3, l} < w, r1 < r2 < r3
f8(x, w, r1, r2, r3, l) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x >> r3) ^ (x << l);
}

# 0 < r1 < r2 < r3 < r4 < w
f9(x, w, r1, r2, r3, r4) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x >> r3) ^ (x >> r4);
}
Table 3: Invertible instances of $f_5, f_6, f_7$ & $f_8$
$w$ Distinct $f_5$, RRL/LLR #Bijective $f_5$ Distinct $f_6$, RRR/LLL Distinct $f_7$, RRLL/LLRR #Bijective $f_7$ Distinct $f_8$, RRRL/LLLR #Bijective $f_8$ Distinct $f_9$, RRRR/LLLL
16 1575 816 455 11025 5451 6825 3408 1365
32 14415 8226 4495 216225 109588 139345 73203 31465
64 123039 75429 39711 3814209 1958503 2501793 1271522 595665
Note that all instances of $f_6$ and $f_9$ are invertible, provided the constants are chosen with the constraints give above their definitions.
The tables can be found here.

Applying the RRC-64-test to the degski64 and Lea64 mixers

In LXM: better splittable pseudorandom number generators (and almost as fast) by Guy L Steele and Sebastiano Vigna, approaches for pseud...