I have been playing with genetic programming for several years, attempting to use it to create pseudo random number generators (RNGs) and hash functions. In the course of doing this, with various parameters, I frequently encountered the pseudorandom number generator given by combining a bitwise rotation and a multiply. Sample C# code below, with rotation constant b and multiplication constant c.<\/p>\n\n\n\n

public ulong Next()\n{\n\t_state = c * BitOperations.RotateLeft(_state, b);\n\treturn _state;\n}<\/code><\/pre>\n\n\n\n
This is a somewhat random function as is, but it has several shortcomings. First, it\u2019s not quite random enough by itself unless you only use half of the output. Second, the period is not well known. The period of an RNG is the number of values it returns before it starts repeating. For most commercial RNGs, the period is known mathematically, or at least a lower bound on it is known. For the RNG above, The period might be as short as 1 or as long as 2^64-1, which is the range of possible non-zero values of a ulong (Clearly the value zero is unchanged by the rotate-multiply, so this generator would have to be seeded with a non-zero value).<\/p>\n\n\n\n
Starting from some initial value of _state (an initial, or seed value), and repeatedly calling the function above, it will obviously eventually repeat.  The set of values that it traverses before repeating is called the cycle, which has a length.  The ideal case that we are searching for is a “full cycle”, where the function traverses every possible value before repeating.  We will see that constants b and c which have full cycle are rare.  Most have a number of cycles of varying length.  Some have multiple cycles of length 1, and some sets of constants b and c have thousands of cycles all length 4 or less.  Obviously that doesn’t make for a very good random generator if it keeps returning the same four values in a row, which is why we are trying to find those “full cycle” constants.  <\/p>\n\n\n\n
Recall that bitwise rotation is a common low-level operation in computers, and is quite simple. For comparison, if we were discussing 5 digit decimal numbers, then RotateLeft(12345,2)=34512 and RotateLeft(100,3)=1. Bitwise rotation is the same thing in base 2 arithmetic. Since computers represent everything in base 2 with zeroes and ones, bitwise rotation is natural, and a well-known way of mixing portions of a number in many cryptographic hash functions or ciphers.<\/p>\n\n\n\n
Also, recall that computers use modular arithmetic for integers. That sounds fancier than it is, it really means that the result of any operation is considered as the remainder with the modulus. For instance, among the integers modulo 256 (which would be 8-bit integers), 255+5=4 (260 % 256), and 21*61=1 (1281 % 256). Modular arithmetic isn\u2019t very well known by all developers, so I\u2019ll highlight some results as needed. If you want to learn more you can read about it over on wikipedia<\/a>.  Modular arithmetic is the way integers work by default on computers. If you multiply two unsigned 32-bit integers, the results is given modulo 2^32.<\/p>\n\n\n\n
So we are searching for a pair of integers (b,c) for which the function has a full cycle. It is important that the function f(x) is invertible, otherwise it might be possible for two different x\u2019s to have the same result, in which case we couldn\u2019t have a full cycle. Bitwise rotation is clearly invertible, and the multiplication by c will be invertible as long as c is odd. This is a result from modular arithmetic, in the integers modulo 2^n, every odd number has a unique inverse. So we immediately know that we need only consider odd values for c.<\/p>\n\n\n\n
I brute forced integers of bit size 3-23, and came up with a list of rotate-multiply constants that have a full cycle. Fortunately, there are definitely such constants for every bit size, suggesting that such constants exist, which I call my first hypothesis.<\/p>\n\n\n\n
Hypothesis 1<\/strong>: There are rotate, multiply constants b and c for any given integer size n such that there is a full cycle that contains every non-zero integer.<\/p>\n\n\n\n
The basis for this is purely empirical. The table below shows the number of rotate-multiply pairs that exists at each bit length with a full cycle.<\/p>\n\n\n\n
Bit Length<\/td>
Count<\/td><\/tr>
3<\/td>
1<\/td><\/tr>
4<\/td>
1<\/td><\/tr>
5<\/td>
2<\/td><\/tr>
6<\/td>
4<\/td><\/tr>
7<\/td>
4<\/td><\/tr>
8<\/td>
1<\/td><\/tr>
9<\/td>
4<\/td><\/tr>
10<\/td>
3<\/td><\/tr>
11<\/td>
6<\/td><\/tr>
12<\/td>
3<\/td><\/tr>
13<\/td>
7<\/td><\/tr>
14<\/td>
7<\/td><\/tr>
15<\/td>
11<\/td><\/tr>
16<\/td>
9<\/td><\/tr>
17<\/td>
13<\/td><\/tr>
18<\/td>
10<\/td><\/tr>
19<\/td>
8<\/td><\/tr>
20<\/td>
9<\/td><\/tr>
21<\/td>
10<\/td><\/tr>
22<\/td>
10<\/td><\/tr>
23<\/td>
11<\/td><\/tr><\/tbody><\/table>