Newsgroup: it.comp.sicurezza.crittografia
Titolo: Generazione numeri casuali e GePaHE

Negli ultimi giorni mi sono dovuto confrontare, per la prima volta a
livello scientifico/informatico, con i metodi Monte Carlo.
Sintetizzando per chi non sapesse di cosa sto parlando si tratta di
metodi simulativi probabilistici che si basano sulla disponibilit� di
un'enorme quantit� di numeri casuali.
Risultano essere sistemi molto potenti per simulare e prevedere
l'andamento di sistemi a geometria complessa, le cui equazioni
deterministiche non sono risolvibili.
L'esempio che mi viene in mente adesso � il calcolo della dose
radioattiva sommistrata ai vari organi di un paziente sottoposto a
radioterapia.
Ho visto che in Fortran (il linguaggio principe per quel che riguarda
l'analisi numerica) � presente dalla specifica del '95 una funzione
intrinseca per generare numeri pseudo-casuali: RANDOM_NUMBER
(
http://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fNUMBER.html
).
Il problema, come al solito, � che bisogna fornire un seed "casuale" per
inizializzare il generatore.
In questo caso, a seconda del compilatore, il seed non deve essere solo
uno, ma pi� di uno.
Mi sono allora dovuto porre il problema di trovare numeri oltre
all'orario del sistema da usare. Personalmente la soluzione proposta nel
manuale di gfortran
(
http://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fSEED.html
) non mi
piace per niente: prendere 8 numeri consecutivi o con
differenza fra loro predeterminata mi sembra tutto tranne che una buona
soluzione.
Ho quindi allora pensato di usare l'impredicibilit� del resto della
divisione fra numeri molti elevati. Ho quindi dato in pasto al mio
generatore di numeri casuali fatto in casa l'orario del sistema per poi
generare gli altri seed che mi servivano. Avendo a disposizione il
vettore di seed ho inizializzato la funzione random intrinseca del
compilatore.
Ho qualche domanda in proposito:
1) � corretta la procedura che ho seguito?
2) si poteva fare di meglio? se s�, come?
Parlando di numeri casuali mi � tornato in mente il programma GePaHE
(
http://www.webalice.it/cristiano.pi/GePaHE/
) di Cristiano.
Al momento si tratta di un progetto abbandonato oppure no?
Se non chiedo troppo, mi potreste spiegare effettivamente come funziona?
In particolare la frase
"Questo risultato viene raggiunto sfruttando adeguatamente i
temporizzatori ad alta risoluzione presenti nei comuni personal
computer con sistemi operativi Windows e CPU classe Pentium (ad es.
Athlon), non sono quindi necessari componenti elettronici aggiuntivi."
non mi � chiara.
Cosa sono effettivamente i temporizzatori? Perch� sono veramente
casuali?
Sarebbe possibile ottenere un'implementazione multipiattaforma, in
particolare anche per i sistemi *nix oppure il gioco si basa in parte
anche su funzioni intrinseche del sistema operativo Windows?
E per finire: a quale rate costante si potrebbero generare numeri
casuali?
Ho notato che generalmente l'approccio prevalenete di chi
studia/progetta codici Monte Carlo � quello di lasciare al compilatore
l'onere di dare una buona funzione generatrice di numeri casuali,
concentrandosi sulla fisica del sistema.
Questo approccio si � dimostrato nella pratica valido, anche se
personalmente non riesco ad accettare completamente che una simulazione
realistica possa fare affidamento su sequenze di numeri non veramente
casuali.
Per questo motivo mi piacerebbe approfondire la questione, magari
provando a scrivere un codice che utilizza come seed dei veri numeri
casuali e che ad intervelli veramente casuali reinizializza il
generatore PRNG.
L'ideale sarebbe avere un generatore puramente casuale, ma temo che allo
stato attuale non sia praticamente possibile, vista anche la lentezza
con cui si riempe /dev/random su sistemi GNU/Linux (a meno ovviamente
del discorso su GePaHE).
-- 
Lurkos

 del discorso su GePaHE).
Rimango convinto che per lo scopo di una simulazione di Montecarlo sia 
una paranoia inutile. Non stai centrando il punto. Studia le proprieta' 
del generatore, il modo in cui lo usi perche' ci sono alcuni pitfall 
quando generi grandezze fisiche legate in modo non linerare e come 
esegui il sampling.
Se poi proprio vuoi puoi cercare su google qualche sito che di permette 
di selezionare un set di numeri generati da un sistema fisico 
(rumore,decadimento radioattivo). Ma , spero di non offenderti, stai 
perdendo tempo sull'aspettomeno meno importante di una simulazione di 
montecarlo. L'argomento e' OT qui ma ti stupirai scoprendo che in molti 
casi (ma non sempre) una simulazione di montecarlo di un sistema fisico 
puo' essere "migliore" (ossia piu' accurata e/o piu' efficiente) usando 
numeri NON casuali (quasi-random sequence) senza nessun seed. Un esempio 
e' il calcolo di integrali multipli. Mai sentito parlare delle sequenze 
di Sobol?
Ciao
Max

 delle sequenze di Sobol?
