reverse - tabla - para que sirven los numeros pseudoaleatorios

Generador de secuencia pseudoaleatoria reversible

Question

Me gustaría algún tipo de método para crear una secuencia bastante larga de números aleatorios que pueda hojear hacia atrás y hacia adelante . Como una máquina con los botones "siguiente" y "anterior", eso te dará números aleatorios.

Algo como la resolución de 10 bits (es decir, enteros positivos en un rango de 0 a 1023) es suficiente, y una secuencia de> 100k números. Es para una aplicación simple de tipo juego, no necesito encriptación, aleatoriedad de fuerza ni nada, pero quiero que se sienta bastante aleatorio. Sin embargo, tengo una cantidad limitada de memoria disponible, por lo que no puedo generar solo un fragmento de datos aleatorios y revisarlos. Necesito obtener los números en "tiempo interactivo". Puedo pasar unos cuantos minutos pensando en el próximo número, pero no mucho más que eso. Finalmente se ejecutará en algún tipo de microcontrolador, probablemente solo un Arduino.

Podría hacerlo con un simple generador lineal congruente (LCG). Seguir adelante es simple, para ir hacia atrás. Tendría que almacenar los números más recientes y almacenar algunos puntos a intervalos para poder recrear la secuencia desde allí.

¿Pero tal vez haya algún generador pseudoaleatorio que te permita avanzar y retroceder? Debería ser posible conectar dos registros lineales de desplazamiento de realimentación (LFSR) para rodar en diferentes direcciones, ¿no?

¿O tal vez solo puedo arreglarme con el número de índice usando una función hash de algún tipo? Voy a intentar eso primero.

¿Alguna otra idea?

Answer 1

Aunque estoy de acuerdo con @BlueRaja en que debes usar AES en "Modo contador", con un comienzo aleatorio o basado en el tiempo para tu secuencia, AES podría no estar disponible o no ser factible en tu situación incrustada.

Encontré este interesante artículo que analiza cómo construir un PRNG reversible; solo tiene 10 páginas y tiene muchas muestras de código. Dale esto en el intento si AES no funciona para ti.

Answer 2

El uso de un algoritmo de cifrado simétrico muy simple es una de las formas más sencillas de hacerlo. Cada número aleatorio está formado simplemente por encriptar el anterior con una tecla fija y para ir hacia atrás simplemente descifrarlo.

Puede consultar el Código RC4 en http://en.wikipedia.org/wiki/RC4 . Podría usar un horario clave mucho más pequeño para que todo encaje en un arduino.

Answer 3

Encripta la secuencia 1, 2, 3, ... con cualquier cifra y cualquier tecla.

AES está disponible en casi todos los sistemas recientes, y es muy rápido.

Answer 4

Hice una pregunta muy similar en los foros de tigsource .

Hashing

Al menos en los juegos, una función hash probablemente podría hacer lo que quieras. Podrías hacerlo así

class ReversibleRNG {
    int x;
public:
    ReversibleRNG(int seed) : x(seed) {}
    int next(){return yourFavoriteHash(++x);}
    int prev(){return yourFavoriteHash(--x);}
};

Generador congruente lineal reversible (lcg)

Como lo han señalado varias personas, una lcg es realmente reversible. En un lcg, el siguiente estado se calcula así:

x = (a * prevx + c) mod m

Podemos reordenar esto:

x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)

Como a y m se eligen para ser relativamente primos en un lcg, podemos encontrar el inverso utilizando el algoritmo euclid extendido.

ainverse = extEuclid(a, m).x;
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)

Lo que significa

prevx = ainverse * (x - c) mod m

Si elige m y a cuidadosamente, el algoritmo puede tener un período de 2 ^ 64

Implementación

Hice una implementación solo de encabezado de este algoritmo en caso de que alguien esté interesado.

Answer 5

Si un generador congruente lineal es lo suficientemente bueno, úselo. Son fácilmente reversibles. El punto es que el generador inverso también es un LCG. Los LCG también pueden saltar en cualquier dirección (hacia adelante y hacia atrás) muy rápido.

Los detalles se pueden encontrar en El arte de la programación de computadoras - Volumen 2

En particular, la sección 3.2.1. Las ecuaciones 6-8 de TAOCP y también el ejercicio 5 dan los resultados deseados. En caso de que no pueda resolver el ejercicio, puede encontrar soluciones fácilmente, por ejemplo, here

Answer 6

Simplemente invierta el orden de los bits en una secuencia creciente de números enteros. Por ejemplo (con resolución de 8 bits):

• 0 <=> 0
• 1 <=> 128
• 2 <=> 64
• 3 <=> 192
• 4 <=> 32
• etc

Es muy fácil avanzar y retroceder en la secuencia, y es mucho más rápido que invocar funciones de cifrado o hash. También tiene la ventaja de generar la secuencia más larga posible.

Definitivamente no es criptográficamente seguro. Aquí hay un diagrama de dispersión de los valores generados (nuevamente con una resolución de 8 bits):

Puedes ver patrones fácilmente, aunque podría ser lo suficientemente "aleatorio" para ti.

Answer 7

También puede ir hacia atrás con un LCG, es simplemente otro LCG usando el inverso del modulo multiplicador del módulo, junto con un incremento adecuado.

Para sus números pequeños, puede usar la fuerza bruta para buscar el inverso, en general se puede calcular con un algoritmo de GCD extendido.

A menos que su juego sea estrictamente divertido, sin riesgos de ningún tipo, elegiría algo criptográficamente seguro, como el enfoque AES sugerido por otros. Los LCG y otros generadores lineales de números aleatorios no pueden resistir a un adversario inteligente.