INFORMATICA - QUANTUM COMPUTING
QRNG & PRNG

Novembre 2024

1. QRNG & PRNG

I Quantum Random Number Generator (QRNG) sono, come introdotto nella pagina sull'hypercomputing dei veri oracoli computazionali nel senso di Turing. Si tratta di sistemi hardware oggi piuttosto diffusi per diverse applicazioni di sicurezza/comunicazioni digitali e calcolo/ottimizzazione che permettono di generare dei flussi binari "realmente" casuali partendo da effetti quantistici quindi non deterministici di principio. Diversi QRNG sono disponibili in cloud e liberamente accessibili su Internet, altri sono semplici chiavette USB, altri ancora apparati di congrua complessità da inserire in una rete di calcolatori classici.

In questo lavoro "giocheremo" con diversi QRNG e con le sequenze da essi generate per poi mettere i risultati in relazione sia con le sequenze random determinate da classici Pseudo Random Number Generator (PRNG) che con sequenze numeriche particolari studiate per assomigliare a sequenze numeriche casuali. Non verranno presi in considerazioni i super-classici test del NIST sulla randomness (che rimanderemo ad un'altra pagina futura) ma diverse applicazioni del metodo Montecarlo alimentate da tali sequenze su problemi la cui soluzione è nota e deterministica.

2. Le sequenze considerate

Partiremo dalle sequenze generate nei seguenti modi:
a) QRNG Crypta Labs (chiavetta USB) - cryptalabs.com;
b) QRNG Random Power (hardware) - randompower.eu;
c) QRNG Think Quantum (hardware) - thinkquantum.com;
d) QRNG LFDR (cloud) - lfdr.de;
e) PRNG Python3.12.3 (software) su Linux;
f) Sequenza binaria "normale";
g) Sequenza binaria derivata dalle potenze positive di 2;
h) Sequenza binaria derivata dalle potenze megative di 2;
i) Sequenza binaria derivata dai decimali del numero di Eulero.

Tutte le attività di analisi dei dati e impiego del metodo Montecarlo sono state svolte in ambiente Linux. Vediamo ora brevemente come sono state estratte le sequenze.

Per i QRNG delle ditte Random Power e Think Quantum devo ringraziare i loro staff che mi hanno enormemente facilitato il lavoro consentendomi di avere a disposizione i flussi già pronti. In relazione al QNRG di Crypta Labs ho acquistato la relativa chiavetta USB ed è stato molto semplice interfacciarla con del codice python sotto Linux (basta fare attenzione alla connessione "serial" sulla porta "/dev/tty" giusta), inoltre la ditta provvede un software di riferimento per chi è alle prime armi. Per il flusso random da LFDR, esso è disponibile su Internet ed è bastato realizzare poco codice python per impiegare le QRNG REST API all'URL stabilito dal citato laboratorio e così ottenere la stringa JSON opportunamente formattata che codifica il flusso dei numeri random del loro QRNG. Riguardo il PRNG classico di python (3.12.3) sotto Linux basta richiamarlo con le dovute funzioni e naturalmente si può customizzare l'impiego con una grande varietà di parametri, documentazione in proposito è disponibile su Internet in abbondanza.

Argomento a parte per i punti (f),(g),(h) ed (i) che ho costruito realizzando delle specifiche procedure python.

