For The Love of Computing: The Lagged Fibonacci Generator — Where Nature Meet Random Numbers
For The Love of Computing: The Lagged Fibonacci Generator — Where Nature Meet Random Numbers
One of the greatest challenges we face in computer science is the generation of truly random numbers. Why? Because we generate encryption keys from them, and if someone improves their chances of guessing our random number, they may be able to guess our key. The two main types of random number generators are:
- Pseudo-Random Number Generators (PRNGs). This method repeats the random numbers after a given time (periodic). They are fast and are also deterministic, and are useful in producing a repeatable set of random numbers.
- True Random Number Generators (TRNGs). This method generates a truly random number, and uses somethin which is random. One approach is to monitor the movements of a mouse pointer on a screen or from the pauses in key-strokes. Overall the method is generally slow, especially if it involves human interaction, but is non-deterministic (it cannot be guessed) and aperiodic (it doesn’t repeat after a given time period).
At the core of random numbers is a seed value, and which is used to start the random number generator. Once running, and generating a sequence, the seed value should not be guessable. Each time a new sequence is generated a new random seed is also created.
A typical method that is used in random number generators is to load an initial seed value into registers and then clock the values through, and where the next state is dependent on the values in the registers. This is a fast method, and will always produce a given sequence, and which is dependent on the seed value. It is then a difficult value to reverse the any of the future states back to the original seed.
Lagged Fibonacci Generator
The Fibonacci sequence — also known as the Golden Ratio — is one of the most fundamental characteristics of the Universe. It is created by starting at 0 and 1, and where the next value in the sequence is the addition of the previous two values. Thus we get 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on. Leonardo Fibonacci come up with the sequence when he observed the grow of a rabbit population over the period of a year, but can be seen within many things in nature, including flower petals, pine cones, tree branches, shells, and the shape of galaxies:
In general, a Fibonacci sequence is defined by:
Sₙ=Sₙ₋₁+Sₙ₋₂
and where the current term is the sum of the two previous values. For example if we start at zero and one, we end up with the sequence of:
0,1,1,2,3,5,8,13,21,34,55...
The problem we have in computer security is to generate random numbers that cannot be predicted, as we will often generate encryption keys for our tunneled connections and for encrypted data. We thus need to create a random seed value — typically generated from a truly random event — and then use this to generate a sequence of random values.
We can then generalise the sequence by selecting offset values of j and k, and then defining an operator:
Sₙ≡Sₙ₋ⱼ★Sₙ₋ₖ (mod m), 0<j<k
The operator ★can be either addition (+), subtraction (−), multiplication (×) or X-OR (⊕).
There are various safe pairs of values for j and k, including 3 and 7. So let’s generate with an additional and with a seed value of 6421893 and use a mod of 10.
In this case we will start with the sequence of 6,4,2,1,8,9,3, and where we take the 3rd and 7th element and add them together and take (mod 10). In the first step, we have 2 + 3 (mod 10) which gives 5. This will then become a new random number. Let’s now generate a few other ones [here]:
j= 3 k= 7
Seed: 6421893
6 4 [ 2] 1 8 9 [ 3] --> 5
4 2 [ 1] 8 9 3 [ 5] --> 6
2 1 [ 8] 9 3 5 [ 6] --> 4
1 8 [ 9] 3 5 6 [ 4] --> 3
8 9 [ 3] 5 6 4 [ 3] --> 6
9 3 [ 5] 6 4 3 [ 6] --> 1
3 5 [ 6] 4 3 6 [ 1] --> 7
5 6 [ 4] 3 6 1 [ 7] --> 1
6 4 [ 3] 6 1 7 [ 1] --> 4
4 3 [ 6] 1 7 1 [ 4] --> 0
3 6 [ 1] 7 1 4 [ 0] --> 1
6 1 [ 7] 1 4 0 [ 1] --> 8
1 7 [ 1] 4 0 1 [ 8] --> 9
7 1 [ 4] 0 1 8 [ 9] --> 3
1 4 [ 0] 1 8 9 [ 3] --> 3
4 0 [ 1] 8 9 3 [ 3] --> 4
0 1 [ 8] 9 3 3 [ 4] --> 2
1 8 [ 9] 3 3 4 [ 2] --> 1
8 9 [ 3] 3 4 2 [ 1] --> 4
9 3 [ 3] 4 2 1 [ 4] --> 7
3 3 [ 4] 2 1 4 [ 7] --> 7
The random number then becomes:
5, 6, 4, 3, 6, 1, 7, 1, 4, 0, 1, 8, 9, 3, 3, 4, 2, 1, 4, 7
A simple program to generate this is given next:
import array
import sys
j = 3
k = 7
modval = 10
val = "8675309"
def conv(val):
arr = []
for i in xrange(len(val)):
arr.append(int(val[i]))
return arr
def showvals(val,j,k):
for i in xrange(len(val)):
if (i==j-1):
print "[%3d]"%val[i],
elif (i==k-1):
print "[%3d]"%val[i],
else:
print "%3d"%val[i],
s=conv(val)
print "j=",j," k=",k
print "Seed:\t",val
if (len(s)<k):
print "Value needs to be larger than 7"
exit()
showvals(s,j,k)
for n in xrange(20):
out = (s[j-1] + s[k-1]) % modval
for i in xrange(len(s)-1):
s[i] = s[i+1]
s[len(s)-1] = out
print "-->",out
showvals(s,j,k)
print "-->",out
If we select a value of 100 for the mod value, we get:
j= 3 k= 7
Seed: 6421893
Mod: 100
6 4 [ 2] 1 8 9 [ 3] --> 5
4 2 [ 1] 8 9 3 [ 5] --> 6
2 1 [ 8] 9 3 5 [ 6] --> 14
1 8 [ 9] 3 5 6 [ 14] --> 23
8 9 [ 3] 5 6 14 [ 23] --> 26
9 3 [ 5] 6 14 23 [ 26] --> 31
3 5 [ 6] 14 23 26 [ 31] --> 37
5 6 [ 14] 23 26 31 [ 37] --> 51
6 14 [ 23] 26 31 37 [ 51] --> 74
14 23 [ 26] 31 37 51 [ 74] --> 0
23 26 [ 31] 37 51 74 [ 0] --> 31
26 31 [ 37] 51 74 0 [ 31] --> 68
31 37 [ 51] 74 0 31 [ 68] --> 19
37 51 [ 74] 0 31 68 [ 19] --> 93
51 74 [ 0] 31 68 19 [ 93] --> 93
74 0 [ 31] 68 19 93 [ 93] --> 24
0 31 [ 68] 19 93 93 [ 24] --> 92
31 68 [ 19] 93 93 24 [ 92] --> 11
68 19 [ 93] 93 24 92 [ 11] --> 4
19 93 [ 93] 24 92 11 [ 4] --> 97
93 93 [ 24] 92 11 4 [ 97] --> 97
Random [5, 6, 14, 23, 26, 31, 37, 51, 74, 0, 31, 68, 19, 93, 93, 24, 92, 11, 4,97]
Our values will thus be in the range of 0 to the mod value minus one. In normal circumstances, we use a mod value (m) which is a power of 2, such as 232
, and which will generate 32-bit random values. The seed value used is obviously important, in order for the values not to be predictable. It is a lagged method as we must remember a given number of values from the past generation.
The Lagged Fibonacci Generator is used in Freeciv — an empire-building strategy game — and use the values of {j = 24, k = 55}.
Testing for randomness
One method that we can use to test for randomness is the Monte Carlo method. For this we test to see if we can get close to PI. If we take a mod 256, and a seed of “8675309”, we the first 100 values of:
16, 21, 24, 24, 33, 49, 70, 94, 118, 151, 200, 14, 108, 226, 121, 65, 79, 187, 157, 22, 87, 166, 97, 254, 20, 107, 17, 114, 112, 132, 239, 0, 114, 226,102, 85, 85, 199, 169, 15, 100, 185, 128, 41, 56, 156, 85, 213, 254, 54, 210, 39, 252, 250, 48, 2, 41, 37, 31, 79, 81, 122, 159, 190, 13, 94, 216, 119, 53, 66,160, 120, 239, 36, 102, 6, 126, 109, 145, 247, 253, 123, 232, 121, 112, 109, 232, 208, 73, 185, 38, 14, 222, 39, 224, 6, 20, 242, 25, 249
Next, for the Monte Carlo method, we take the values in pairs, and normalise to a value between 0 and 1, and create a magnitude [here]. We then draw a circle and determine the number of points within the circle as opposed to those outside the circle. If it is random, we will get a value close to PI.
As we can see our value is fairly close to PI (3.14..), but now lets generate 200 values:
16, 21, 24, 24, 33, 49, 70, 94, 118, 151, 200, 14, 108, 226, 121, 65, 79, 187, 157, 22, 87, 166, 97, 254, 20, 107, 17, 114, 112, 132, 239, 0, 114, 226,102, 85, 85, 199, 169, 15, 100, 185, 128, 41, 56, 156, 85, 213, 254, 54, 210, 39, 252, 250, 48, 2, 41, 37, 31, 79, 81, 122, 159, 190, 13, 94, 216, 119, 53, 66,160, 120, 239, 36, 102, 6, 126, 109, 145, 247, 253, 123, 232, 121, 112, 109, 232, 208, 73, 185, 38, 14, 222, 39, 224, 6, 20, 242, 25, 249, 255, 19, 5, 30, 23, 22, 41, 46, 76, 99, 121, 162, 208, 28, 127, 248, 154, 106, 134, 5, 253, 151, 1, 135, 140, 137, 32, 33, 168, 52, 189, 221, 254, 166, 218, 151, 116, 114, 24, 242,137, 253, 111, 135, 121, 2, 255, 110, 245, 110, 112, 111, 221, 210, 64, 176, 31, 252, 206, 14, 190, 221, 217, 167, 181, 115, 80, 41, 208, 133, 248, 72, 113, 65,198, 190, 6, 119, 184, 126, 60, 66, 185, 113, 239, 43, 109, 38, 151, 134, 177,30, 68, 219, 97, 18, 48, 116, 79, 176
And now we get closer to PI (2.88):
If we now try 800 values:
16, 21, 24, 24, 33, 49, 70, 94, 118, 151, 200, 14, 108, 226, 121, 65, 79, 187, 157, 22, 87, 166, 97, 254, 20, 107, 17, 114, 112, 132, 239, 0, 114, 226, 102, 85, 85, 199, 169, 15, 100, 185, 128, 41, 56, 156, 85, 213, 254, 54, 210, 39, 252, 250, 48, 2, 41, 37, 31, 79, 81, 122, 159, 190, 13, 94, 216, 119, 53, 66, 160, 120, 239, 36, 102, 6, 126, 109, 145, 247, 253, 123, 232, 121, 112, 109, 232, 208, 73, 185, 38, 14, 222, 39, 224, 6, 20, 242, 25, 249, 255, 19, 5, 30, 23, 22, 41, 46, 76, 99, 121, 162, 208, 28, 127, 248, 154, 106, 134, 5, 253, 151, 1, 135, 140, 137, 32, 33, 168, 52, 189, 221, 254, 166, 218, 151, 116, 114, 24, 242, 137, 253, 111, 135, 121, 2, 255, 110, 245, 110, 112, 111, 221, 210, 64, 176, 31, 252, 206, 14, 190, 221, 217, 167, 181, 115, 80, 41, 208, 133, 248, 72, 113, 65, 198, 190, 6, 119, 184, 126, 60, 66, 185, 113, 239, 43, 109, 38, 151, 134, 177, 30, 68, 219, 97, 18, 48, 116, 79, 176, 194, 242, 102, 181, 101, 39, 25, 127, 52, 153, 192, 217, 88, 140, 37, 229, 190, 22, 162, 199, 172, 106, 128, 34, 233, 149, 255, 127, 161, 138, 31, 30, 157, 62, 200, 231, 5, 162, 224, 168, 143, 148, 54, 22, 190, 77, 225, 23, 45, 235, 56, 25, 48, 93, 72, 128, 153, 201, 38, 110, 238, 135, 80, 118, 228, 210, 89, 169, 31, 3, 213, 46, 215, 246, 249, 206, 252, 211, 201, 194, 144, 140, 95, 40, 234, 122, 6, 101, 141, 119, 241, 247, 92, 233, 96, 81, 72, 164, 141, 237, 62, 134, 42, 183, 164, 226, 104, 146, 73, 237, 207, 55, 201, 18, 255, 206, 5, 206, 224, 223, 173, 178, 128, 96, 63, 236, 158, 30, 126, 189, 169, 71, 101, 227, 160, 73, 144, 245, 216, 120, 193, 81, 70, 30, 150, 87, 168, 238, 12, 162, 249, 161, 143, 155, 61, 54, 215, 102, 1, 62, 116, 75, 177, 178, 240, 100, 175, 96, 18, 2, 102, 21, 117, 135, 137, 239, 4, 121, 0, 137, 120, 124, 245, 245, 126, 246, 114, 103, 92, 218, 208, 66, 169, 5, 223, 175, 241, 154, 159, 126, 45, 30, 184, 87, 213, 2, 32, 216, 47, 4, 6, 38, 254, 45, 49, 55, 93, 91, 136, 185, 240, 77, 168, 48, 233, 217, 38, 206, 254, 231, 192, 230, 180, 178, 153, 89, 63, 243, 165, 62, 151, 214, 201, 110, 172, 67, 25, 226, 80, 252, 63, 88, 58, 138, 134, 197, 29, 87, 225, 103, 44, 73, 160, 129, 232, 20, 93, 253, 126, 102, 122, 215, 212, 82, 184, 50, 9, 221, 47, 231, 25, 34, 255, 46, 21, 46, 80, 79, 125, 146, 192, 16, 95, 220, 110, 46, 62, 157, 121, 231, 21, 83, 240, 105, 80, 101, 184, 168, 17, 97, 198, 126, 38, 55, 152, 94, 220, 2, 57, 209, 47, 11, 13, 70, 23, 70, 81, 94, 164, 187, 1, 82, 176, 84, 15, 16, 98, 18, 102, 117, 133, 231, 249, 95, 212, 89, 64, 57, 152, 108, 197, 5, 62, 214, 66, 7, 12, 74, 32, 98, 105, 117, 191, 223, 65, 170, 31, 222, 189, 254, 168, 199, 165, 98, 96, 8, 207, 116, 214, 54, 62, 13, 129, 87, 141, 203, 216, 89, 176, 61, 8, 224, 57, 233, 38, 46, 14, 71, 48, 86, 132, 146, 217, 9, 95, 227, 117, 78, 87, 182, 153, 14, 92, 179, 105, 2, 16, 108, 31, 136, 138, 154, 6, 37, 173, 55, 209, 215, 252, 169, 224, 177, 136, 132, 45, 13, 190, 70, 202, 247, 4, 194, 8, 210, 201, 205, 143, 151, 105, 50, 255, 142, 37, 142, 192, 191, 77, 114, 0, 192, 127, 204, 62, 62, 254, 125, 73, 135, 197, 195, 64, 137, 16, 213, 152, 216, 97, 113, 70, 222, 182, 23, 136, 206, 172, 98, 121, 1, 207, 123, 221, 86, 87, 38, 161, 126, 212, 43, 81, 242, 112, 68, 111, 192, 178, 34, 102, 213, 149, 71, 105, 207, 164, 57, 128, 233, 184, 92, 149, 21, 254, 182, 18, 167, 188, 186, 112, 130, 41, 229, 159, 15, 145, 186, 159, 62, 77, 222, 152, 55, 117, 194, 160, 56, 111, 228, 166, 70, 126, 237, 209, 119, 189, 59, 40, 249, 112, 45, 104, 144, 137, 249, 38, 142, 30, 167, 160, 198, 84, 114, 25, 185, 127, 211, 69, 94, 23, 150, 105, 174, 12, 35, 185, 34, 208, 220, 255, 184, 218, 170, 134, 133, 61, 23, 193, 71, 204, 9, 32, 225
We now get even closer to PI (3.02):
Conclusions
If you are writing code, may sure you know how your random numbers are generated. If you want them to be dependable, such as in a simulation or a game, then you should use the same seed. If you want them to be truly random, then you need to make sure they are being generated from a random source.
For me, I see beauty in the simplicity of cryptography, and the creation of random numbers with something that is so fundamental — and beautiful — as the Fibonacci sequence is something that is a beautiful as a piece of art.
The Lagged Fibonacci Generator is here.
The Monte Carlo method is here.