Prima di tutto ti ringrazio per la risposta. Mi hai dato modo di
riflettere su diversi punti.
Mi sono documentato anche sulle sequenze di Sobol e ho capito cosa
intendi. In pratica nel calcolo di integrali conviene "sparare a caso",
ma in maniera ordinata, in modo da riempire i buchi in maniera
uniforme.
Quasi quasi provo ad implementare il solito calcolo di pigreco con una
sequenza di sobol e una "casuale" per vedere con quale arrivo prima ad
una data precisione.
P.S.: spero di non essere linciato per l'OT... :-)
-- 
Lurkos

Lurkos wrote:
[...]
Allora, come ti e` stato gia` risposto, non credo che avere
una assoluta impredicibilita` sia un requisito per questo
genere di simulazioni, anzi, forse e` uno svantaggio, dato
che non saresti in grado di riprodurre i risultati.
Un suggerimento sarebbe:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
Da cui:
Caution: Mersenne Twister is basically for Monte-Carlo
simulations - it is not cryptographically secure "as is".
Please read FAQ.
bye,
-- 
piergiorgio

 non veramente casuali.
Come ti dicevo, la casualit� dei numeri non � un requisito per una 
simulazione di Montecarlo. E` invece richiesto un generatore avente un 
periodo molto grande e possibilmente molto veloce e che, ovviamente, generi 
sequenze con ottime propriet� statistiche.
Ciao
Cristiano redivivo (la Telecom, in appena 11 mesi, mi ha portato la linea 
telefonica dentro casa e dopo appena altri 15 giorni mi ha anche attivato 
l'ADSL!)

 dipende dal contesto
E` gi� difficile definire il concetto di casualit�, figuriamoci il concetto 
di "casualit� sufficiente in base al contesto"! :-)
Cristiano 

 cosa serva la simulazione di Montecarlo.
Ma questo � evidente per il semplice fatto che Lurkos stia chiedendo 
chiarimenti e che l'abbia scritto proprio all'inizio del suo post: "Negli 
ultimi giorni mi sono dovuto confrontare, per la prima volta a livello 
scientifico/informatico, con i metodi Monte Carlo.", non serve che tu lo 
sottolinei.
Tra l'altro, in questo thread, Lurkos � l'unico che ha scritto "Monte Carlo" 
correttamente! :-)
Cristiano 

 Si potrebbe dire che il concetto di casualit� dipende dal contesto.
Dipende dal contesto quale livello di confidenza per accettare l'ipotesi 
di casualita' sia opportuno' E' parte del "protocollo" di gestione del 
test statistico. Non puoi dire "e' casuale!". Non ha senso. In 
statistica i test (non solo di casualita') "dipendono" dal livello di 
confidenza scelto. la statistica e' "scienza esatta" non perche' posso 
essere "certo" di qualcosa, ma perche' posso stimare la probabilita' di 
accettare l'ipotesi errata (o rigettare l'ipotesi giusta).

 senso.
Continui a parlare di test statistici, ma qui si stava parlando di 
casualit�.
Secondo me hai le idee piuttosto confuse, ma quel che � peggio � che non 
sembri aperto al dialogo costruttivo.
PLONK
Cristiano 

 sembri aperto al dialogo costruttivo.
Si parlava della non necessita' di una sequenza casuale nel metodo di 
Monte-Carlo. Poi del fatto che e' comunque impossibile dimostrare con 
certezza l'ipotesi di casualita'. Poi sei intervenuto (per spararti una 
posa e fare la figura di esperto ) dicendo che era possibile con 
"certezza" stabilirlo. Questo e' un test statistico.
Non ho interesse a discutere in modo costruttivo con te  solo a non 
propagare la tua ignoranza (ma e' un interesse relativo).
Quindi ora o posti un algoritmo che data una sequenza di numeri e' in 
grado di certificare con "certezza" la sua casualita' o ammetti di aver 
fatto una affermazione erronea..o taci che e' meglio
(nota come ti hanno fatto notare su sci.stat.math il tuo RaBiGeTe e' una 
scopiazzatura di parti di Knuth, NIST tests e Diehard. Ti hanno anche 
detto che e' roba vecchia..quindi non postarmi quella.)
Invece di simulare scaricati
An Introduction to Probability and Random Processes
by Gian-Carlo Rota, Kenneth Baclawski , 1979
Elementary Practical Statistics
by A. L. O'Toole - The MacMillan Company , 1964
Non-Uniform Random Variate Generation
by Luc Devroye - Springer , 1986
e studiali. Poi ti mando quelli seri.