La (f) è una stringa "normale" ossia una sequenza binaria del tipo:
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 ...
che come si può facilmente intuire è (in decimale):
0 1 2 3 4 5 6 7 8 9 10 11 12 ...
Per la sequenza (g) ho prima calcolato ad approssimazione 0 tutti gli interi potenze positive di 2 da 20 fino a 223000 per poi mettere in fila (senza separatori) tutti gli interi che ne risultano (vedere di seguito), comprimere il grande file risultante con ZIP ed ottenere così una complessa sequenza binaria. Qualora siate appassionati di numeri interi (come il sottoscritto) potete usufruire dei calcoli delle potenze di 2 scaricandoli dalla pagina specifica che ho loro dedicato nella parte di matematica di questo sito web Potenze negative di 2 e Potenze positive di 2:
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 ...
La sequenza (h) in maniera simile è stata ottenuta calcolando tutte le potenze negative di 2 da 2-1 a 2-4000), mettendo nuovamente in fila (senza separatori) tutti gli interi che ne risultano ma nella parte decimale (vedere di seguito), comprimendo il grande file risultante con TAR ed ottenendo così un'altra complessa sequenza binaria:
2^(-1) = 5 * 10^-1
2^(-2) = 25 * 10^-2
2^(-3) = 125 * 10^-3
2^(-4) = 625 * 10^-4
2^(-5) = 3125 * 10^-5
2^(-6) = 15625 * 10^-6
2^(-7) = 78125 * 10^-7
2^(-8) = 390625 * 10^-8
2^(-9) = 1953125 * 10^-9
2^(-10) = 9765625 * 10^-10
2^(-11) = 48828125 * 10^-11
2^(-12) = 244140625 * 10^-12
2^(-13) = 1220703125 * 10^-13
...
quindi 5 25 125 625 3125 15625 78125 390625 1953125 9765625 48828125 244140625 1220703125 ...
Infine, per (i) è stata considerata la parte decimale del numero di Eulero e per circa 2000000 di cifre (2.71828182845904523536028747135266249775...) e tramite una procedura python è stato convertito in una lunga sequenza binaria. Sempre nel caso siate interessati a questo numero particolare potete visitare la pagina ad esso dedicato in questo sito web: Numero di Eulero in decimale e binario.

Va sottolineato che l'estrazione delle sequenze dai RNG, siano essi quantistici o matematici, non è avvenuta alla stessa velocità. In particolare, i QRNG hardware su scheda (Random Power e Think Quantum) sono estremamente performanti. La chiavetta USB della Crypta Labs ovviamente ha una performance inferiore (anche considerato il costo limitato) e non riesce ad operare per molte ore di seguito. L'estrazione su Internet dal server LFDR del flusso random è invece limitato dai fornitori sia in quantità che in velocità, proprio a seguito dell'essere liberamente disponibile a tutti. Il PRNG, per sua natura, espone una performance dipendente dalla macchina che lo esegue e quindi può raggiungere velocità superiori a quelle dei QRNG.

La velocità di generazione del flusso di bit random sembra un parametro poco interessante ma così non è in quanto per particolari applicazioni, sia nell'ambito della sicurezza delle telecomunicazioni che nelle simulazioni Montecarlo, riveste un'importanza notevole.

3. La compressione delle sequenze

Come analizzato nella pagina della casualità di Komogorov, una sequenza S (finita) perfettamente random non è riducibile, ossia per qualsiasi compressore di dati COMP() si voglia considerare applicato ad S, non si può ottenere una sequenza compressa COMP(S) che abbia dimensione inferiore ad S. Il significato è che la quantità di informazioni contenute nella S è talmente alta che nessun algoritmo può farne una sintesi riducendone la lunghezza.

Dal punto di vista pratico prenderemo in considerazione diversi file con le sequenze descritte nel paragrafo precedente e andremo a comprimerle con svariati compressori software liberamente disponibili sotto Linux. Il risultato è quanto meno interessante:

COMPRPRNG(e)QRNG(d)QRNG(a)QRNG(c)QRNG(b)
-1048576010485760104857601048576010485760
P7ZIP1048653410486550104865501048655810486558
BZIP21053165810531868105330891053185510531796
TAR1048760310487613104876141048762010487618
LZ41048578710485787104857871048578710485787
LZOP1048629010486298104862971048630310486302
RAR1048592610485942104859401048595210485950
XZ1048634410486344104863441048634410486344
ZIP1048752610487542104875401048755210487550
Minimo1048578710485787104857871048578710485787
Delta+27+27+27+27+27
Percent+0.00026%+0.00026%+0.00026%+0.00026%+0.00026%

Si può sicuramente notare che per tutte le sequenze generate da PRNG e QRNG i relativi file compressi, nel migliore dei casi comunque aumentano di dimensione invece di diminuire. Questo non sorprende affatto, tenuto conto che i file sono incomprimibili e quindi tutti i compressori, anche quelli che sembrano operare meglio (che forniscono come risultati file di dimensioni minime rispetto agli altri) non possono fare altro che aggiungere al file originale i soliti dati di controllo per la gestione della compressione (in particolare i 27 byte in più che si vedono in tabella). Un'altra considerazione va fatta sul punto che è sempre LZ4 l'algoritmo di compressione che determina il minimo, sintomo che le sequenze hanno delle caratteristiche matematiche in comune.

