The Laws of Cryptography: The logistic Lattice as a RNG

The Laws of Cryptography:
The logistic Lattice as a
Random Number Generator

by Neal R. Wagner

NOTE: This site is obsolete. See:

Book draft (in PDF): The Laws of Cryptography with Java Code.
Original article: ``The logistic lattice in random number generation,'' Proc. 30th Annual Allerton Conf. on Comm., Control, and Computing, 1993, pp. 922-931: PDF copy
Remarks on the article: PDF copy

Here is a program implementing the logistic lattice in two dimensions. This code shows the results of three parallel runs, with the viscosity constant v equal to 0, 10^-12, and 10^-13. The code below does two steps of the equation at a time, for testing and demonstration purposes, since the variable NSTEP gets set to 1. An actual implementation would use NSTEP = 60, for 120 iterations.


// Chaotic2Dtest: class to give 3-by-3 logistic lattice
import java.util.*; // needed for Random class
import java.io.*;
public class Chaotic2Dtest {
   private final int NMAX = 3;          // size of lattice
   private final double BETA = 0.292893218813452476; // Magic number in f
   private double  NU; // = 1.0e-14;    // Viscosity constant in step
   private final double  TWO_DIV_PI = 0.636619772367581343; // 2/Pi in S
   private int  NSTEP; // = 60;         // Half # of steps to iterate
   private double[][] t;    // the seed array
   private double[][] tn;   // extra copy of seed array
   private double[][] tret; // transformed seed array to return
   private Random random;   // library random number generator

   // mod: need instead of %, because % can yield negative result
   private int mod(int i, int j) {      // If i is negative, then i%j
      int k = i%j;                      // may be negative.  In general,
      if (k < 0)  k = k + j;            // result is machine dependent.
      return(k);                        // Check your own architecture.
   }

   // Chaotic2Dtest: constructor.  Mainly initializes seed array
   public Chaotic2Dtest(long seed, double NuIn, int NSTEPIn) {
      t = new double[NMAX][NMAX];
      tn = new double[NMAX][NMAX];
      tret = new double[NMAX][NMAX];
      NU = NuIn; NSTEP = NSTEPIn;
      random = new Random(seed);
      for (int i = 0; i < NMAX; i++)
         for (int j = 0; j < NMAX; j++)
             t[i][j] = 2.0*random.nextDouble() - 1.0;
   }

   // f: the remapped logistic equation
   private double f(double x) {
      double temp = Math.abs(x);
      if (temp <= BETA) return(2.0*temp*(2.0-temp));
      else return(-2.0*(1.0-temp)*(1.0-temp));
   }

   // step: one step of the simulation.
   private void step(double[][] t, double[][] tn) { // Coupled map lattice
      for (int i = 0; i < NMAX; i++)
         for (int j = 0; j < NMAX; j++) 
            t[i][j] = f(t[i][j]);
      for (int i = 0; i < NMAX; i++)
         for (int j = 0; j < NMAX; j++)
            tn[i][j] = (1.0 - 4.0*NU)*t[i][j] + 
               NU*(t[mod(i-1, NMAX)][j] +
                   t[mod(i+1, NMAX)][j] +
                   t[i][mod(j-1, NMAX)] +
                   t[i][mod(j+1, NMAX)]);
   }

   // S: change distribution to uniform
   private double S(double x) {
      if (x >= 0) return(TWO_DIV_PI*Math.asin(Math.sqrt(x/2)));
      else return(TWO_DIV_PI*Math.asin(Math.sqrt(-x/2)) + 0.5);
   }

   // chaoticUniform: the generator itself.  Returns 9 doubles
   double[][] chaoticUniform() {
      for (int i = 0; i < NSTEP; i++) { // Iterate step 2*NSTEP times
         step(t, tn);
         step(tn, t);
      }
      for (int i = 0; i < NMAX; i++)
         for (int j = 0; j < NMAX; j++)
            tret[i][j] = S(t[i][j]);
      return tret;
   }

   public static void main(String[] args) throws IOException{
      int NMAX = 3;
      Chaotic2Dtest ct0 = new Chaotic2Dtest(1, 0.0, 1);
      Chaotic2Dtest ct1 = new Chaotic2Dtest(1, 1.0e-12, 1);
      Chaotic2Dtest ct2 = new Chaotic2Dtest(1, 1.0e-13, 1);
      double[][] t0, t1, t2;
      while(true) {
         System.in.read(); // hit return to do next iteration
         t0 = ct0.chaoticUniform();
         t1 = ct1.chaoticUniform();
         t2 = ct2.chaoticUniform();
         for (int i = 0; i < NMAX; i++)
            for (int j = 0; j < NMAX; j++)
               System.out.println(t0[i][j] + " \t" +
                                  t1[i][j] + " \t" +
                                  t2[i][j]);
      }
   }
}

