Symmetric Bijective Algorithm for Integers

Question

I need an algorithm that can do a one-to-one mapping (ie. no collision) of a 32-bit signed integer onto another 32-bit signed integer.

My real concern is enough entropy so that the output of the function appears to be random. Basically I am looking for a cipher similar to XOR Cipher but that can generate more arbitrary-looking outputs. Security is not my real concern, although obscurity is.

Edit for clarification purpose:

1. The algorithm must be symetric, so that I can reverse the operation without a keypair.
2. The algorithm must be bijective, every 32-bit input number must generate a 32-bit unique number.
3. The output of the function must be obscure enough, adding only one to the input should result big effect on the output.

Example expected result:

F(100) = 98456
F(101) = -758
F(102) = 10875498
F(103) = 986541
F(104) = 945451245
F(105) = -488554

Just like MD5, changing one thing may change lots of things.

I am looking for a mathmetical function, so manually mapping integers is not a solution for me. For those who are asking, algorithm speed is not very important.

Answer 1

If your goal is simply to get a seemingly random permutation of numbers of a roughly defined size, then there is another possible way: reduce the set of numbers to a prime number.

Then you can use a mapping of the form

f(i) = (i * a + b) % p

and if p is indeed a prime, this will be a bijection for all a != 0 and all b. It will look fairly random for larger a and b.

For example, in my case for which I stumbled on this question, I used 1073741789 as a prime for the range of numbers smaller than 1 << 30. That makes me lose only 35 numbers, which is fine in my case.

My encoding is then

((n + 173741789) * 507371178) % 1073741789

and the decoding is

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Note that 507371178 * 233233408 % 1073741789 == 1, so those two numbers are inverse the field of numbers modulo 1073741789 (you can figure out inverse numbers in such fields with the extended euclidean algorithm).

I chose a and b fairly arbitrarily, I merely made sure they are roughly half the size of p.

Answer 2

Draw a large circle on a large sheet of paper. Write all the integers from 0 to MAXINT clockwise from the top of the circle, equally spaced. Write all the integers from 0 to MININT anti-clockwise, equally spaced again. Observe that MININT is next to MAXINT at the bottom of the circle. Now make a duplicate of this figure on both sides of a piece of stiff card. Pin the stiff card to the circle through the centres of both. Pick an angle of rotation, any angle you like. Now you have a 1-1 mapping which meets some of your requirements, but is probably not obscure enough. Unpin the card, flip it around a diameter, any diameter. Repeat these steps (in any order) until you have a bijection you are happy with.

If you have been following closely it shouldn't be difficult to program this in your preferred language.

For Clarification following the comment: If you only rotate the card against the paper then the method is as simple as you complain. However, when you flip the card over the mapping is not equivalent to (x+m) mod MAXINT for any m. For example, if you leave the card unrotated and flip it around the diameter through 0 (which is at the top of the clock face) then 1 is mapped to -1, 2 to -2, and so forth. (x+m) mod MAXINT corresponds to rotations of the card only.

Answer 3

I will try to explain my solution to this on a much simpler example, which then can be easily extended for your large one.

Say i have a 4 bit number. There are 16 distinct values. Look at it as if it was a four dimensional cube: 4 dimensional cube http://www.ams.org/featurecolumn/images/january2009/klee8.jpg.

Every vertex represents one of those numbers, every bit represents one dimension. So its basicaly XYZW, where each of the dimensions can have only values 0 or 1. Now imagine you use a different order of dimensions. For example XZYW. Each of the vertices now changed its number!

You can do this for any number of dimensions, just permute those dimensions. If security is not your concern this could be a nice fast solution for you. On the other hand, i dont know if the output will be "obscure" enough for your needs and certainly after a large amount of mapping done, the mapping can be reversed (which may be an advantage or disadvantage, depending on your needs.)

Answer 4

Split the number in two (16 most significant bits and 16 least significant bits) and consider the bits in the two 16-bit results as cards in two decks. Mix the decks forcing one into the other.

So if your initial number is b31,b30,...,b1,b0 you end up with b15,b31,b14,b30,...,b1,b17,b0,b16. It's fast and quick to implement, as is the inverse.

If you look at the decimal representation of the results, the series looks pretty obscure.

You can manually map 0 -> maxvalue and maxvalue -> 0 to avoid them mapping onto themselves.

Answer 5

Can you use a random generated lookup-table? As long as the random numbers in the table are unique, you get a bijective mapping. It's not symmetric, though.

One 16 GB lookup-table for all 32 bit values is probably not practical, but you could use two separate 16-bit lookup tables for the high-word and the low word.

PS: I think you can generate a symmetric bijective lookup table, if that's important. The algorithm would start with an empty LUT:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Pick the first element, assign it a random mapping. To make the mapping symmetric, assign the inverse, too:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Pick the next number, again assign a random mapping, but pick a number that's not been assigned yet. (i.e. in this case, don't pick 1 or 3). Repeat until the LUT is complete. This should generate a random bijective symmetric mapping.

Answer 6

Take a number, multiplies by 9, inverse digits, divide by 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

Should be obscure enough !!

Edit : it is not a bijection for 0 ending integer

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

You can always add a specific rule like : Take a number, divide by 10 x times, multiplies by 9, inverse digits, divide by 9, multiples by 10^x.

And so

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00t it works !

Edit 2 : For more obscurness, you can add an arbitrary number, and substract at the end.

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129