Andiamo adesso a verificare cosa accade comprimendo le rimanenti sequenze che, ben lungi dall'essere random, sono assolutamente deterministiche, anche se dall'elevato grado di entropia (disordine e quindi informazione). La tabella che segue è esplicativa:

COMPEULERO2^(-n)2^nNORM
-25000824105751048576010485760
P7ZIP2501572408281104746282430091
BZIP22515512416216105124165302167
TAR2502732403989104581959123047
LZ425002724105941048578710485787
LZOP25007324107511048629610486292
RAR25016624087621047975416400
XZ2500802409044104787242435316
ZIP2502202404020104581879123091
Minimo25002724039891045818716400
Delta+19-6586-27573-10469360
Percent+0.0076-0.28%-0.27%-99.5%

La sequenza "normale" subisce una compressione massima del 99.5% ed anche questo sorprende poco dato che è il risultato di un contatore che avanza regolarmente in binario. Il fatto interessante è che tale sequenza comunque copre la maggioranza delle combinazioni binarie possibili per cui in questo senso è uniforme e sembra avere un elevato contenuto informativo ma di fatto è estremante semplice. I risultati sorprendenti sono quelli delle potenze di 2 positive e negative nonchè dell'espansione binaria dei decimali del numero di Eulero. Queste ultime, nonostante il loro determinismo incontestabile, sono difficilmente comprimibili ed addirittura per il numero di Eulero non lo è affatto e si comporta come le sequenze dei PRNG e QRNG aumentando in dimensione se compresse. Per tutti gli altri la compressione ha avuto effetto anche se con diminuzioni di dimensioni diverse e si noti che gli algoritmi di compressione che lavorano al meglio sono di volta in volta differenti, questo al contrario di quanto avvenuto per le sequenze provenienti da PRNG e QRNG. Queste sequenze hanno quindi caratteristiche matematiche sicuramente diverse tra loro.

In definitiva, i tentativi di compressione (come quello svolto ma anche ampliandolo a più compressori) non posssono costituire un test per la misura della randomness ma sicuramente costituiscono un test di esclusione della buona-randomness. In altre parole qualsiasi sequenza random finita di congrue dimensioni che sia riducibile mediante compressione non si può considerare ben-fatta.

