La generazioni �di �

numeri casuali�

Fisica dell’Informazione

Cifrari composti

Ottenuti dall’applicazione sequenziale dei metodi precedentemente visti. Non sempre sono i migliori. Il più popolare tra i cifrari composti a chiave simmetrica: il DES

Due problemi principali: Il problema della resistenza ad un attacco esaustivo. Il ruolo della chiave.

Come si trova una “buona chiave”? Il problema della password….

La necessità di generare numeri casuali….

La generazione di numeri casuali

1) Che cosa si intende per una sequenza di numeri casuali

2) Come può ottenersi una sequenza di numeri casuali

3) Data una sequenza come si fa a dire se essa è casuale

L’impiego di numeri casuali riveste attualmente una grande importanza in molte applicazioni di uso quotidiano:

- Esperimenti statistici –analisi di algoritmi- Simulazione di sistemi stocastici - Metodi Monte-Carlo - Algoritmi probabilistici - Crittografia - Protocolli di comunicazione sicuri - Gambling machines - Computer games

1) Che cosa si intende per una sequenza di numeri casuali

Diciamo che una sequenza di numeri è una SEQUENZA CASUALE se:

•  Ogni elemento ha la stessa probabilità di apparire nella sequenza (distribuzione uniforme)

•  Dalla conoscenza di uno o più elementi della sequenza è impossibile predire il valore degli elementi successivi

2) Come può ottenersi una sequenza di numeri casuali

Per definizione una sequenza di numeri casuali non può essere generata mediante un algoritmo (in senso stretto).

Resta la possibilità di affidarsi a sistemi fisici che generano valori misurabili di una qualche grandezza soggetta a fluttuazione statistica: il RUMORE

Johnson Noise

2) Come può ottenersi una sequenza di numeri casuali

Johnson Noise

Nichols A. Romero, Junior Physics Laboratory, Massachusetts Institute of Technology (1998) http://w3.physics.uiuc.edu/~nromero/archive/8.14.pdf

3) Data una sequenza come si fa a dire se essa è casuale

Storicamente sono stati assunti diversi approcci:

•  Criterio di Von Mises (principio dell'impossibilità di un sistema di gioco o assioma del disordine) negli anni ‘20 analogia con sistemi del gioco d’azzardo. Controllo empirico sui risultati: se si vince allora non è casuale!

•  Popper anni 30, è casuale se la lunghezza minima dell’algoritmo è pari alla lunghezza della sequenza.

La generazione di numeri casuali

1) Che cosa si intende per una sequenza di numeri casuali

2) Come può ottenersi una sequenza di numeri casuali

3) Data una sequenza come si fa a dire se essa è casuale

3) Data una sequenza come si fa a dire se essa è casuale Sistemi dinamici caotici e sistemi rumorosi

Casuale viene talvolta interpretato come irregolare. Ad esempio, la tensione ai capi di un resistore all’equilibrio termico Costituisce una segnale altamente irregolare (e casuale).

Facciamo un esperimento:

Sistema fisico x(t) osservabile

Esiste una legge che descrive l’evoluzione della x(t), noto tutto quello che c’è da sapere sul sistema fisico?

Se c’è diciamo che il nostro sistema fisico è un sistema dinamico

Anni addietro qualcuno si è un po’ fatto prendere la mano…

Il trionfo del determinismo

Dobbiamo dunque considerare lo stato presente dell’universo come effetto del suo stato anteriore e come causa del suo stato futuro. Un’intelligenza che, per un dato istante, conoscesse tutte le forze di cui è animata la natura e la situazione rispettiva degli esseri che la compongono, se perdipiù fosse abbastanza profonda per sottomettere questi dati all’analisi, abbraccerebbe nella stessa formula i movimenti dei più grandi corpi dell’universo e dell’atomo più leggero: nulla sarebbe incerto per essa e l’avvenire, come il passato, sarebbe presente ai suoi occhi.

(Pierre-Simon de Laplace, 1814)

Cioè il futuro è COMPLETAMENTE determinato dalla conoscenza del passato!!!

TUTTO BENE… se non fosse che:

Occorre conoscere le condizioni iniziali del sistema (posizione e velocità ad un dato istante).

Questo in genere è difficile ed uno conosce le condizioni iniziali solo con una certa approssimazione, ovvero con una piccola incertezza.

Che succede se sbaglio di poco la misura delle condizioni iniziali?

Per i sistemi che ho visto prima (palle di cannone, pendoli semplici e razzi)… non molto

Che succede se sbaglio di poco la misura delle condizioni iniziali?

Per altri sistemi invece, un piccolo errore sulla misura delle condizioni iniziali può portare a grandi, enormi differenze sul risultato finale. E’ l’effetto farfalla!!!