Here is the function step for the second version of the equation that handles symmetries in the initial numbers.


   private void step(double[][] t, double[][] tn) { // Coupled map lattice
      for (int i = 0; i < NMAX; i++)
         for (int j = 0; j < NMAX; j++) 
            t[i][j] = f(t[i][j]);
      for (int i = 0; i < NMAX; i++)
         for (int j = 0; j < NMAX; j++)
            tn[i][j] = (1.0 - 4.0*NU)*t[i][j] + 
               NU*(1.1*t[mod(i-1, NMAX)][j] +
                   0.9*t[mod(i+1, NMAX)][j] +
                   1.2*t[i][mod(j-1, NMAX)] +
                   0.8*t[i][mod(j+1, NMAX)]);
   }

If all initial numbers are the same, all node values will remain the same. In the run shown below, all nodes were set to 0.5 except for one which was set to 0.4999999999999. The resulting output is shown for three values of v in three columns below: 0.0, 10^-12, and 10^-13. The value v = 0 would leave all nodes independent of one another, that is, just 9 independent logistic equations. Iterations 2, 48, 74, 100, and 120 are shown.

Notice that after 120 iterations, all node values in the middle column have drifted completely apart. This is the reason that 120 iterations are used in the generator itself.

Notice also that the initial value of 0.5 is transformed to itself by the remapped logistic equation. (This corresponds to 0.75 in the original equation.) This value is then transformed to 0.8333333... by the transformation S that yields numbers uniformly distributed in the interval from 0 to 1.

9 values for v = 0 9 values for v = 10^-12 9 values for v = 10^-13

Iteration number: 2 0.8333333333331865 0.8333333333331865 0.8333333333331865 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334

Iteration number: 48 0.5040834897791248 0.5036049050782517 0.5021691550116464 0.8333333333333334 0.8333333331818866 0.8333333333219761 0.8333333333333334 0.8333333332366295 0.83333333332515 0.8333333333333334 0.8333333332015176 0.8333333333229862 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333332189119 0.8333333333241839 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334 0.8333333333333334

Iteration number: 74 0.3602326768156076 0.5833674744417872 0.47153769384353167 0.8333333333333334 0.8231749738724833 0.8325716798549819 0.8333333333333334 0.826847020511059 0.8327845046032647 0.8333333333333334 0.8244919644092912 0.8326394144500628 0.8333333333333334 0.8333333333331181 0.8333333333333328 0.8333333333333334 0.8333333333331748 0.833333333333333 0.8333333333333334 0.8256584292117882 0.8327197098392694 0.8333333333333334 0.8333333333331479 0.8333333333333328 0.8333333333333334 0.8333333333332305 0.8333333333333331

Iteration number: 100 0.28322543483494855 0.9957436720669621 0.5329869100296993 0.8333333333333334 0.8698208441903008 0.3663600043966403 0.8333333333333334 0.24828271001134866 0.06072814757025873 0.8333333333333334 0.6086436328075263 0.7253693182396282 0.8333333333333334 0.8333152337340284 0.8333332244057435 0.8333333333333334 0.8333207796242934 0.8333332571545267 0.8333333333333334 0.7364311648949555 0.2422766762266617 0.8333333333333334 0.8333179900269688 0.8333332360776878 0.8333333333333334 0.833324925779414 0.8333332795639763

Iteration number: 120 0.8935574910647093 0.5833052795925358 0.7821714186572044 0.8333333333333334 0.7615175283592651 0.30797021553244913 0.8333333333333334 0.7909250549646865 0.07806647066456404 0.8333333333333334 0.6059141053682064 0.6417576242558025 0.8333333333333334 0.35452800150669156 0.719114512983271 0.8333333333333334 0.16981560934264034 0.7534540927550613 0.8333333333333334 0.045160386927817195 0.4919490670536787 0.8333333333333334 0.7447109018158442 0.7313534352471185 0.8333333333333334 0.9826254952427942 0.7769521043864014

Revision date: 2002-02-02. (Please use ISO 8601, the International Standard.)