周期可调的PRNG

我需要构建一个周期可调的就地伪随机数生成器。另外，在一段时间内不得发生碰撞。也就是说，以下内容必须返回 true：

// prng is "generated" at run-time
// (though a by-hand solution would work)

bool test(func prng, int period) {
    int seed = 0;  // Any number should work
    int cur = seed;

    for (int i = 0; i <= period; ++i) {
        cur = prng(cur);

        if (cur == seed) {
            if (i == period) {
                // We hit our period on target
                return true;
            }

            // Period too low (we hit our seed already!)
            return false;
        }
    }

    // Period too high
    return false;
}

（示例是伪代码；任何常用可读语言（C++、Python、Haskell 等）的答案都是可以接受的。）

PRNG 必须not取决于生成数字时的可变静态。也就是说，我不能有一个包含已返回数字的大表或类似的东西。它应该只依赖给定的输入来生成下一项。

该算法不必具有加密强度（当然），或“强”随机性。然而，x % period是不能接受的;它必须至少是somewhat random.

我研究过线性同余生成器，但这对于我的特定约束来说似乎是错误的路径。

（暴力破解不是一种选择，除非它相对较快（几秒钟）。）

我认为一个好的候选人是斐波那契线性反馈移位寄存器 (LFSR).

您可以从以下位置获取相关信息和算法维基百科 http://en.wikipedia.org/wiki/Linear_feedback_shift_register.

只是摘录：

The initial value of the LFSR is called the seed, and because the operation 
of the register is deterministic, the stream of values produced by the 
register is completely determined by its current (or previous) state. 
Likewise, because the register has a finite number of possible states, it must 
eventually enter a repeating cycle. However, an LFSR with a well-chosen 
feedback function can produce a sequence of bits which appears random and 
which has a very long cycle.
  

The only problem is that the periods for the LFSR are always of the form 2^N-1.
You could overcome this noting that for any wanted period P, choosing the N that gives you the "next" 2^N-1 value leaves potentially 2^(N-1)-1 numbers to supress from the cycle (because if you need to supress more than that, just generate with N-1).

So, to supress k values (k = ((2^N-1) - P) ⋳ {1 ... ,2^(N-1)-1}) you can add a little logic such as

    If (Mod(cur,2(N-1)+1-k) == 0) Then
       cur=Mod(cur+1,2N-1)