Preciso construir um gerador de números pseudo-aleatórios no local com um período ajustável. Além disso, não deve haver colisões dentro de um período. Ou seja, o seguinte deve retornar verdadeiro:

// 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;
}

(Exemplo é pseudocódigo; uma resposta em qualquer linguagem comumente legível (C ++, Python, Haskell etc.) é aceitável.)

O PRNG devenão dependem do estado estático mutável ao gerar os números. Ou seja, não posso ter uma grande tabela de números já retornados ou algo assim. Ele deve confiar apenas na entrada fornecida para gerar o próximo termo.

O algoritmo não precisa ser criptograficamente forte (é claro), ou "fortemente" aleatoriamente. Contudo,x % period não é aceitável; tem que ser pelo menosum pouco aleatória.

Eu olhei para geradores congruenciais lineares, mas esse parece ser o caminho errado a seguir para minhas restrições específicas.

(Forçar força bruta não é uma opção, a menos que seja relativamente rápido (alguns segundos).)