Does the Flap of a Butterfly’s Wings in Brazil set off a Tornado in Texas?

Il pendolo forzato:

Lo stesso pendolo, se messo in oscillazione con due condizioni iniziali lievemente differenti, dopo un certo tempo assume posizioni che diventano RAPIDAMENTE molto diverse !!!

Pendolo smorzato e forzato

Oltre l’approssimazione delle Piccole oscillazioni

Pendolo smorzato e forzato

Oltre l’approssimazione delle Piccole oscillazioni

Pendolo smorzato e forzato

Oltre l’approssimazione delle Piccole oscillazioni

Pendolo smorzato e forzato

Oltre l’approssimazione delle Piccole oscillazioni

  Fattori rilevanti in relazione alla predicibilità di un sistema dinamico:

•  Primo esponente di Lyapunov •  Dimensione dell’attrattore •  Grandezza dell’errore nella

determinazione dello stato iniziale

Sistemi dinamici

Esponenti di Lyapunov

0

0 ),(ln1lim

xtXx

tt Δ

Δ=

∞→λ

0>λ

Esponenti di Lyapunov

Dimensione dell’attrattore

Esempio: Sistema di Lorenz

bzxydtdz

yrxxzdtdy

yxdtdx

−=

−+−=

+−= σσ

Sistema di Lorenz

28;10;38

=== rb σPer opportuna scelta dei parametri

L’attrattore di Lorentz in 3D:

L’attrattore di Roessler

3) Data una sequenza come si fa a dire se essa è casuale

Data l’alta irregolarità delle traiettorie dei sistemi dinamici caotici data una serie temporale non è banale decidere se questa è stata prodotta da un sistema dinamico o è il risultato di un rumore.

Esistono studi in letteratura…

La generazione di sequenze pseudo-casuali

Cosa ci aspettiamo da un buon generatore di numeri pseudo casuali?

Esempio: simuliamo il lancio di una coppia di dadi

Assumiamo che i dadi siano NON truccati: Ogni intero compreso tra 1 e 6 ha probabilità 1/6 di essere osservato in ciascun lancio indipendentemente dai risultati degli altri lanci.

Lancio di un dato 6 volte: - 333333 prima sequenza - 146232 seconda sequenza

La generazione di sequenze pseudo-casuali

Cosa ci aspettiamo da un buon simulatore di dadi ?

- ciascun intero compreso tra 1 e 6 dovrebbe apparire con una frequenza ‘vicina’ al valore 1/6 - ciascuna coppia dovrebbe apparire con una frequenza ‘vicina’ al valore 1/36 - ciascuna tripla di numeri dovrebbe apparire con una frequenza ‘vicina’ al valore 1/216 - ............

Inoltre: che le generazioni consecutive di numeri non siano correlate.

La generazione di sequenze pseudo-casuali

Generatori basati sull’aritmetica modulare.

Consideriamo una divisione. Chiamiamo q il quoziente, cioè il risultato della divisione fra il dividendo x e il divisore m, mentre R è l'eventuale resto.

Scriviamo x(mod m)= R,

La generazione di sequenze pseudo-casuali Generatori basati sull’aritmetica modulare.

Per x(mod m) valgono le seguenti proprietà:

･è sempre R < m･ ･se x < m, allora x (mod m)= x ･se x = m, allora x(mod x)= 0･ ･se x supera di 1 m, allora x(mod (m)= 1 ･x(mod 1)= 0･ ･0(mod m)= 0

Una classe di metodi di generazione di numeri pseudo-casuali impiega i cosiddetti metodi congruenziali.

si dice che a è congruente con b se a mod m = b mod m

tre tipi principali di metodi congruenziali:

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

Dove ri, a, b, m sono interi non negativi e ri è compreso tra 0 ed m.�

ro (valore iniziale della sequenza) è detto seme.

Questi metodi danno origine a sequenze pseudo casuali che tendono a ripetersi dopo un certo numero di elementi. Per questo vengono dette sequenze periodiche.

Il periodo della sequenza ha valore minore o uguale a m. Per ottenere il periodo massimo si debbono rispettare alcune condizioni:

･b ed m devono essere primi tra loro; ･sia p un numero primo, divisore di m. Allora a-1 deve essere multiplo di p;

Per chi vuole approfondire…. :

- L'Ecuyer, P. 1998. Random number generation. In Handbook of Simulation, ed. J. Banks, J Wiley. chapter 4.

- Knuth, D. E. 1998. The Art of Computer Programming, Vol 2: Seminumerical Algorithms.Third ed. - Addison-Wesley.