Generatore lineare congruenziale
Da Wikipedia, l'enciclopedia encyclopedia
In matematica il generatore lineare congruenziale (LCG dall'inglese Linear Congruential Generator) è un algoritmo per la generazione di numeri pseudo-casuali vecchio e molto conosciuto. La teoria sulla quale poggia è semplice da capire e da implementare; inoltre ha il vantaggio di essere computazionalmente leggero.
Il generatore è definito ricorsivamente:
dove è un valore della successione dei numeri pseudocasuali e
- — il "modulo"
- — il "moltiplicatore"
- — l'"incremento" (nel caso speciale in cui si parla di generatore Park-Miller RNG o moltiplicativo)
- — il "seme" o il "valore iniziale"
Il periodo di un LCG è al più m, e per alcune scelte di a può essere molto più piccolo. Il LCG ha un periodo pieno se e solo se:
- e sono coprimi
- è divisibile per tutti i fattori primi di ,
- è un multiplo di 4 se è un multiplo di 4.[1]
Nonostante gli LCG siano generalmente in grado di produrre numeri pseudocasuali decenti, la loro qualità è molto sensibile alla scelta dei coefficienti c, m ed a.
Storicamente, scelte sbagliate hanno portato a implementazioni inefficienti di LCG. Un esempio significativo è RANDU che è stato usato largamente nei primi anni '70 e ha portato a dei risultati che attualmente sono messi in dubbio a causa dell'uso di un LCG di scarsa qualità[2].
Se un generatore congruenziale lineare è inizializzato con un carattere e iterato, il risultato è un semplice cifrario classico chiamato cifrario affine; questo cifrario è facilmente forzabile con un'analisi frequentista standard.