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.

public ulong Next()
{
	_state = c * BitOperations.RotateLeft(_state, b);
	return _state;
}

This is a somewhat random function as is, but it has several shortcomings. First, it’s 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).

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.

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.

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’t very well known by all developers, so I’ll highlight some results as needed. If you want to learn more you can read about it over on wikipedia. 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.

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’s to have the same result, in which case we couldn’t 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.

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.

Hypothesis 1: 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.

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.

Bit Length	Count
3	1
4	1
5	2
6	4
7	4
8	1
9	4
10	3
11	6
12	3
13	7
14	7
15	11
16	9
17	13
18	10
19	8
20	9
21	10
22	10
23	11

As can be seen, it looks like there are more such pairs as the bit size increases. I didn’t see any a priori reason why such pairs even have to exist, so this is nice to see.

Now we can get to the first theorem, albeit a trivial one. The number I listed in the table above is actually half the number of rotate-multiply pairs that exist, because every such pair (b,c) has a twin pair (n-b, k), where k is the multiplicative inverse of c. You can see this by just inverting the function f(x)=c*RotateLeft(x,b) for a given bit size n. Let k be the multiplicative inverse of c. Then

x_n+1=c*RotateLeft(x_n,b)
kx_n+1 = RotateLeft(x_n,b)
RotateLeft(kx_n+1, n-b)=x_n

This is just another recurrence relation, although it’s a little different. It’s going backwards, and the multiply happens, then the rotate. This must have the same length as the original, although it’s a slightly different kind of formula. I noticed this empirically before I saw the math, but I’ll call that a theorem. The key is to notice that the relationship alternates rotate and multiply. You could look at the function as multiply first, then rotate, or rotate first, then multiply. You would get a different sequence, but of the same length.

I visualize this by thinking of the sequence obtained by starting from an initial value, rotating it, then multiplying it. For instance, for an 8-bit integer with rotate 3 and multiply 21, starting from 1, we get RotateLeft(1,3)=8, then 8 * 21 = 168, then we repeat the process, obtaining the sequence below.

1,8,168,69,169,77,81,138,82,146,250,215,163,29,97,11,231,…

The first recurrence relationship describes the sequence 1,168,169,81,82,250,163,97,231. The second relationship, going backwards, describes 11,29,215,146,138,77,69,8. So the sequences are related, but they must be of the same length since they are looking at the same chain of operations.

Theorem 1: For a given bit size n, if (b, c) is a rotate-multiply pair with a cycle length m, then (n-b, k), where k is the inverse of c, is another rotate-multiply pair with a cycle length m.

As an example, for 8-bit integers, (3,21) is a full-cycle pair of constants, and so is (5,61), since 3+5=8 and 61 is the multiplicative inverse of 21 modulo 256. The generated sequences are related by the equation above, but are not the same. The first sequence is 1, 168, 169, 81, 82, 250, … The second is 1, 160, 196, 56, 171, 225. This reduces the search space by half. Only the rotates less or equal to than n/2 need to be checked, as the twin pair can be easily deduced. Mark Overton has done some research on this topic, and his appendix C contains a rotate multiplier pair of (18: 3,731,015,275) for 32 bit integers, with period just shy of max. He notes that rotates greater than 16 are less random. Using this theorem, we can construct the twin pair, which would be “more random”, and better suited for his purposes – (14: 583,185,987). With a seed of 1, I have confirmed the period of both of these is 4,294,967,293, as the paper says.

Hypothesis 2: The multiplier c in a full-cycle pair is always congruent to 1 (mod 4)

This is another empirical hypothesis, but I observed it for every full-cycle pair for bit size 3 to 21. This is strong enough evidence for me to use it to reduce my search. Now the code ignores constants c that are congruent to 3 (mod 4). Note that c is congruent to 1 (mod 4) is just a fancy way of saying the constant c divided by 4 has remainder 1, or c % 4 = 1 in c-style syntax.

There will be more articles coming, as I am collecting data and looking through it for patterns that may help me find the constants b and c that work for 64 bit integers. Future articles will discuss cycle statistics, fixed points, roots of unity, and order in cyclic groups. Below is what I have gathered so far. These are full cycle bit length, rotate left, multiply pairs.

Bit Length	Rotate	Multiply	Bit Length	Rotate	Multiply
3	1	5	17	5	60669
4	1	9	17	5	87353
5	2	13	17	6	59053
5	2	17	17	6	65537
6	1	33	17	6	76209
6	2	57	17	7	65537
6	3	29	17	7	95205
6	3	53	17	8	50845
7	1	61	17	8	82897
7	1	65	18	2	225013
7	2	9	18	4	178077
7	2	65	18	5	18125
8	3	21	18	5	112837
9	2	105	18	5	131073
9	2	257	18	5	192957
9	2	289	18	6	143697
9	3	241	18	7	182433
10	1	637	18	9	68729
10	3	513	18	9	237001
10	4	1009	19	2	519821
11	1	225	19	4	59753
11	1	237	19	5	14177
11	1	1813	19	5	128565
11	4	1081	19	5	323697
11	4	1165	19	7	211525
11	5	1025	19	8	409841
12	1	1625	19	9	228385
12	3	725	20	1	634197
12	5	3561	20	1	940945
13	1	7897	20	1	958881
13	2	4033	20	2	283877
13	3	561	20	3	497933
13	3	1965	20	6	727193
13	4	637	20	7	167493
13	4	905	20	7	524289
13	4	5429	20	7	950113
14	1	7457	21	2	78437
14	3	1629	21	2	737153
14	3	9901	21	4	723317
14	3	13377	21	6	321549
14	5	1965	21	6	1523857
14	7	1957	21	7	1740677
14	7	2093	21	8	1933937
15	1	12957	21	9	518925
15	1	16385	21	10	286961
15	1	20121	21	10	1048577
15	2	1929	22	1	2097153
15	2	16385	22	3	1458649
15	4	13609	22	3	2107557
15	4	16385	22	6	1359401
15	5	4781	22	7	547981
15	5	8681	22	7	2383549
15	6	4305	22	8	1358145
15	6	31173	22	8	1690877
16	1	5977	22	8	2158689
16	1	31373	22	9	3168081
16	1	54205	23	1	2502269
16	1	55833	23	5	1856189
16	1	56373	23	5	4194305
16	2	13233	23	6	716037
16	2	55921	23	6	7071101
16	5	17497	23	8	1904041
16	5	23269	23	9	2413621
17	1	39077	23	9	4194305
17	3	38713	23	10	5903105
17	3	65537	23	10	7835097
17	4	82981	23	11	6768185