Dunque, scrivo quest'ultimo post sui rng giusto per fare chiarezza, visto
che forse ho incasinato la mente a qualcuno e non sono riuscito a far capire
l'unica cosa che mi interessava.
Allora analizziamo questo codice :
/* Un semplice PseudoRandomNumberGenerator */
/* usando un algoritmo LCGs */
/* hjan - theblackangel@xxxxxxxx */
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#define max 1000000 /*numeri generati */
#define seed 1
FILE *output; /*File uscita numeri*/
main ()
{
unsigned int i, sem, newx, newy;
sem=seed; /*il seed*/
output = fopen("random_lin.txt", "w");
/* generating random numbers */
for (i=0; i<=max; i++)
{
/* Generatore di 16 numeri random nel campo 0-15 */
newx = (5*sem+3) % 16;
fprintf (output, "%i\n", newx);
sem=newx; /* cambio seed */
}
fclose (output);
}
Solito prng basato su LCG, stavolta però gli ho fatto estrarre 1 milione di
numeri.
Allego un grafico della distribuzine di queste estrazioni, precisamente
prng_lin1M.png ottenuto con gnuplot dal file random_lin.txt.
Come si può vedere il prng converge all'equiprobabilità delle estrazioni.
Analizziamo ora il codice qui sotto :
/* Un semplice PseudoRandomNumberGenerator */
/* usando un algoritmo non lineare */
/* hjan - theblackangel@xxxxxxxx */
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#define max 1000000 /*numeri generati */
FILE *output; /*File uscita numeri*/
unsigned int seeder(){
unsigned int randnum,key;
int fd = open("/dev/urandom", O_RDONLY);
if (fd != -1) {
read(fd,&randnum,4);
key = randnum;
}
close(fd);
return key;
}
main ()
{
unsigned int i, seed, newx, newy;
seed=seeder(); /*il seed*/
output = fopen("random.txt", "w");
/* generating random numbers */
for (i=0; i<=max; i++)
{
/* Generatore di 16 numeri random nel campo 0-15 */
newx = (5*seed+3) % 16;
fprintf (output, "%i\n", newx);
seed=seeder(); /* cambio seed */
// printf("seed %u \n",seed);
}
fclose (output);
}
Cosa cambia? Il seed qui viene variato ogni volta e pescato da /dev/urandom.
Il grafico allegato, prng1M, si mostra uguale al grafico precedente, facendo
supporre che i due generatori siano "identici" e quindi non c'è differenza
nell'usare l'uno o l'altro.
Ebbene non è così.
Analizziamo la sequenza dei primi 48 numeri estratti dal primo codice :
8 11 10 5 12 15 14 9 0 3 2 13 4 7 6 1 8 11 10 5 12 15 14 9 0 3 2 13 4 7 6
1 8 11 10 5 12 15 14 9 0 3 2 13 4 7 6 1
Questa sequenza mostra si l'equiprobabilità dell'estrazione ma anche la
ripetitività della sequenza quindi la sua predicibilità data la conoscenza
dello stato precedente.
Analizziamo la sequenza dei primi 48 numeri estratti dal secondo codice :
6 11 5 8 3 10 13 13 0 10 15 5 10 4 9 12 7 2 9 2 2 1 2 6 5 0 0 0 4 13 9 7 2 3
11 3 9 3 15 1 11 1 1 10 10 4 8 2
Questa sequenza non mostra una correlazione, o sequenze ripetute, almeno non
banali e la convergenza è dimostrata graficamente per un numero di prove
alto.
Questo fattore, che si potrebbe dimostrare anche matematicamente analizzando
l'entropia delle due sequenze, è molto importtante in qualsiasi sistema di
crittografia o estrazione casuale.
Infatti la non predicibilità della chiave generata successimante è
fondamentale.
A questo proposito provate a chiedere ad un famoso casinò online come la
pensa su questo fatto...soprattutto quando ha dovuto sborsare 1M$ perché un
signore era riuscito a capire che il loro rng per le estrazioni basava il
seed sull'ora di sistema e poi era una banale formuletta.
Il tipo era così riuscito a capire come si ripeteva la sequenza e a puntare
sicuro perché in grado di predirla :D
Ed è questo il punto che volevo chiarire nelle mail precedenti anche se mi
rondo conto di non averlo fatto ;)
Scusate il lungo post
g
--
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.300 / Virus Database: 265.8.5 - Release Date: 03/02/2005
--
Email.it, the professional e-mail, gratis per te: http://www.email.it/f
Sponsor:
Telefonare all'estero risparmiando fino all'80%? Con Email.it Phone Card puoi,
clicca e scopri tutti i vantaggi
Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid&83&d=6-2Attachment:
prng1M.png
Description: PNG image
Attachment:
prng_lin1M.png
Description: PNG image
No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.300 / Virus Database: 265.8.5 - Release Date: 03/02/2005 ========---------- Archivio delle e-mail postate in lista //www.freelists.org/archives/lugge/ Prima di scrivere in m-list per favore leggi il regolamento http://www.lugge.net/index.php?mod=cosa_facciamo/gruppo_di_discussione Modifica dell'account sulla lista LUGGe http://www.lugge.net/index.php?mod=cosa_facciamo/gruppo_di_discussione#list
