Per fare cicli lunghissimi di generazione di numeri pseudocasuali
Versione del 20140713 : http://www.elegio.it/doc/tn/lunghicicli.html
Dove ho messo altri documenti su questo tema: http://www.elegio.it/doc/tn/Ovviamente NON suggerisco di fare TUTTO DA SOLO ossia NON usare programmi GARANTITISSIMI DA MOLTI MATEMATICI disponibili in rete più o meno gratuitamente... Ma quando uno, mettiamo il Santo Papa o la Angelica Merkel, affida ad un suo segretario un testo che vuole che resti segreto... che garanzia ha che il suo segretario/segretaria di fiducia non comunichi con molto lucro ai giornalisti o ai servizi segreti degli Stati Amici ( dagli amici mi guardi Dio ) quel messaggio prima di criptarlo ?
Dunque consiglio alla Merkel ( complimenti per la vittoria al mondiale di calcio 2014... io tifavo sia per la Germania che per l'Argentina e sono stato comunque felice ) e consiglio al Papa argentino ed all'eventuale suo successore... ( mah... ci sarà ? ) di provvedere PERSONALMENTE a precriptare il messaggio usando un algoritmo semplice che oltretutto sia a lui perfettamente comprensibile come questo ( insegnare più matematica ai seminaristi ed ai politici ), e solo dopo avere preso questa misura di sicurezza affidare il messaggio segreto ai suoi segretari e camerieri magari persino cardinali, di sua assoluta fiducia...Che garanzia ha, per esempio, il Papa di essere in mani più sicure di quell' Iscariota amministratore economista, bancario e contabile del Nazareno ?
1) Scegliere e fare un calcolo dimostrativo// // Questo e' il generatore dei numeri casuali. // function generatore(kbase,kaso){ var k,kk=kaso.length,nn=0; for(k=0;kk>k;k++){ do{kaso[k][0]=(kaso[k][0]*kaso[k][1])%kaso[k][2]; }while(kaso[k][0]%2==1); nn+=(kaso[k][0]/2)%kbase;} return nn%kbase; } //Consiglio vivamente di usare per ogni kaso[k][2], tranne il primo kaso[0][2], un SAFE PRIME spiegato, per esempio, qui: http://it.wikipedia.org/wiki/Numero_primo_sicuro che si ottiene da un primo di Sophie Germain, come spiegato qui : http://en.wikipedia.org/wiki/Sophie_Germain_prime
Per capire l'algoritmo bisogna avere presente il concetto di RADICE PRIMITIVA che viene spiegato qui: http://en.wikipedia.org/wiki/Primitive_root_modulo_n.
Breve spiegazione dell'algoritmo
Il vettore kaso può essere lungo quanto si vuole ed ogni suo elemento deve essere costituito da una terna di numeri interi: il valore del numero pseudocasuale, che cambia di volta in volta, riguardante il numero primo considerato, la radice primitiva usata per il numero primo considerato e il k_esimo numero primo considerato.
Una radice primitiva a è un intero che consente di generare tutti i numeri compresi tra 1 e p−1 facendo ovviamente calcoli in algebra modulare usando come modulo il primo p. Dunque an modulo p, scegliendo un valore opportuno di n, produce un qualsiasi intero tra 1 e p−1. Dato che n può essere un intero gigantesco, l'elevazione a potenza si fa con successive moltiplicazioni e calcolo del resto della divisione per p. Dunque in Javascript si deve scrivere (x*a)%p dove x è l'intero ottenuto al passo precedente e l'operatore % rappresenta in Javascript il calcolo del modulo ( ossia il resto della divisione di x*a diviso p ). Usando wxMaxima ( http://www.elegio.it/max/ ) si otterrebbe lo stesso risultato scrivendo mod(x*a,p).
Solitamente si usano come numeri pseudocasuali tutti i numeri ottenuti col metodo notissimo usato qui ma l'originalità di questo algoritmo consiste nel fatto che vengono scartati i numeri dispari ed utilizzati SOLO I NUMERI PARI DIVISI PER 2 come si vede dalla istruzione do{kaso[k][0]=(kaso[k][0]*kaso[k][1])%kaso[k][2]; }while(kaso[k][0]%2==1).
Questo sperpero di numeri pseudocasuali ha il vantaggio di rendere praticamente imprevedibile il legame matematico tra un numero pseudocasuale e il suo successivo perché a priori è ignoto il numero di passi da fare per ottenere, dopo un numero pari, un altro numero pari.
Dopo che si è generato un numero pseudocasuale lo divido per due per cui il totale dei numeri utilizzati sarà (p−1)/2. Ma se p è un SAFE PRIME allora (p−1)/2 sarà un numero dispari e primo ossia un primo di Sophie Germain.
Per ottenere una uniforme probabilità di generazione di interi compresi tra 0 e kbase−1 bisogna che uno ed uno solo dei primi, diminuito di 1 e diviso per 2, sia esattamente divisibile per kbase mentre tutti gli altri interi, essendo primi di Sophie Germain e diversi l'uno dall'altro, saranno tra loro primi e lo saranno anche nei confronti dell'intero divisibile per kbase.
In generale la generazione equiprobabile dei numeri tra 0 e kbase−1 si ottiene se tutti i numeri (kaso[k][2]-1)/2 sono tra loro primi e uno di essi, di solito (kaso[0][2]-1)/2 è esattamente divisibile per kbase. Poi l'algoritmo somma tutti i numeri pseudocasuali ottenuti ad un dato passo e calcola il modulo di questa sommatoria rispetto a kbase. Vista la grande imprevedibilità ottenuta usando non un solo generatore di numeri pseudocasuali ma parecchi... la pseudocasualità dell'intero ottenuto in questo modo dovrebbe essere elevatissima...
L'avanzamento del calcolo e i risultati vengono visualizzati nei tre capitoli seguenti.
2a) A calcolo terminato visualizza la numerosità delle estrazioni
2b) A calcolo terminato visualizza i ritardi che si sono verificati.
2c) A calcolo terminato visualizza qualche numero estratto alla fine...
3) Spiegazione dei metodi applicati.
Si sceglie un numero primo grosso, sia nprimo , dunque un numero dispari, tale per cui nprimo-1 è esattamente divisibile per il totale dei numeri che si vuole tirare a sorte.
Dunque se si vuole simulare l'estrazione di un numero del lotto bisogna che nprimo-1 sia esattamente divisibile per 90 dato che al lotto può essere estratto un qualsiasi intero tra 1 e 90, mentre se si vuole simulare l'estrazione di un numero della roulette bisogna che nprimo-1 sia esattamente divisibile per 37 perché dalla roulette può uscire un qualsiasi intero tra 1 e 36 ma può uscire anche lo 0 ed in quel caso il banco non premia nessun giocatore ed incamera tutti i soldi puntati quella volta.Usando wxMaxima ( vedere http://www.elegio.it/max/ ) per sapere se un dato intero è effettivamente un numero primo, bisogna usare la funzione primep(nprimo) che deve dare come risultato true se veramente nprimo è un numero primo.
Fatta la scelta del numero primo ( per esempio prendendoli piccoli per simulare la roulette ed evidenziare i difetti di casualità ossia per esempio 26641 oppure 223 oppure 593 ) bisogna trovare una radice primitiva ossia un numero che, elevato ad una qualsiasi potenza tra 0 e nprimo-2 dà un numero sempre diverso tra 1 e nprimo-1.
Usando wxMaxima, per esempio, per trovare la più piccola radice primitiva posseduta da nprimo bisogna digitare zn_primroot(nprimo) e, per esempio, si scopre che la più piccola radice primitiva di 26641 è 7 mentre sia 223 che 593 hanno 3 come la loro più piccola radice primitiva. Notare che anche 149 ha 3 come radice primitiva pur avendo anche 2 che non è radice primitiva di 223 e 593. infatti power_mod(2,37,223) dà 1 come ovviamente anche power_mod(2,0,223) ed anche power_mod(2,111,223) ossia lo stesso numero 1 compare più di una volta elevando la base, non radice primitiva, ad una potenza tra 0 e nprimo-2.Per avere una generazione di interi che sembri veramente casuale il più possibile non bisogna però scegliere come base una radice primitiva piccola perché altrimenti si ottiene una sequenza di interi facilmente prevedibile. Se per esempio scegliamo come base, il numero 3, allora 31 vale 3, 32 vale 9, 33 vale 27, 34 vale 81 e solo 35 vale 243 che è maggiore di 149 e 223 ma non di 593 per cui modulo 593 vale ancora 243 mentre, scrivendo usando Javascript, 243%149 vale 94 e 243%223 vale 20 ossia maschera il fatto che è stato ottenuto elevando 3 alla potenza 5.
Riporto qui dei numeri primi forti e tanto grandi da essere al limite della possibilità di Javascript di trattare senza approssimazione interi giganti. Tutti questi hanno radice primitiva 2 e dunque basta raddoppiare il numero e calcolare il modulo non facendo una divisione ma semplicemente verificando che il numero ottenuto col raddoppio non supera il valore del primo ossia del modulo e altrimenti sottraggo il modulo:4000000000000163, 4000000000001219, 4000000000017587, 4000000000019147, 4000000000022003, 4000000000024907, 4000000000034483, 4000000000036499, 4000000000037243, 4000000000040027, 4000000000043963, 4000000000047419, 4000000000050779, 4000000000056059, 4000000000059587, 4000000000062659, 4000000000076579, 4000000000076723, 4000000000076867, 4000000000085483, 4000000000085603,Per simulare una roulette usando 2 come radice primitiva vanno bene [ 74000000003627, 74000000005699, 74000000006587, 74000000010509, 74000000014949, 74000000017613, 74000000018723, 74000000024051, 74000000027677, 74000000033227, 74000000038037, 74000000039813, 74000000041811, 74000000042477, 74000000043661 ] etc... ossia primi che diminuiti di 1 sono divisibili esattamente da 37.
Il fatto che Javascript usi numeri in duplice precisione ossia interi non enormi mi ha suggerito un algoritmo che consente di ottenere un periodo anche enormemente lungo ossia non solo circa un milione di miliardi di passi ma.. miliardi di miliardi di miliardi... quanti se ne vuole.
Il problema è però dimostrare che tutti i numeri estratti con questo algoritmo hanno esattamente la stessa probabilità di venire estratti. Ovviamente sarebbe possibile una dimostrazione rigorosa, matematica ma qui ho preferito verificare con un esempio impegnativo la fondatezza di questa affermazione.Perché l'algoritmo funzioni bisogna scegliere un certo numero di primi diversi l'uno dall'altro e tali per cui ogni primo diminuito di uno e diviso per due dia un intero che risulti primo rispetto agli analoghi interi dedotti con questa regola dagli altri numeri primi.Ma attenzione ! Per garantire che tutti i numeri estratti siano esattamente equiprobabili bisogna fare in modo che uno ( ed uno solo ) dei primi diminuito di 1 e diviso per 2 sia anche divisibile esattamente per il totale dei numeri che si vogliono ottenere ( 37 nel caso che si voglia simulare una roulette ).Qui, nell'esempio ho scelto 26641 con radice primitiva 7 perché 26640/2 = 13320 che è divisibile per vari interi ossia 37 dato che voglio simulare l'estrazione a sorte di una roulette che ha 36 numeri che premiano gli scommettitori e lo 0 che premia solo il banco. Ma con questo numero posso simulare il gioco della testa/croce o il lancio di un dado a sei facce etc...Per potere fare la verifica della uguale probabilità ho scelto, come altri numeri primi 227 che ha anche 226/2=113 primo ed ha radice primitiva 2, 263 che ha anche 262/2=131 primo ed ha radice primitiva 5, e 347 che ha anche con 346/2=173 primo e radice primitiva 2. In questo modo 13320,113,131 e 173 sono sicuramente tra loro primi e questo garantisce che l'algoritmo si comporti come si desidera. Ma naturalmente avrei potuto scegliere non numeri primi così piccoli ma numeri primi giganteschi per cui il ciclo globale sarebbe durato miliardi di miliardi di miliardi di passi ma questo non avrebbe permesso la verifica diretta della uniforme probabilità di estrazione dei numeri di questa roulette...Ho aggiunto anche la possibilità di usare numeri primi ciclopici ma ho dato la possibilità di interrompere il calcolo per farsi una idea della frequenza e dei ritardi dei numeri estratti fino a quel momento...
4) Il sorgente della funzione più importante usata.// // Questa funzione serve a dimostrare che facendo // TUTTE le possibili estrazioni a sorte, tutti i numeri // della roulette vengono estratti uno stesso numero // di volte. // function frequenze(){ var j,k,jbasta,nn,mm; if(jfatti==0){ quanti=1; for(j=0;kprimo.length>j;j++){ kprimo[j][0]=1; quanti=quanti*((kprimo[j][2]-1)/2); // Fissa un limite ragionevole anche se enorme... if(quanti>4e10) quanti=4e10; } for(j=0;kbase>j;j++){ ripetuti[j]=0; ultimifatti[j]=0;} listaobj[0].innerHTML="Dovra' generare "+quanti+" numeri della roulette !"; } jbasta=Math.min(jfatti+incremento,quanti); for(j=jfatti+1;jbasta>=j;j++){ nn=generatore(kbase,kprimo); vedere[j%visibili]=nn; mm=j-ultimifatti[nn]; if(mm>=ritardi.length)for(k=ritardi.length;mm>=k;k++)ritardi[k]=[0,0]; ritardi[mm]=[ritardi[mm][0]+1,[" [",nn,j,"] "]]; ultimifatti[nn]=j; if(mm==0)allarme(j) ripetuti[nn]++; } if(jbasta==quanti || mifermo ){ vedotutto(ripetuti,ultimifatti,ritardi,vedere); jfatti=0; return true; } jfatti=jbasta; listaobj[0].innerHTML="Fatti per ora: "+jfatti+" di "+quanti; setTimeout("frequenze()",100); } //Ho trascritto qui l'algoritmo usato in questo documento per renderlo evidente il più possibile...
5) Riferimenti internettistici
http://www.elegio.it/doc/tn/ dove tratto vari aspetti della crittografia.
http://www.elegio.it/doc/tn/metodo-lineare-congruente.html dove non tratto solo il metodo moltiplicativo congruente che obbliga ad usare numeri primi e conoscere loro radici primitive.
http://en.wikipedia.org/wiki/Double_precision_floating-point_format Between 252=4˙503˙599˙627˙370˙496 and 253=9˙007˙199˙254˙740˙992 the representable numbers are exactly the integers.... dunque in Javascript attualmente è opportuno non trattare interi più grandi di 6 milioni di miliardi... Io, per ragioni storiche ho spesso usato questo numero numerone:7+1.024e12 ossia 1024000000000007 che ha come radice primitiva 5 ed è facilmente scrivibile pur essendo gigantesco. Infatti: zn_primroot(1024*10^12+7) ed ha la peculiarità che risulta true anche mezzonumerone:(numerone-1)/2;primep(mezzonumerone) ossia 512000000000003 con radice primitiva 2 ed anche mezzobisnumerone:(mezzonumerone-1)/2;primep(mezzobisnumerone) ossia 256000000000001 con radice primitiva 7.
http://planetmath.org/SafePrime ovvero PRIMI SICURI di cui ne parla anche in http://it.wikipedia.org/wiki/Numero_primo_sicuro
http://it.wikipedia.org/wiki/Numeri_pseudocasuali dove si ricorda il grande http://it.wikipedia.org/wiki/Donald_Knuth.
6) Variante del generatore// // Questo e' il generatore dei numeri casuali che // puo' usare primi qualsiasi purche' diversi tra loro. // function generatoreveloce(kbase,kaso){ var k,kk=kaso.length,nn=0; for(k=0;kk>k;k++){ do{kaso[k][0]=(kaso[k][0]*kaso[k][1])%kaso[k][2]; }while(kaso[k][0]>kaso[k][3]); nn+=kaso[k][0]%kbase;} return nn%kbase; } //Come si vede, le operazioni da fare ad ogni passo sono un po' meno di quelle dell'altra versione e se il terzo intero ossia kaso[k][3], pur essendo obbligatoriamente più piccolo del primo a lui corrispondente ossia kaso[k][2], è quasi uguale a lui, il numero di numeri scartati diventa piccolo con il solo svantaggio che risultano meno casuali ma se già lo sono, questo inconveniente non è grave...
Sottolineo che, per garantire il corretto funzionamento dell'algoritmo è OBBLIGATORIO che kaso[k][0] sia un numero positivo minore di kaso[k][2], inoltre kaso[k][1] deve essere una radice primitiva del numero primo kaso[k][2] ed ovviamente tutti i numeri primi usati debbono essere diversi l'uno dall'altro... ed infine kaso[k][3] deve essere minore di kaso[k][2] ma non c'è il vincolo che sia un numero primo ma tutti i kaso[k][3] DEBBONO essere PRIMI TRA LORO ossia il massimo comune divisore ( in inglese : gcd ) tra ciascuna coppia di loro deve essere sempre 1.
Infine per garantire che tutti i numeri estratti abbiano una esattamente identica probabilità di estrazione bisogna scegliere uno solo dei kaso[k][3] in modo che sia divisibile esattamente per kbase ma rispettare comunque il vincolo che tutti i kaso[k][3] non abbiano tra loro alcun divisore comune.Qui ci sono esempi che evidenziano questo rischio ossia esempi in cui si vede che NON SI HA una probabilità ESATTAMENTE uguale se kbase possiede un divisore comune con due numeri kaso[k][3]. È il caso di 6 o di 90 che hanno un fattore comune sia con 12987 ( il 3 ) che con 500 ( il 2 e con 90 anche il 5 ). Tuttavia, data la lunghezza del ciclo globale, la probabilità NON è ESATTAMENTE uguale ma è QUASI UGUALE.... Provare per constatarlo direttamente ! I risultati di queste sperimentazioni vengono scritti nei capitoli immediatamente successivi a questo...
7a) A calcolo terminato visualizza la numerosità delle estrazioni
7b) A calcolo terminato visualizza i ritardi che si sono verificati.
7c) A calcolo terminato visualizza qualche numero estratto alla fine...
8) Qualche grosso primo utile
9) Conclusioni