The Essence Of Randomness

       Anyone who considers arithmetic methods to produce random numbers, is in a state of sin.     
-Von Neumann       

                                                                                                         
                                                         
                 The generation of random numbers has a wide range of practical applications in fields as diverse as lotteries and games to encryption and national security. Thus, the sanctity of the process of generation of random numbers is of vital importance.                         
                 However, generating random numbers is much harder than it sounds for the simple reason that conventional computers are deterministic in nature; i.e. given an algorithm and an input, known as the seed, they will always produce the same output. Thus, it as it is not possible to generate true random numbers using a deterministic algorithm, most commonly used "random" number generators use a convoluted algorithm in order to obscure the underlying pattern behind their generation. These types of random number generators are known as 'pseudo-random' number generators. For most practical purposes such as random sampling and the modelling of some truly random events such as the rolling of a die or the tossing of a coin, pseudo-random number generators are sufficient as the error that occurs due to the biasing of the generation process is too minute to have major observational errors.
                           
The "Leviathan" from Elementary: The random number generator of the safe was attacked and compromised to produce escalating sequences of numbers from 𝝅 which seemed random. Such sequences satisfy the next-bit test for randomness but not the state compromise extension as given a sequence of digits, it is possible to find the preceding digits by running backwards through 𝝅.  

                                                             
                                                                                        A generic pseudo-random number generator



Some pseudo-random number generation techniques include linear congruential generators and the Blum-Blum-Shub generator.

Pseudo Random Number Generators

1. The Linear Congruential Generator


                                                                                                                      Given a seed number (input) and provided with a set of constant numbers (a,c,m) , the linear congruential will produce the next number in the sequence using the above described algorithm.                                                      
            However, as seen below, unless the values for a,c and m are chosen appropriately, the linear congruential generator will have a small period and thus, the obtainment of a series of outputs will lead to the compromise of the integrity of the random process.

           Thus, if (a,c,m) are chosen such that the periodicity of the LCG is too large to have a physical significance on the experiment or process to be modeled using the generator, the LCG can be used as a sufficiently secure pseudo-random number generator.

2. The Blum-Blum-Shub Generator                                                                                                                  The Blum-Blum-Shub generator is one of the more efficient pseudo-random number generators. It uses the concept of one-way functions (Functions for which the pre-image of a given output is computationally expensive to obtain) for the production of a sequence of numbers which seem random. This is also known as the quadratic residue generator. The set up for this generator requires two large primes p and q to be chosen such that p ≡ 3 (mod 4) ≡ q. The product of these primes is then calculated to attain the value n. Then, an integer value x is chosen such that x is co-prime to n. The initial seed of the BBS generator is then given by :                                                      
                               x(0) ≡ Math.pow(x,2) (mod n).                                        
                            
          The sequence of random bits b(0), b(1) … is then generated from the obtained sequence: where b(­j) is the least significant bit of the value x(j)­.                                                           
          However, this process is computationally expensive for a long series of random bits. To make it faster, it is possible to let b(0) through b(k) be the k least significant bits of x(j) provided that:                                                            
                                k < log2(log2(n))                                                                                                                                     
          However, it is not fundamentally safe to use pseudo-random number generators to secure information at a more important level such as matters related to national security as a breach of the sanctity of the modeling algorithm would, in essence compromise total security of data.                                                 
          The most commonly used method for the securing of data channels and sealing block-chain ledgers - RSA encryption - uses one-way functions to simulate random behavior and relies on the exponential time complexity of finding the prime factors of enormously large numbers to secure data. However, as Shor's algorithm proved, the exponential time complexity of finding the pre-image of a sufficiently large number is not due to a fundamental property of nature but a limiting factor in the computer architecture used today. Thus, the advancement of quantum computing or the development of a more advanced paradigm of parallel computing could render the RSA encryption obsolete. Thus, the development of a truly sacrosanct method of generating random numbers is required in the field of data encryption.                                              
          A truly random number generator is a hardware number generator which generates random numbers from a physical process - rather than an algorithm. They are based on microscopic phenomena that produce low-level , statistically random "noise" signals. These physical signals areconverted to electrical signals using a transducer and then amplified. 

The HNG developed by ComScire                                               
                                                   
           The physical process governing the hardware number generator can either a truly probabilistic process or a deterministic, chaotic and unstable dynamic system. Note that an unstable dynamic system can be used to model a random variable as it is not possible to determinstically determine the result of the process as to do so would require knowledge of all possible parameters of the system - which is impossible. This is the essence of randomness in experiments such as a coin toss or a die roll.                                                
           Let us now conduct an analysis of the various physical process which form the basis of HNGs, to determine the true essence of randomness.

A. Quantum Random Properties

1. Shot Noise                                                   
             

                                 
            Shot noise or Poisson noise  is a type of noise that can be modeled by the Poisson point process - which is a type of mathematical process or object that consists of points randomly located on a mathematical space. It arises due to the discrete nature of light emission in photonic or optical instruments or the discrete nature of charge in an electric circuit. Shot noise may be dominant when the finite number of particles that carry energy is sufficiently small so that uncertainties due to the Poisson distribution, which describes the occurrence of independent random events, are of significance.  However, when the number of particles that carry energy rises, the signal to noise ratio due to Shot noise, also rises as Shot noise is proportional to the square root of the energy packets while the signal strength is directly proportional to the number of packets,At high frequencies and low amplitudes of current, shot noise due to electronic randomness is the primary source of noise in a circuit and this can be used to simulate a random number generator on amplification.

2. Nuclear Decay From A Radiation Source                        
             Though nuclear decay is, on a gross scale, governed by its half life, on the scale of individual atoms, held in an excited state, it is a purely random process and one which can be used to model a Quantum Number Generator.

3. Photons Through A Semi-Transparent Mirror                 
                                       
                                    
              The passing of light through a semi-transparent mirror is governed by the reflectivity and transmittivity of the media involved, on a gross scale. However the passing of a single photon through the surface is probabilistic in nature, weighted by the reflectivity and transmittivity of the media. By assigning classical bit states to the two possible outcomes,it is possible to obtain a random number generator.

B. Classical Random Properties                                                 
              The basic classical random properties arise due to thermal noise which, at its core, is purely quantum mechanical in nature. This includes thermal noise from a resistor and thermal circuital phenomena such as avalanche breakdown.                                                                                                               Other classical physical processes used to model random number generators are, as mentioned earlier, deterministic, chaotic systems - which are not "truly" random - just random "enough".                                           
                

                     Hence, the true rigorous definition of randomness is satisfied by only probabilistic processes and since all true probabilistic processes "derive" their uncertainty from the randomness of quantum mechanical measurement, the true essence of randomness is ultimately, quantum mechanical in origin.