Ulteriore e finale considerazione va sicuramente svolta sui PRNG che, come noto, sono frutto di un meccanismo comunque deterministico anche se caotico. La sequenza di un PRNG ben-fatto, dal punto di vista della compressione dati, si comporta esattamente come quella di un QRNG (casuale per definizione quantistica). Naturalmente questo avviene anche per alcune sequenze matematiche non caotiche ma tendenzialmente normali, come la parte decimale del numero di Eulero analizzata che, di fatto, non risulta comprimibile sebbene sia il risultato di un algoritmo noto e peraltro di piccole dimensioni (per i più curiosi si noti che l'algoritmo di generazione del numero di Eulero è esso stesso una forma di compressione di tale numero - vds la mia pagina: compressione di Komogorov).

3. Uso del Metodo Montecarlo

Le sequenze così come indicate da (a) ad (i) nel precedente paragrafo 2. sono state quindi impiegate per risolvere svariati problemi matematici con il metodo Montecarlo, basato appunto sull'impiego di valori casuali o pseudo-casuali. In particolare i problemi matematici considerati sono a risoluzione nota e saranno descritti di seguito. L'idea è confrontare l'impiego delle diverse sequenze per verificare che tipo di risultato la stessa procedura Montecarlo produce affrontando gli stessi problemi. Anche questo non può essere considerato un test di randomness nel senso canonico (statistico puro) del termine, ma rivela diversi aspetti come vedremo. Procediamo nel descrivere i problemi matematici considerati dividendoli in classi:

3.a Integrali definiti tra [0,1] 1-dim:

I seguenti integrali definiti unidimensionali nel "quadrato" [0,1]x[0,1] rappresentano l'area della singola funzione rispetto all'asse X. Si noti che tutte le funzioni nel citato quadrato sono positive e non assumono mai valori maggiori di 1. Il calcolo Montecarlo di tali integrali è alquanto semplice, basta generare delle coppie random (x,y) (con x e y nel quadrato [0,1]x[0,1]) e verificare se ognuno di tali punti geometrici sia nell'area coperta dalla funzione o meno (ossia f(x)>y). La frequenza relativa di tale evento (ossia la frequenza relativa che "sparando" a caso (x,y) questo cada nell'area coperta dalla funzione rispetto all'asse X) converge proprio al valore numerico dell'integrale definito. Questo ipotizzando che la sorgente sia sufficientemente random... In ogni caso, come si può vedere, la soluzione deterministica dei vari integrali è già nota per cui, operando con le sequenze studiate è possibile verificare quanto ci si avvicina, con il metodo Montecarlo, ai valori attesi.

(I) (II)
(III) (IV)
(V) (VI)
(VII)

Di seguito, alcuni grafici che fanno meglio capire come avviene l'integrazione definita mediante il metodo Montecarlo su alcune funzioni ivi riportate usando in un caso la sequenza PRNG e nell'altro una sequenza da un QRNG per disegnare i punti in blu che "centrano" l'area di integrazione:

(I) (VII)

3.b Integrale definito di superficie in [0,1]x[0,1] 2-dim:

Un altro problema matematico che consideriamo è il calcolo con metodo Montecarlo dell'area di una circonferenza, ossia dell'integrale di superficie nel quadrato [0,1]x[0,1] della funzione descrivente una circonferenza con centro (1/2,1/2). Il metodo di calcolo è identico ossia ottenere la frequenza relativa di centrare l'area del cerchio nello "sparare" a caso (x,y) nel quadrato [0,1]x[0,1]:

3.c Integrale volumetrico in [0,1]x[0,1]x[0,1] 3-dim:

Ulteriore problema matematico per analizzare l'uso delle sequenze è calcolare, sempre mediante il metodo Montecarlo, il volume di una sfera centrata in (1/2,1/2,1/2) e di un ellissoide all'interno del cubo tridimensionale [0,1]x[0,1]x[0,1]:

In particolare la sfera verrà identificata dalla sequenza random proveniente da QRNG, graficamente, come segue:

Il metodo è sempre ottenere la frequenza relativa di centrare il volume in studio "sparando" a caso (x,y,z) stavolta nel cubo [0,1]x[0,1]x[0,1].

3.d Integrale volumetrico in [0,1]x[0,1]x...x[0,1] n-dim:

Lo studio dei problemi matematici è stato esteso anche al calcolo con metodo Montecarlo del volume di un'ipersfera nello spazio n-dimensionale con n che varia da 4 a 10, ciò per evidenziare correlazioni tra i dati random. In questo caso il volume dell'ipersfera centrata in (1/2,1/2,...,1/2) è calcolabile in maniera precisa dalla formula seguente e naturalmente non sono possibili rappresentazioni grafiche:

3.e Sistemi di equazioni lineari 2-dim, 3-dim e 6-dim:

Per finire sono state considerate le risoluzioni con metodo Montecarlo dei seguenti sistemi di equazioni lineari a 2, 3 e 6 dimensioni. Le soluzioni esatte sono state trovate con il metodo classico del determinante, mentre il metodo Montecarlo, sfruttando le sequenze random, le ha "inseguite" con maggiore o minore efficacia:

Segue, quale esempio, una rappresentazione grafica di "inseguimento" del risultato (tracciato rosso insegue il punto blu) per uno dei 2 sistemi 3-dim mediante la sequenza PRNG:

3.f Analisi dei risultati (Montecarlo):

Partiamo dalla fine, nel senso di considerare la media aritmetica dei valori assoluti degli scostamenti di quanto ottenuto come soluzione "Montecarlo" dei problemi matematici descritti (impiegando le diverse sequenze random), rispetto alle soluzioni sopra indicate, ottenute tramite metodi deterministici classici (l'ordine del seguente elenco è relativo all'entità di tale errore medio):

b) QRNG Random Power: ERR = 0.00367;
c) QRNG Think Quantum: ERR = 0.00552;
a) QRNG Crypta Labs USB KEY: ERR = 0.00663 ;
e) PRNG Python3.12.3: ERR = 0.00673;
d) QRNG LFDR (cloud): ERR = 0.00888;
h) Potenze negative di 2: ERR = 0.01672;
g) Potenze positive di 2: ERR = 0.02202;
i) Decimali del numero di Eulero: ERR = 0.02373;
f) Sequenza binaria "normale": ERR = 0.052638.

