Generatori di numeri pseudocasuali: i casi shift-register e lagged Fibonacci

Abstract

La casualità è un concetto centrale in molteplici ambiti, dalla scienza alla vita quotidiana, e in particolare in numerosi settori come la crittografia, la simulazione e la statistica, dove viene utilizzata per generare risposte nuove e imprevedibili a partire da input dati. Alla base di questa generazione ci sono i numeri pseudo-casuali, generati tramite algoritmi noti come Generatori di Numeri Pseudo-Casuali (PRNG). Questa tesi esplora i generatori shift-register e lagged Fibonacci, analizzandone il funzionamento, il periodo e la qualità statistica delle sequenze generate. Il primo capitolo introduce i criteri per valutare la qualità di un PRNG, con particolare attenzione ai test DieHard. Nel secondo capitolo, vengono descritti in dettaglio i generatori shift-register, che sono efficienti ma con periodi brevi, e i lagged Fibonacci, che offrono periodi più lunghi e maggiore indipendenza nelle sequenze, sebbene con una maggiore complessità computazionale. I risultati mostrano che, pur essendo più semplici, gli shift-register presentano limitazioni nella qualità statistica delle sequenze, mentre i lagged Fibonacci, pur essendo più complessi, garantiscono prestazioni migliori in termini di indipendenza e robustezza.

Randomness is a fundamental concept in various fields, from science to everyday life, and is particularly important in areas such as cryptography, simulation, and statistics, where it is used to generate new and unpredictable outcomes based on given inputs. At the heart of this generation are pseudo-random numbers, produced through algorithms known as Pseudo-Random Number Generators (PRNGs). This thesis examines the shift-register and lagged Fibonacci generators, analyzing their functionality, period, and the statistical quality of the generated sequences. The first chapter introduces the criteria for evaluating the quality of a PRNG, with a focus on the DieHard tests. The second chapter provides a detailed description of shift-register generators, which are efficient but have short periods, and lagged Fibonacci generators, which offer longer periods and greater independence in the sequences, although with higher computational complexity. The results show that while shift-registers are simpler, they have limitations in terms of the statistical quality of the sequences. In contrast, lagged Fibonacci generators, although more complex, deliver better performance in terms of sequence independence and robustness.