Reversibile generatore di sequenza pseudo-casuale

Question

desidero qualche metodo per creare un abbastanza lunga sequenza di numeri casuali che posso scorrere avanti e indietro . Come una macchina con i pulsanti "Avanti" e "precedente", che vi darà numeri casuali.

Qualcosa di simile a una risoluzione di 10-bit (ossia numeri interi positivi in ??un range da 0 a 1023) è sufficiente, e una sequenza di> 100k numeri. E 'per un semplice gioco di tipo app, non ho bisogno di casualità crittografia-resistenza o altro, ma voglio che si sentono abbastanza casuale. Ho un quantità limitata di memoria se disponibile, quindi non posso solo creare un blocco di dati casuali e passare attraverso di essa. Ho bisogno di ottenere i numeri in "tempo interattivo" - io posso facilmente passare qualche ms pensare al numero successivo, ma non in modo confortevole molto di più. Alla fine verrà eseguito su una sorta di microcontrollori, probabilmente solo un Arduino.

ho potuto farlo con un semplice lineare, generatore congruenziale (LCG). Andando avanti è semplice, per andare indietro avrei dovuto memorizzare nella cache i numeri più recenti e memorizzare alcuni punti a intervalli in modo da poter ricreare la sequenza da lì.

Ma forse c'è qualche generatore pseudo-casuale che ti permette di andare sia in avanti e indietro? Dovrebbe essere possibile collegare due registro a scorrimento a retroazione lineare (LFSRs) a rullo in direzioni diverse, no?

O forse posso solo ottenere con garbling il numero di indice utilizzando una funzione hash di qualche tipo? Io vado a provare quella prima.

Altre idee?

Answer 1

ho chiesto a un domanda molto simile al tigsource forum .

di hashing

Almeno nei giochi, una funzione di hash potrebbe probabilmente fare quello che vuoi. Si potrebbe fare in questo modo

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

reversibile lineare congruenziale generatore (LCG)

Per quanto più le persone hanno le punte, un LCG è davvero reversibile. In un LCG, lo stato successivo viene calcolato in questo modo:

x = (a * prevx + c) mod m

Possiamo riordinare questo:

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

Dal momento che una e m sono scelti per essere relativamente privilegiata a un LCG, possiamo trovare l'inverso utilizzando l'algoritmo di Euclide esteso.

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

Il che significa

prevx = ainverse * (x - c) mod m

Se si sceglie m ed una cura, l'algoritmo può avere un periodo di 2 ^ 64

Attuazione

Ho fatto un header-unica implementazione di questo algoritmo nel caso di tutti gli interessati.

Answer 2

Utilizzo di una molto semplice algoritmo di crittografia simmetrica è uno dei modi più semplici per fare questo. Ogni numero casuale è formato da solo crittografare il precedente con qualche chiave fissa e di andare a ritroso che hai appena decifrare.

Si potrebbe guardare il RC4 - Codice http://en.wikipedia.org/wiki/RC4 . Si potrebbe utilizzare un programma chiave molto più piccolo per arrivare a tutti in forma su un Arduino.

Answer 3

Encrypt la 1, 2, 3, ... sequenza con qualsiasi cifra e un tasto qualsiasi.

AES è disponibile su quasi ogni sistema di recente là fuori, ed è fulmini veloce.

Answer 4

Basta invertire l'ordine dei bit in una sequenza crescente di numeri interi. Per esempio (con 8 bit di risoluzione):

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

E 'molto facile per andare avanti e indietro nella sequenza, ed è molto molto più veloce di invocare funzioni di crittografia e hash. Essa ha anche il vantaggio di generare la più lunga possibile sequenza.

E 'sicuramente non è crittograficamente sicuro. Ecco un grafico a dispersione dei valori generati (di nuovo con una risoluzione di 8 bit):

si può facilmente vedere i modelli, anche se potrebbe essere "casuale" abbastanza per voi.

Answer 5

Se un generatore congruenziale lineare è buon uso abbastanza esso. Sono facilmente reversibile. Il punto è che il generatore contrario è anche un LCG. LCGs possono anche saltare in qualsiasi direzione (avanti e indietro) molto veloce.

I dettagli possono essere trovati in The Art of Computer Programming - Volume 2

In particolare la sezione 3.2.1 pagina 10 Equazioni 6-8 di TAOCP e anche esercitare 5 ottenere i risultati desiderati. Nel caso in cui non si può risolvere l'esercizio si possono trovare soluzioni ad esso facilmente, per esempio qui

Answer 6

Anche se sono d'accordo con @BlueRaja che si dovrebbe semplicemente usare AES in modalità "contatore", con un inizio casuale o time-based per la sequenza, AES potrebbe non essere disponibile o fattibile nella vostra situazione incorporato.

Ho trovato questo interessante carta discute come costruire un PRNG reversibile; E 'solo 10 pagine e ha un sacco di esempi di codice. Dare che alla prova se AES non funziona per te.

Answer 7

Si può anche andare all'indietro con un LCG, è solo un altro LCG utilizzando l'inverso del moltiplicatore modulo il modulo, insieme ad un incremento adeguato.

Per i vostri piccoli numeri si può semplicemente usare la forza bruta per cercare l'inverso, in generale, può essere calcolato con un algoritmo GCD estesa.

A meno che il gioco è strettamente per divertimento, senza pali di qualsiasi tipo coinvolte, sceglierei qualcosa crittograficamente sicuro, come ad esempio l'approccio AES suggerito da altri. LCGs e altri generatori di numeri casuali lineari non possono sopportare un avversario intelligente.