Necesito construir un generador de números pseudoaleatorio en el lugar con un período ajustable. Además, no debe haber colisiones dentro de un período. Es decir, lo siguiente debe devolver verdadero:

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

(El ejemplo es pseudocódigo; una respuesta en cualquier lenguaje legible comúnmente (C ++, Python, Haskell, etc.) es aceptable).

El PRNG debeno dependerá del estado estático mutable al generar los números. Es decir, no puedo tener una tabla grande de números ya devueltos o algo así. Solo debe basarse en la entrada dada para generar el próximo término.

El algoritmo no tiene que ser criptográficamente fuerte (por supuesto) o aleatorio "fuerte". Sin embargo,x % period no es aceptable; tiene que ser al menosalgo aleatorio.

He buscado generadores congruentes lineales, pero ese parece ser el camino equivocado para mis limitaciones específicas.

(Forzar fuerza bruta no es una opción, a menos que sea relativamente rápido (unos segundos)).