Lagged Fibonacci generator

[drew99]

Someone is able to explain me in detail how works the lagged Fibonacci generator?
If j and k are very large, how it's possible that in the first few cycles you can get f (n - j) and f (n - k)?
Thanks in advance for your answers.

[Nominal Animal]

Based on the Wikipedia article on Lagged Fibonacci generator, a type of pseudorandom number generator:

 f(n) = ( f(n-j) OP f(n-k) ) mod m

where j < k < n, m is usually a power of two, and OP is a binary operator (addition, subtraction, multiplication, or exclusive or, in practice).

"Before the first cycle", f(0 .. k-1) must be computed or set first.

In practice, you keep f(n-k) to f(n-1) stored in an array. Then, the next value is obtained via

f[ n mod k ] = f[ (n + k - j) mod k ] OP f[ (n + k - k) mod k ]

where the oldest value in the array is always replaced with the new value, and you only need an array with k entries.

[drew99]

I've understood what you said, but i knew that you can generate pseudorandom sequence of numbers from one seed.
Do I have to set/know n bits at the beginning, if I want to generate a sequence of n bits from some starting bits of a cipher algorithm key with a lagged Fibonacci generator?
I knew that if you want to do this, you only have to initialize the generator with a seed.

[Nominal Animal]

i knew that you can generate pseudorandom sequence of numbers from one seed. Do I have to set/know n bits at the beginning, if I want to generate a sequence of n bits from some starting bits of a cipher algorithm key with a lagged Fibonacci generator?
I knew that if you want to do this, you only have to initialize the generator with a seed.

The lagged Fibonacci generator has k numbers of state. That is, the initial values f(0) .. f(k-1) define the sequence.

A random number seed is a value that can be used to define the generator state. There are two types of seeds:
1) The seed is large enough to be the state.
For example, linear congruential pseudorandom number generators only have one number of state, so the state and the seed are the same thing.
2) Seed is used to generate the state using some other algorithm.
For example, Mersenne Twister has lots of state. A very simple way to generate a full state based on just one input is included in its examples.

You stated that k is large, so the second approach makes more sense. A typical solution is to use a well-known LGC (See here for a list), using the seed for its initial state, to fill in the first k values. To reiterate: You only need the LGC for your initialization (similar to srand() for standard C library random number generator), as it is only used when you seed the state.

You will always need to initialize your generator state before using it. It does not matter how many bits you are going to need from it (although in certain cases some of the state bits will not be used if you need only very few bits); the state is always the same size. (As an analogy, you wouldn't expect a half-built factory to produce half a product, would you? You need the entire factory to have it work at all.)