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.

9 kommentarer:

  1. Is there any way to dump to a file all of the valid (or invalid) r1,r2 pairs for f2 and/or f3? I have no idea how I would write the necessary Octave code to even find the inverse of a matrix. Haroldbot ( http://haroldbot.nl ) can find this info for 32-bit numbers, but I'm interested in 64-bit numbers at this point in time. Thanks for this post, by the way; I didn't know any of the XORed-multiple-bit-op expressions you listed were ever bijections except for x ^ rotate(x, a) ^ rotate(x, b).

    SvaraRadera
    Svar
    1. Yes, currently compiling the files for 32 and 64 bits mentioned above, adding (x >> r1) ^ (x >> r2) ^ (x >> r3) and (x >> r1) ^ (x >> r2) ^ (x >> r3) ^ (x >> r4) for completeness. If you haven't seen me posting a link to a repo in a day or two, please remind me.

      Radera
  2. Thanks so much! I'm currently testing some variants on the MurmurHash3 finalizer, inspired by your earlier post, that are meant to work with gamma=1. It is proving a challenge. Using paired xorshifts seems to help somewhat when one of the two xorshift-multiply steps is removed, with failures coming in on PractRand at 8TB instead of much earlier. I found a generator/unary hash that works well using two rotates and a little less multiplication, since gamma is 1; I'll post it on your MurmurHash finalizer post. If can switch to paired shifts, I suspect some platforms may optimize this a little better.

    SvaraRadera
    Svar
    1. Link provided above and tables updated. Enjoy!

      Radera
  3. This is great! Just so you are aware, there seems to be a mistake in the repo's README.md; the shifts are given as `(x << a) ^ (x >> b)` but should be `x ^ (x << a) ^ (x >> b)`, which would match this post. Thanks a bunch!

    SvaraRadera
    Svar
    1. Woops. Thanks for pointing that out. Fixed.

      Radera
  4. Thanks for the research. I was surprised to learned that, while the primitives of the form x^=rot(x,k) are not invertible, it turns out there exist some bijections of the form x^=rot(x,k1)^rot(x,k2) - in fact, all of them, under 64 bits.

    So, when I see x^=rot(x,k) in a hash function, does this usually mean a blunder? Am I right to understand that, since x^=(x>>k) is a bijection, it should work much better? By the way, if x^=(x>>k) is a bijection, then some of the cases of x^=(x>>k1)^(x>>k2) that you study are redundant, specifically those that can be decomposed into x^=(x>>k1), x^=(x>>k2).

    Then there is another primitive in modern hash functions based on wide multiplication and combining the halves:

    uint128_t w = (uint128_t) v * PRIME;
    return (w >> 64) ^ (uint64_t) w; // wmul-xor
    return (w >> 64) + (uint64_t) w; // wmul-add

    It mixes bits well in both dicrections. Is it a bijection? Perhaps only under certain PRIMEs?

    SvaraRadera
    Svar
    1. Den här kommentaren har tagits bort av skribenten.

      Radera
    2. Whether x ^= rot(x, k) is a blunder would depend on the intent.
      If the intent is to not make a bijection, it's a blunder.

      I am not sure about
      y = x ^ x >> s1 ^ x >> s2;
      vs
      y1 = x ^ x >> s1;
      y2 = y1 ^ y1 >> s2;
      being identical. Assuming SR(w, s) is the s bits right shift operator [matrix] for w-bit words, the first can be written as
      y = mod(x * (eye(w) + SR(w, s_1) + SR(w, s_...) + SR(w, s_n), 2)
      and the other would be
      y_n = mod(x * (eye(w) + SR(w, s_1)) * (eye(w) + SR(w, s_...)) * eye(w) + SR(w, s_n)), 2)
      It's not obvious to me that there are tuples <s_1, s_..., s_n>, for n shifts, s.t. y = y_n. My guess is that there aren't.

      Assuming that PRIME is *odd*, it doesn't have to be prime, and that
      the inverse of (I + SR(128, 64)) exists (I assume it does but I haven't checked 128 bit shifts at all), wmul-xor is bijective.

      Note that
      (x >> s) + x is *not* bijective. Not sure if it there are any pairs <w, s> any for which it is.

      Radera

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