Home | Perchè la crittografia | Crittografia a chiave segreta | Crittografia a chiave pubblica | Numeri primi | Aritmetica modulare

I numeri casuali sono utilizzati per costruire simulazioni di fenomeni fisico-ingegneristici (reattori nucleari, traffico stradale,...), di problemi decisionali e di finanza (prezzo di un'opzione, previsione Dow-Jones), informatica (crittografia).

I numeri generati al computer sono numeri pseudo-casuali ossia numeri generati da algoritmi matematici in grado di superare test statistici che conferiscono a questi numeri una apparente casualità. Questi test statistici verificano che:
1. I numeri della sequenza generata devono essere uniformemente distribuiti (cioè devono avere la stessa probabilità di presentarsi);

2. I numeri devono risultare statisticamente indipendenti;

3. la sequenza deve poter essere riprodotta;

4. la sequenza deve poter avere un periodo di lunghezza arbitraria.

Nel caso di generazione mediante formule matematiche, i numeri vengono calcolati in modo completamente deterministico e sempre necessitano dell'impostazione di un numero iniziale (seme).
Uno dei metodi matematici più noti per generare numeri casuali, distribuiti uniformemente,è rappresentato dai generatori lineari congruenziali o più brevemente LCG.
il metodo della congruenza lineare permette, dato un valore iniziale

  dove:

  a        è un coefficiente intero strettamente positivo, detto moltiplicatore

 c        è un coefficiente intero non negativo detto  incremento 

 m        è un coefficiente intero strettamente positivo detto modulo

 x i       è il generico numero della sequenza

MOD è l'operazione modulo, cioè a (MOD b) rappresenta il resto della divisione intera tra a e b.

Osservazioni:

• La lunghezza massima raggiungibile dalla sequenza generata, senza ripetizione, vale m;

• Particolari scelte di a e c possono ridurre notevolmente la lunghezza utile della sequenza;

• Il valore di

I criteri necessari e sufficienti che garantiscono l'ottimalità del metodo sono:

1. I parametri c e m devono essere coprimi cioè MCD (c,m) = 1

2. ogni divisore primo di m deve dividere (a-1)

3. se m è multiplo di 4, anche (a-1) lo deve essere.

4. il seme viene fissato in modo hardware, prelevandone il valore da un contatore interno al computer oppure ne viene richiesto il valore all'inizio del processo di generazione.

L'applet java permette di generare una sequenza di numeri casuali con il generatore congruenziale di Lehmer.

Home | Teorema di Eulero | Algoritmo di Euclide | Piccolo teorema di Fermat | Numeri Casuali