La prima osservazione che si può fare è sicuramente relativa alla predominanza dei QRNG in quanto a minimo scostamento medio dai risultati ottimali. Fermo restando che ripetendo la prova con diverse altre sequenze per ognuna delle categorie si potrebbero avere delle variazioni, sicuramente non è una semplice fluttuazione che almeno 3 QRNG di natura e tecnologie diverse tra loro siano in testa rispetto al PRNG. In ogni caso, ripeto, questa è semplice sperimentazione e non un test statistico ufficiale per cui le mie sono valutazioni generali.

Considerazione a parte va invece fatta per le sequenze matematiche deterministiche che ho scelto per il loro particolare contenuto entropico: a parte la sequenza binaria "normale" che ha prestazioni pessime proprio perchè costruita su basi davvero elementari e quindi ampiamente prevedibili, le altre si comportano discretamente, anche considerando che la loro lunghezza è più limitata rispetto alle prime.

Dal punto di vista grafico è interessante vedere che le sequenze non PRNG e non QRNG evidenziano dei visibili schemi di comportamento nel calcolo degli integrali, di seguito alcuni esempi. L'integrale di f(x) = e-x calcolato sulla sequenza binaria "normale" (f) ottiene 0.53930 contro un valore esatto di 0.6321205588285577 ma la distribuzione geometrica dei punti sull'area di integrazione è evidentemente affetta da schemi predefiniti:

Lo stesso accade, ma in maniera più leggera, per le sequenze di potenze di 2 (h) e (g):

Sorprende, invece, vedere l'ottimo comportamento grafico della sequenza di Eulero, che ad esempio, per l'integrale di f(x) = x determina 0.4973120 contro il valore esatto 0.5. Tale comportamento simil-random viene spesso preso in considerazione nei test di randomness per discriminare la migliore casualità possibile da questo "buon" comportamento matematico:

Possiamo poi fare una considerazione rilevante sui sistemi lineari che hanno messo a dura prova le sequenze. Se consideriamo solo gli errori inerenti ad essi abbiamo:

b) QRNG Random Power: ERR = 0.04528;
c) QRNG Think Quantum: ERR = 0.05031;
a) QRNG Crypta Labs USB KEY: ERR = 0.06837 ;
h) Potenze negative di 2: ERR = 0.05466;
e) PRNG Python3.12.3: ERR = 0.08778;
d) QRNG LFDR (cloud): ERR = 0.14889;
g) Potenze positive di 2: ERR = 0.17457;
i) Decimali del numero di Eulero: ERR = 0.29058;
f) Sequenza binaria "normale": ERR = 0.32541.

che sono piuttosto elevati rispetto all'errore medio di cui sopra. Risulta lampante il balzo in avanti delle potenze negative di 2 che addirittura surclassano il PRNG e un QRNG ma molto probabilmente è solo un caso dato che le altre sequenze deterministiche non caotiche rimangono in basso con valori di errore rilevanti.

4. Conclusioni

I generatori di numeri random hanno sicuramente un fascino tutto loro, soprattutto per gli appassionati di matematica discreta come lo scrivente. I QRNG in particolare evidenziano chiaramente delle caratteristiche di alta qualità nella casualità, a prescindere dalle tecnologie che li implementano e per applicazioni scientifiche (come i metodi di calcolo visti) e di sicurezza risultano una scelta determinante. Sicuramente la lentezza dei QRNG attuali e il loro costo possono giustificare (confrontando le prestazioni) ancora l'uso di "buoni" PRNG che siano particolarmente testati e validati dalla comunità scientifica. Appunto finale sulle sequenze che sembrano random ma che non lo sono affatto, come l'espansione binaria del numero di Eulero: mai fidarsi di impiegarli al posto di QRNG e PRNG, neanche per eventuali prove (qualcuno li usa per generare password di prova, ma date le regolarità che evidenziano possono divenire estremamente prevedibili se affrontati con HPC o comunque potenti strumenti di calcolo).

marcomattiucci.it

Informatica:

Quantum Computing: