Post on 31-Jul-2021
transcript
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.