Aritmetica modulare e generazione di numeri pseudo-casuali

E' noto, nell'aritmetica tradizionale, che il quoziente, q, è il risultato della divisione fra il dividendo x e il divisore m, mentre R è l'eventuale resto.

Nell'aritmetica modulare, in luogo della usuale notazione impiegata per la divisione, si utilizza questa notazione: x(mod m)= R, e si dice: "x modulo m è uguale a R".

In pratica, la divisione in aritmetica modulare, è ottenuta secondo questo procedimento:

1) si calcola la divisione con la tecnica tradizionale (x : m = q);
2) si moltiplica la parte intera del quoziente per il divisore e la si sottrae dal dividendo (x - m * Q);
3) il risultato della sottrazione, è R

esempi:

I calcoli proposti come esempi, possono essere effettuti anche con la calcolatrice fornita con Windows®. In modalità scientifica, la calcolatrice si presenta come nella figura sotto.

Ad esempio, per effettuare il calcolo 74 mod 7, digitate il numero "7", poi clic su "mod", poi digitate il numero 7, infine clic su "=".
Per un numero esponenziale, come 16³⁷ mod 77 = 58, digitate "37", poi clic su x^y, quindi clic su "MOD", poi digitate "37", infine clic su "="

Per la notazione: x(mod m) = R, valgono le seguenti proprietà:

• è sempre R < m

  tutti i possibili resti sono una quantità pari ad m e con valori compresi fra 0 ed m-1

• se x < m, allora x (mod m)= x

  esempio: 31(mod 45)= 31 (per definizione);

• se x = m, allora x(mod x)= 0

• se x+1 = m, allora x(mod (m)= 1

  esempio: 38 (mod 37) = 1

• x(mod 1)= 0

• 0(mod m)= 0

Con gli elementi di aritmetica modulare esaminati, è possibile generare numeri pseudo-casuali. I metodi di generazione di numeri pseudo-casuali prevalentemente usati sono i cosiddetti metodi congruenziali (si dice che a è congruente con b se a mod m = b mod m), basati sulla divisione mod m

Per generare numeri casuali, si possono utilizzare tre tipi di metodi congruenziali:

1. Metodo additivo: r_i+1=r_i+r_i-1(mod m)
2. Metodo moltiplicativo: r_i+1=ar_i(mod m)
3. Metodo misto: r_i+1=(ar_i+b)(mod m)

dove: r_i, a, b, m sono interi non negativi e r_i è compreso tra 0 ed m.
Vengono chiamati: a moltiplicatore, b incremento e m modulo, mentre r_o (valore iniziale della sequenza), è detto seme.
Tutti questi metodi danno origine a sequenze periodiche, con periodo minore o al più uguale ad m. Per ottenere il periodo massimo, devono essere rispetate queste condizioni:

• b ed m devono essere primi tra loro;
  
• si determinano i numeri primi, p, divisori di m: a-1 deve essere multiplo di p;
  
• se m è multiplo di 4, a-1 deve essere multiplo di 4.

La tabella riporta un semplice esempio per la generazione di numeri casuali compresi fra 0 e 7 (mod 7) e fra 0 e 8 (mod 8). Pero', nel primo caso si sono scelti parametri ottimizzati; nel secondo, no (m è multiplo di 4, e per a si è scelto il valore 16 invece di a-1=17). Il lettore puo' verificare che la relazione (17x+5) mod 8 produce effettivamente una sequenza pseudocasuale di periodo 8.

In realtà, per la generazione di numeri pseudocasuali, si sceglie per m il valore piu' elevato possibile, al fine di ottenere un periodo elevato. Infatti, comunemenet i linguaggi di programmazione (Basic, C, Java, JavaScript, ecc.) dispongono di funzioni già predisposte per restituire un valore casuale. Ma, per evitare di ottenere ogni volta gli stessi numeri, la generazione viene automaticamente effettuata con m molto elevati.

E' importante scegliere m in modo tale da assicurarsi una sequenza di periodo abbastanza lungo; in ogni caso, la lunghezza del periodo deve essere superiore alla quantità di numeri casuali richiesti dal problema che interessa.
Quando la lunghezza del periodo è uguale ad m, si dice che il generatore ha periodo pieno.