Good question. I suspect that it is equivalent to a 32-bit carryless multiplication with 0x1edc6f41, an invertible transformation. There is also a bit reversal (bit reflection), also invertible.
Snobbysays:
aesenc
Rich Geldreichsays:
Exactly- it must be invertible, or you couldn’t decrypt. It’s also incredibly fast.
Cecilsays:
Hrm.
How many of these operations are reversible for all integer inputs?
I’d definitely not consider shifts reversible. I’d probably not even consider addition/subtraction reversible as they aren’t reversible for all inputs. They’re “sometimes reversible” but not “always reversible”.
They are always invertible, for all integer inputs. There are programming-language issues that may interfere, such as undefined behaviors under overflow for signed integers, but they are technical issues.
Jonathan Graehlsays:
Encryption is reversible, although often an IV or other padding are added. Do you think most encryption methods, or at least those that don’t require any more bits for the encrypted output, can be implemented using only the ‘primitives’ you listed?
A function mapping from {1, …, 2^n} to {1, …, 2^n} is reversible if and only if it is a one-to-one mapping. Any such mapping f(x) can be represented by the sequence (f(1), …, f(2^n)). There are (2^n)! such one-to-one sequences. That is, the reversible functions are simply permutations (shufflings) of the numbers from 1 to 2^n. For example, if n = 2, there are (2^2)! = 4! = 24 reversible functions.
How many reversible operations do we know? For 32 bit integers, we know (2^32)! reversible operations.
I guess what you really want to know is, how many of these reversible operations are easy to define? I suppose circuit complexity might be the natural way to define “easy” reversible functions (https://en.wikipedia.org/wiki/Circuit_complexity). If you specify a precise measure of circuit complexity and set a threshold on circuit complexity, there would be an exact answer to the question of how many of the (2^32)! reversible functions have a complexity below the given threshold. However, calculating the exact answer is likely to be very time consuming.
This seems like a rather easy question. Did I miss something? All of these (2^32)! functions could be defined with NOR.
As you point out, there are 2^64 ! permutations on 64-bit words, and that’s about 2^64^{2^64} permutations. To identify one of them, I need about 2^{70} bits. We are talking about exabytes. So it is not practical to address reversible functions as an element of the set of all permutations.
I submit to you that this set might as well be infinite.
In practical software, we see a tiny fraction of all these reversible functions. The question is which ones do we commonly see?
If I asked a programmer to write a reversible function over machine words… I’d get examples from the above blog post… plus, maybe, some minor variations. There are only so many ways to write reversible functions in software today. This comes from the fact that we work with a fairly limited set of operations.
Some of them are not immediately obvious. For example, XORing an odd number of rotations is invertible… but not an even number.
Why would anyone care about this? Well… these are used all over… to generate random numbers, to hash numbers and so forth.
If you are working with ints in Java, then (x >>> (32-b)) | ( x << b) is strictly equivalent to (x >>> (-b)) | ( x << b). For longs, you have that (x >>> (64-b)) | ( x << b) is strictly equivalent to (x >>> (-b)) | ( x << b). So, the better form is (x >>> (-b)) | ( x << b) because it works the same no matter which words you are using.
In C, it is a different matter because it has undefined behaviors. Java does not.
Mr Pedantsays:
Oops, my mistake, you are correct.
TIL In Java, the >>> operator masks the shift amount by 31.
It virtually masks the shift, yes. In reality, at least on an Intel processor, there is no shift needed since the machine instruction only uses the least significant bits during a shift.
It is not just Java. Go, JavaScript… also work the same way.
Mr Pedantsays:
Oh sure, I’m familiar with the x86 assembly opcodes SAR and SHR. It’s just surprising to see that limitation of a particular CPU reflected in a high level language.
My assumption was that in a high level language ((x >>> a) >>> b) === (x >>> (a+b))
And indeed, in python that is the case:
python -c “print (2**65537)>>65536” # == 2
Here are a couple of odd ones, based on TBM. x + c * (x & -x) with an even c, which is invertible because it doesn’t change what x&-x is so the same amount can be subtracted again. Of course the addition can be replaced with XOR. Here’s “proof” (not really, but I believe the bot) for c=2, http://haroldbot.nl/?q=let+c+%3D+2%2C+y+%3D+x+%2B+c+*+%28x+%26+-x%29+in+y+-+c+*+%28y+%26+-y%29 (dev version can handle unbound c)
x + c * ((x ^ (x + 1)) + 1) seems to work for any c (if I believe the bot), for a similar reason.
I can’t think of a use for them, but I found them interesting because they don’t just add a constant, but something that can be recovered.
Marc Reynoldssays:
Seems worth explicitly noting that the inverse of multiply by odd K is the product by its modulo inverse.
I wonder if there is there any accessible coverage of bijections as properties of F_2 matrices.
Jim Applesays:
Feistel permutations, as used in “Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation”: https://arxiv.org/abs/0912.5424
We have that x + (x << a) is (1 + (1<. That is, we have a multiplication by an odd integer. Multiplication by an odd integer is an invertible operation modulo a power of two. Please see this follow-up post for details: https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/
As presented, the signed-shift-based rotation isn’t reversible, but a similar one is, and I’m guessing there was just a transcription error. (x >> b) | (x << (-b)) produces -1 whenever b == -1 (or 63 for Java long, 31 for Java int) and x is any negative number. But, (x << b) ^ (x >> (-b)) is reversible (using XOR instead of OR, and also using the structure of a left rotation, so let’s call this a signed-left-rotation). If you take the result r of an earlier signed-left-rotation and you know the rotation amount b, then long n = (r >>> b) | (r << b); n ^= ((n >> -1) >>> b); will have n == x for, as far as I can tell, any x. This starts to reverse the signed-left-rotation using a typical right-rotation, then if that is a negative number, it flips the lowest b bits, which completes the reversal. If I’m wrong on any of this, please let me know! There could easily be a cleaner way to do this but I don’t know what it would be.
Oops, reversal code should be long n = (r >>> b) | (r << -b); n ^= ((n >> -1) >>> b); . There’s my own transcription error; I had used Long.rotateRight(r, b) in my test code.
I should also mention that, like xor-shift, a xor-based rotation can’t use a rotation amount of 0 (after modulo by the number of bits in type). One way around this is to special-case rotations by 0, and their reversals (Java code): long signedLeftRotate(long x, int b) { return (x << b) ^ (x >> (-b)) | (x & (~((-(b & 63)) >> -1))); } and long reverseSignedLeftRotate(long x, int b) { long n = (x >>> b) | (x << (-b)); return n ^ (((n >> -1) >>> b) & ((-(b & 63)) >> -1)); }
These return x if b is 0, but they’re a substantial amount of extra operations to avoid a possible branch.
Is the x86-64 CRC instruction reversible on 32-bit unsigned integers?
Good question. I suspect that it is equivalent to a 32-bit carryless multiplication with 0x1edc6f41, an invertible transformation. There is also a bit reversal (bit reflection), also invertible.
aesenc
Exactly- it must be invertible, or you couldn’t decrypt. It’s also incredibly fast.
Hrm.
How many of these operations are reversible for all integer inputs?
I’d definitely not consider shifts reversible. I’d probably not even consider addition/subtraction reversible as they aren’t reversible for all inputs. They’re “sometimes reversible” but not “always reversible”.
They are always invertible, for all integer inputs. There are programming-language issues that may interfere, such as undefined behaviors under overflow for signed integers, but they are technical issues.
Encryption is reversible, although often an IV or other padding are added. Do you think most encryption methods, or at least those that don’t require any more bits for the encrypted output, can be implemented using only the ‘primitives’ you listed?
I would be very interested in knowing whether some encryption techniques use primitives we did not include.
I guess you’re looking for operations which (maybe holding some arguments fixed) take an intX_t to an intX_t (not a larger type)?
Right. If you are allowed to generate larger types, then it is a bit too easy.
Taking the int to be a vector over Z_2, multiplication by a square non-singular matrix over Z_2.
How many?
Zero, I don’t give a sh*t…
A function mapping from {1, …, 2^n} to {1, …, 2^n} is reversible if and only if it is a one-to-one mapping. Any such mapping f(x) can be represented by the sequence (f(1), …, f(2^n)). There are (2^n)! such one-to-one sequences. That is, the reversible functions are simply permutations (shufflings) of the numbers from 1 to 2^n. For example, if n = 2, there are (2^2)! = 4! = 24 reversible functions.
How many reversible operations do we know? For 32 bit integers, we know (2^32)! reversible operations.
I guess what you really want to know is, how many of these reversible operations are easy to define? I suppose circuit complexity might be the natural way to define “easy” reversible functions (https://en.wikipedia.org/wiki/Circuit_complexity). If you specify a precise measure of circuit complexity and set a threshold on circuit complexity, there would be an exact answer to the question of how many of the (2^32)! reversible functions have a complexity below the given threshold. However, calculating the exact answer is likely to be very time consuming.
This seems like a rather easy question. Did I miss something? All of these (2^32)! functions could be defined with NOR.
As you point out, there are 2^64 ! permutations on 64-bit words, and that’s about 2^64^{2^64} permutations. To identify one of them, I need about 2^{70} bits. We are talking about exabytes. So it is not practical to address reversible functions as an element of the set of all permutations.
I submit to you that this set might as well be infinite.
In practical software, we see a tiny fraction of all these reversible functions. The question is which ones do we commonly see?
What motivates this question? Why is this interesting? Are you trying to reduce energy consumption below the von Neumann-Landauer limit?
https://en.wikipedia.org/wiki/Reversible_computing
If I asked a programmer to write a reversible function over machine words… I’d get examples from the above blog post… plus, maybe, some minor variations. There are only so many ways to write reversible functions in software today. This comes from the fact that we work with a fairly limited set of operations.
Some of them are not immediately obvious. For example, XORing an odd number of rotations is invertible… but not an even number.
Why would anyone care about this? Well… these are used all over… to generate random numbers, to hash numbers and so forth.
Bitwise not ~
That’s just an instance of XOR with a constant
Rotate needs a tweak: (x >>> (32-b)) | ( x << b)
Mr Pedant: Care to explain?
If you are working with ints in Java, then (x >>> (32-b)) | ( x << b) is strictly equivalent to (x >>> (-b)) | ( x << b). For longs, you have that (x >>> (64-b)) | ( x << b) is strictly equivalent to (x >>> (-b)) | ( x << b). So, the better form is (x >>> (-b)) | ( x << b) because it works the same no matter which words you are using.
In C, it is a different matter because it has undefined behaviors. Java does not.
Oops, my mistake, you are correct.
TIL In Java, the >>> operator masks the shift amount by 31.
It virtually masks the shift, yes. In reality, at least on an Intel processor, there is no shift needed since the machine instruction only uses the least significant bits during a shift.
It is not just Java. Go, JavaScript… also work the same way.
Oh sure, I’m familiar with the x86 assembly opcodes SAR and SHR. It’s just surprising to see that limitation of a particular CPU reflected in a high level language.
My assumption was that in a high level language ((x >>> a) >>> b) === (x >>> (a+b))
And indeed, in python that is the case:
python -c “print (2**65537)>>65536” # == 2
‘Go’ seems to work the same
fmt.Println(7 >> 65536) // == 0
Source: https://golang.org/ref/spec https://golang.org
Java/Javascript OTOH? My mistake… TIL.
Here are a couple of odd ones, based on TBM. x + c * (x & -x) with an even c, which is invertible because it doesn’t change what x&-x is so the same amount can be subtracted again. Of course the addition can be replaced with XOR. Here’s “proof” (not really, but I believe the bot) for c=2, http://haroldbot.nl/?q=let+c+%3D+2%2C+y+%3D+x+%2B+c+*+%28x+%26+-x%29+in+y+-+c+*+%28y+%26+-y%29 (dev version can handle unbound c)
x + c * ((x ^ (x + 1)) + 1) seems to work for any c (if I believe the bot), for a similar reason.
I can’t think of a use for them, but I found them interesting because they don’t just add a constant, but something that can be recovered.
Seems worth explicitly noting that the inverse of multiply by odd K is the product by its modulo inverse.
I wonder if there is there any accessible coverage of bijections as properties of F_2 matrices.
Feistel permutations, as used in “Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation”: https://arxiv.org/abs/0912.5424
What is the inverse of x+ (x<<a)?
We have that x + (x << a) is (1 + (1<. That is, we have a multiplication by an odd integer. Multiplication by an odd integer is an invertible operation modulo a power of two. Please see this follow-up post for details: https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/
Thank You
As presented, the signed-shift-based rotation isn’t reversible, but a similar one is, and I’m guessing there was just a transcription error.
(x >> b) | (x << (-b))produces-1wheneverb == -1(or 63 for Javalong, 31 for Javaint) andxis any negative number. But,(x << b) ^ (x >> (-b))is reversible (using XOR instead of OR, and also using the structure of a left rotation, so let’s call this a signed-left-rotation). If you take the resultrof an earlier signed-left-rotation and you know the rotation amountb, thenlong n = (r >>> b) | (r << b); n ^= ((n >> -1) >>> b);will haven == xfor, as far as I can tell, anyx. This starts to reverse the signed-left-rotation using a typical right-rotation, then if that is a negative number, it flips the lowestbbits, which completes the reversal. If I’m wrong on any of this, please let me know! There could easily be a cleaner way to do this but I don’t know what it would be.Oops, reversal code should be
long n = (r >>> b) | (r << -b); n ^= ((n >> -1) >>> b);. There’s my own transcription error; I had usedLong.rotateRight(r, b)in my test code.I should also mention that, like xor-shift, a xor-based rotation can’t use a rotation amount of 0 (after modulo by the number of bits in type). One way around this is to special-case rotations by 0, and their reversals (Java code):
long signedLeftRotate(long x, int b) { return (x << b) ^ (x >> (-b)) | (x & (~((-(b & 63)) >> -1))); }andlong reverseSignedLeftRotate(long x, int b) { long n = (x >>> b) | (x << (-b)); return n ^ (((n >> -1) >>> b) & ((-(b & 63)) >> -1)); }These return
xifbis 0, but they’re a substantial amount of extra operations to avoid a possible branch.