This document tells about the Cellular Automata and Generation of Pseudo-Random Numbers Using Cellular Automata. Then it analyze the property of randomness between uniform CA and Non-Uniform CA
Cellular Automata (CA)
A method to study Science of Complexity, Space is discrete, represented by cells. Each cell has a finite number of states. Time is discrete, and we go through time step by step. Update rule of each cell depends only on local neighborhood. All cells are updated in parallel, based on information from the last time step [1]. One commonly used type of Pseudorandom Number Generators is based on Cellular Automata. Cellular Automata (CA) was initiated in the early of 1950s. In 1986, Wolfram first applied CA in pseudorandom number generation. Wolfram's work in [1] proved that the randomness of the patterns generated by maximum-length CA is significantly better than other widely used methods. The mathematician Stanislas Ulam who was interested in the evolution of graphic constructions generated by simple rules. The base of his construction was a two-dimensional space divided into "cells", a sort of grid. Each of these cells could have two states: ON or OFF. Starting from a given pattern, the following generation was determined according to neighborhood rules [2]. For example, if a cell was in contact with two "ON" cells, it would switch on too; otherwise it would switch off [3]. A new kind of science that have spent so much Effort building has seemed an ever more central and critical direction for future intellectual development. Automata are arranged geometrically. All automata are identical and change state simultaneously [3].
Fig 1 Example of Cellular Automata
The basic cellular automata elements are Lattice, Cell states, Neighborhood, Transition rules, Time [2, 3].
Transition rules: The transition function using the inputs and current state of the machine to put the machine into its next state.
Fig 2 Example of transition rule
Neighborhood: The neighborhood is the relation of the current cell to neighboring cells. The various neighboring types are von Neumann neighborhood, Moore neighborhood, Extended Moore neighborhood, Margoles neighborhood Considers groups of 2x2.
One State CA: Each cell has a left and right neighbor. All cells identical and can be initialized to different states
Fig 3 Example for One State CA
Two State CA: The two state CA is based upon certain rules they are as follows Rule 30, Rule 90, Rule 110 etc., [2,3]
Fig 4 Example of two states CA
Pseudorandom Number Generation (PRNG)
Random numbers are essential ingredients in a great number of solutions in computer science. Randomized algorithms require a random source to guarantee computational complexity bounds and sampling methods often require randomness to accurately represent the information they are surveying. We need to have a technique for generating numbers from empirical and theoretical distributions in a random fashion, these are uniformly distributed random numbers in (0, 1). They are usually referred to as random numbers. We really need pseudo-random numbers, not random numbers, so that we can verify and validate more easily. However, be computationally infeasible to distinguish a good PRNG from a perfect RNG. For example, a PRNG seeded with 256-bits of entropy (or one with a 256-bit state) cannot produce more than 256 bits of true randomness. An attacker who can guess the seed data can predict the entire PRNG output. Guessing a 256-bit seed value is computationally infeasible, however, so it is possible that such a PRNG could be used in cryptographic applications. Examples of PRNGs designed for cryptographic applications include MD5Random and SHA1Random (which respectively hold 128 bits and 160 bits of state) in the BSAFETM, 3 cryptographic toolkits. Although properly-implemented and seeded PRNGs are suitable for most cryptographic applications, great care must be taken in the development, testing, and selection of PRNG algorithms. It is critical that a PRNG be properly seeded from a reliable source. For example, most PRNGs included in standard software libraries use predictable seed or state values or produce output that can be distinguished from random data.
Pseudo random numbers are generated using different methods, such as: linear Congruential Generator, Tausworthe Generators, and The Mersenne Twister [4].
Example: Linear Congruential Methods: A very popular technique. It uses the relationship:
xi +1 = a xi + c (mod m)
The starting value x0 is known as the seed. Example: if x0 = 0, a = c = 7, and m = 10.Then we can obtain the following sequence of numbers: 7,6,9,0,7,6,9,0,... [4, 5]
Good Random Number Generators should have following issues Randomness, knowledge of the distribution, independent of the previous number, long period, produce the same sequence if started with same initial conditions, fast. Sources of Random Numbers are Tables, Hardware (external sources of random numbers -generates random numbers from a physics process, Software (source of pseudorandom numbers)
.A good PRNG will have a high degree of unpredictability, making the output ungues sable, which is the goal [6].
Uniform CA and Non-Uniform CA
Uniform CA is nothing but using of one rule for generating random number. The rules may be rule 30, rule 90, rule 105, rule 150, rule 165. Whereas Non-Uniform CA uses more than one rule for generating random numbers. It has been said that with the idea of Uniform CA only many researchers focused on Non-Uniform CA. The first Non-uniform CA PRNG was proposed by P. D. Hortensius in 1989 [7]. This Non-uniform CA uses rule 90 and 150. This CA PRNG is referred to hence as CA 90-150. Surprisingly, the combination of these two simple linear rules yields maximum length cycles. Unlike uniform rule-25 CA, adjacent cells in non-uniform CA are not correlated in both time and space. However, the binary sequences produced by some cells in a non-uniform CA fail some random number tests because of distribution problems. Another non-uniform CA PRNG which uses the combination of rules 30 and 45 was also proposed by P. D. Hortensius. This generator can evolve to a random pattern of outputs, but its bit sequence correlation is much higher than that of the PCA 90-150. Later in 1996, Sipper and Tomassini evolved a 50-cell CA with a mélange of rules 90, 150 and 165 [8]. This CA is referred to henceforth as PCA 90-165. Based on their work, Tomassini et al. evolved another 50-cell CA with the rule combination 90, 165,150 and 105 in 1999. This CA is referred to henceforth as PCA 90-105. These two CA are evolved using cellular programming evolution algorithm while those two CA proposed by P. D. Hortensius are handcrafted. The DIEHARD test results show that these two non-uniform CA PRNGs are better than those designed by P. D. Hortensius in. But they still cannot pass some of the tests in DIEHARD and are inferior to the classical generator [7, 8, 9].
Diehard Test Suite
Die harder implements and extends George Marsaglia's Diehard Battery of Tests of Randomness (Marsaglia, 1996). Due to both its robust performance over a wide variety of RNGs, as well as an ability to discern numerous RNGs as weak, Diehard has become something close to a `gold standard' for assessing RNGs [7]. The Diehard test suite consists of 15 tests which also possess the probability value (P-value) for each test. Both the Uniform CA and Non-Uniform CA are subjected for 15 tests and depending upon the P-value
The randomness property of Uniform CA and Non-Uniform CA are analyzed. DIEHARD seems to be the most powerful general test for randomness. Generally, a PRNG which pass DIEHARD can be considered good. The DIEHARD battery of test consists of 18 different independent statistical tests. Results of tests are so called "P-value" which is a real number between 0 and 1. For any given test, smaller P-value means better test result with the exception that a P value less than 0.025 or larger than 0.975 means that the PRNG has failed the test at the .05 level. A complete description of all the tests in DIEHARD is available in [11, 12]
The Diehard tests were developed by Prof. Georges Marsaglia from the Florida state University. This statistical test suite is usually considered to be "the most powerful general test of randomness". The test suite consists of 15 different independent statistical tests and requires at least 80 million bits (10-12 Megabytes) in binary format [11].
Birthday Spacing
The name is based on Birthday Paradox. Chooses random points on a large interval and lists the spacing's between the points. The number of values that appear more than once in the list should be asymptotically Poisson distributed.
Overlapping Permutations
This is the overlapping 5-Permutation (OPERM5) test. Analyzes sequences of five consecutive 32 bit random integers. It looks at a sequence of 1 million such 32 bit random integers. Each set of five consecutive integers can be in one of 120 states for the 5! Possible orderings of five numbers.
Ranks of 31x31 and 32x32 Matrices Test
This test has two sub tests which performs Binary Rank test for 31x31 and 32x32 Matrices. The leftmost 31 bits of 31 random integers are selected from the bit stream to form a 31x31 Matrix and 32 random integers are selected to form a 32x32 Matrix and the ranks are determined over the field (0,1).
Ranks of 6x8 Matrices Test
This is a Binary Rank Test for 6x8 Matrices. Six random 32 bit integers are chosen from the testing bit stream and a single byte from those random integers are chosen to form 6x8 Matrices. Ranks over the field (0,1) are determined for 100,000 such matrices .
Monkey Tests on 20-Bit Words
The name is based on the infinite Monkey Theorem. Treat sequences of 20 bits as words and the test counts the number of missing 20-bit words in a string of 221 overlapping 20 bit words. The number of missing words should be normally distributed. Test is repeated for 20 times and returns the number of the missing words, Z-score (standard normal variate) values and associated P-values for all the runs.
Monkey Tests OPSO, OQSO, DNA
This test consists of 3 sub tests OPSO (Overlapping-Pairs-Sparse-Occupancy) This test is similar to the Monkey tests on 20-bit words except it considers 2 letter Words from an alphabet of 1024 letters. Each letter is determined by a specified ten bits from a 32 bit integer in the bit stream. OPSO generates 221 overlapping 2-letter words from ((221+1) keystrokes and counts the number of missing 2-letter words.
OQSO (Overlapping-Quadruples-Sparse-Occupancy) It is similar to the Monkey tests on 20-bit words except it considers 4 letter words from an alphabet of 32 letters. Each letter is determined by a specified five bits from a 32 bit integer in the bit stream. OQSO generates 221 overlapping 4-letter words from ((221) +3) keystrokes and counts the number of missing 4-letter words.
DNA This test is similar to the Monkey tests on 20-bit words except it considers an alphabet of 4 letters C,G,A,T determined by two designated bits in the bit stream. It considers 10 letter words. DNA generates 221 overlapping 10-letter words from ((221) +9) keystrokes and counts the number of missing 10-letter words.
Count The 1's in s Stream of Bytes
Consider the bit stream under test as a stream of bytes. Hence, each byte can contain 0 to 8 1's with different probabilities. Test converts the count to five letter words Viz. A, B, C, D and E. Letters are determined by the number of 1's in a byte. There are 55 possible 5-letter words and the counts are made on the frequencies for each word from a string of 256,000 overlapping 5 letter words. Test returns a P-value, its associated chi-square and Z-score values, and degrees of freedom.
Count The 1's in Specific Bytes
Count the 1's in specific bytes test is similar to the count the 1's in a stream of bytes test except for a specific byte say the leftmost byte is chosen from each integer. Test is repeated for 25 times for bits 1-8, 2-9, ..., 25-32 from integers in the bit stream. Test returns 25 P-values, their associated Chi-Square, and Z-score values, and degrees of freedom.
Parking Lot Test
Randomly park a car of a circle radius in a square of side 100. Then try to park the 2nd, 3rd and so on, if the car overlaps an existing one then try again. After 12,000 attempts the number of successfully parked cars should follow a certain normal distribution.
Minimum Distance Test
Place randomly chosen 8000 points in a square of side 1000. Find the minimum distance between the pairs. The square of this distance should be exponentially distributed.
Random Spheres Test
Choose 4000 random points in a cube of edge 1000. Centre a sphere at each point such that large enough to reach the next closest point. The smallest sphere's volume should be exponentially distributed.
The Squeeze Test
Multiply 231 by random floats on (0, 1) until you reach 1. The random floats are provided by floating random integers from the bit stream to get a sequence of uniform variables on (0, 1). The number of iterations needed to reach 1 should follow a certain distribution.
Overlapping Sums Test
Random integers are floated to get a sequence of uniform variables on (0, 1). Add sequences of 100 consecutive floats. The sum should be normally distributed.
Runs Test
Test counts runs up, and runs down in a sequence of random floats uniform on (0, 1) obtained by floating 32-bit integers in the testing bit stream. Ascending (runs up) and descending (runs down) runs are counted for sequences of length 10,000.
The Craps Test
Test plays 200,000 games of craps, counts the number of wins and number of throws necessary to end each game. The number of wins should follow a normal distribution with mean 200000*p and variance 200000*p*(1-p) where p is 244/495. Throws necessary to complete the game can be any value between 1 and infinity but all the values above 21 are grouped under 21.
EXISTING SYSTEM
Following the idea of uniform CA PRNs, more researchers focus their interest on non-uniform CA PRNGs since non-uniform CA PRNs are better than uniform ones in general. The first non-uniform CA PRNG was proposed by P. D. Hortensius in 1999 [8]. This non-uniform CA uses rule 90 and 150. This CA PRNs is referred to hence as PCA 90-150. Surprisingly, the combination of these two simple linear rules yields maximum length cycles. Unlike uniform rule-30 CA, adjacent cells in non-uniform CA are not correlated in both time and space
Later in 2002, Sipper and Tomassini [10] evolved a 50-cell CA with a mélange of rules 90, 150 and 165. This CA is referred to henceforth as PCA 90-165. Based on their work, Tomassini et al. [10] evolved another 50-cell CA with the rule combination 90, 165,150 and 105 in 2005. This CA is referred to henceforth as PCA 90-105. These two CA are evolved using cellular programming while those two CA proposed by P. D. Hortensius are handcrafted. The DIEHARD test results show that these two non-uniform CA PRNGs are better than those designed by P. D. Hortensius in [7].
Chowdhury et al. [8] described a methodology for producing pseudorandom numbers by 2-d CA in 1994. Their results suggest that 2-d CA are superior to 1-d ones of the same size in pseudorandom number generation. Following his idea, Marco Tomassini et al. evolved several 8X8 2-d CA PRNGs with rule 15, 63, 31 and 47. DIEDARD test results show that some of the evolved CA PRNGs can pass all the tests in DIEHARD and based on the observation of these evolved 2-d CA PRNs, they can handcraft even better PRNs. Although 2-d CA PRNs are better than 1-d CA PRNs in random number generation, they lose the structure simplicity and computation efficiency of 1-d CA PRNs [7,8].
PROPOSED SYSTEM
Following the idea from P.D. Hortensius, Sipper and Tomassini, we evolve 1-d CA Pseudo-Random Number generator with rule combinations of 150 and 105 in non-uniform CA referred to as PCA 150-105. We also evolve a high quality 1-d CA Pseudo-Random Number Generator with help of rule 90 in uniform CA. Then we test their randomness using DIEHARD test suite and analyze the results and find which Pseudo-Random Number Generator has more randomness property.
EXPERIMENTAL SETUP
The requirements for this analysis are, at first we have generate the PRN's and those PRN's are stored in the ASCII format.
Then those ASCII form is transformed into binary format and then it is fed into the Diehard test suite for testing, the resulting value is noted and tabulated.
The experimental setup holds upon both the software requirements and hardware requirements. The software requirement specification is produced for the analysis task. The function and performance allocated to software as part of system engineering are refined by establishing a complete information description as functional representation; it consists of performance requirements and designing criteria.
Interface
Hard disk: 40GB
RAM : 256 MB
Processor Speed: 2 GHz
Processor: Pentium IV processor or Pentium Duo
System Type: 32 bit-Operating Speed
Software Interface
JDK 1.4.
Die Hard Test Suite.
MS-Excel.
Pseudo Random Number Generation by Uniform Cellular Automata using Rule 90
We know that uniform CA means using of one rule. The random number generation for uniform CA is done using by rule 90. The rule 90 has a rule set, which governs the next state of the automaton.
By using the rule set we can define the next state of generation by as follows:
Table I Rule Set for Rule 90
Current Pattern
New state for center cell
111
0
110
1
101
0
100
1
011
1
010
0
001
1
000
0
Example
T=0
1
1
0
1
0
1
0
1
1
1
T=1
1
1
0
0
0
0
0
1
0
0
T=2
1
1
1
0
0
0
1
0
1
1
T =0, 1, 2... are the time of next state. Let us consider the first state at T=0 as the initial state and with the help of the rule set, consider 1 0 1 at T=1 can be defined as 0 below the 0th bit, where the both 1s are neighborhood cells with the help of the neighborhood cells only we can generate next state with the usage of rule set.
Pseudo Random Number Generation by Non Uniform Cellular Automata using Rule 150 and Rule 105
We know that non uniform CA means using of more than one rule. The random number generation for non uniform CA is done using by rule 150 and rule 105 respectively. Both rules 150 and 105 have rule sets, which governs the next state of the automaton. Rule 150 is used first and the number generated with rule 150 is again subjected to rule 105. The rule set of 150 and 105 are shown in table II and III.
Table II Rule Set for Rule 150 Table III Rule Set for Rule 105
Current Pattern
New state for center cell
111
0
110
1
101
1
100
0
011
1
010
0
001
0
000
1
Current Pattern
New state for center cell
111
1
110
0
101
0
100
1
011
0
010
1
001
1
000
0
Table II and Table III corresponds to rule 150 and rule 105 respectively. By using the above rule set we can define the next state of generation by as follows:
Example
T=0
1
1
0
1
0
1
0
1
1
1
T=1(Rule 150)
1
1
1
0
1
0
1
1
0
0
T=2(Rule 105)
0
1
0
0
1
0
0
0
1
1
T =0, 1, 2...are the time of next state. Let us consider the first state at T=0 as the initial state and with the help of the rule set, consider 1 0 1 at T=1 by using the rule 150 at first can be defined as 1 below the 0th bit, where the both 1s are neighborhood cells, also consider 1 0 1 at T=2 by using the rule 105 can be defined as 0 below the 0th bit, where the both 1s are neighborhood cells with the help of the neighborhood cells only we can generate next state with the usage of rule set.
EXPERIMENT RESULT
Results of Uniform CA PRN and Non Uniform CA PRN after the DIEHARD Test is Tabulated and then a graph is drawn to differentiate both.
Tabulation
No
Tests
Uniform
CA PRN
Non-Uniform
CA PRN
1
Birthday
Spacing
0.255786
0.798438
2
Overlapping
Permutation
0.502316
0.875516
3
Ranks of 31*31
And 32*32
0.67224
0.538412
4
Ranks of 6*8
0.281358
0.342772
5
Bit Streams
0.69201
0.60202
6
OPSO,OQSO,
DNA
1.000000
0.610967
7
Count the 1's in Stream of bytes
0.066826
0.4038823
8
Count the 1's in Specific Bytes
0.882102
0.497181
9
Parking Lot Test
0.784961
0.669675
10
Minimum Distance Test
0.671126
0.293997
11
Random Spheres Test
0.94217
0.618361
12
Squeeze Test
0.639666
0.304911
13
Overlapping
Sums Tests
0.896476
0.627911
14
Runs Tests
0.188311
0.514558
15
Craps Tests
0.870281
0.214467TABLE IV
Graphical Representation
Fig 8 Analysis of random property between Uniform CA PRN and Non-Uniform CA PRN
Result Analysis
After the generation of Pseudo Random Numbers, they are subjected for testing. The testing is performed by using the Diehard test suite. The uniform CA PRN's and non uniform CA PRN's are tested and their values are noted and tabulated. A graph is plotted with the tabulated values of uniform CA PRN's and non uniform PRN's.
Now we have to analyze that each test value should lie in between the p-values i.e. 0.025<p-value<0.975. Looking upon the table and graph that non uniform CA passes all the 15 tests within the p-value limits whereas, uniform CA fails in one test i.e. in Monkey test because its tested value is 1 but the limit of the tested value should be less than 0.975, also look upon another test of uniform CA count the 1's in s stream of bytes in this the p-values it passes at the extreme end of the condition.
Let us take tests in the x-axis and p-value in the y-axis wit suitable scale of measurement. Now values of 15 tests and their corresponding p-values plotted for respective tests. After plotting the values of uniform CA and non uniform CA into the graph it clearly gives the idea for analyzing.
This provides a breakthrough for the analyzing, by examining the graph we can state that non uniform CA has more randomness rather than the uniform CA because the Non uniform CA passes the entire test within the boundary limit and they don't pass even nearer to the boundary limits.
CONCLUSION
Pseudo-Random Numbers are generated with the help of Uniform Cellular Automata and Non-Uniform cellular Automata. Both the numbers are exported in separated ASCII file in hexadecimal format. Then the both files are tested with Die-Hard Test Suite. The p-values of each test obtained from the test suite are noted. Then the graph was drawn based on p-values obtained. On analyzing the graph some of the p-values of Uniform Cellular Automata exceeded the boundary values.
But p-values of Non-Uniform Cellular Automata lies between the boundary values. So that we concluded that the randomness of generated PRN from Non-Uniform Cellular Automata was higher than Uniform Cellular Automata.
FUTURE WORK
The rules used in this analysis part are PCA 90,150 and 105. In future the another set of rules will be worked on non-uniform CA and randomness will be analyzed between PCA 90,150 and 105 with the working of another set of rules. Using PCA 90, 150 and 105 the same work will be implemented in 2-d CA.
APPLICATION
The various applications of CA are Cluster shape modeling (Deforming a cluster in 400 rigid balls), RD Texture generation (Maze formation and zebra formation), Virtual clay modeling (virtual clay work system), Erosion of the bones by 3D-CA (at various time period the erosion of bones are checked,) Hyper texture and Parallel particle systems (collision and scattering, flame particles in wind and aggregation of particle) and the major application is cryptography (encryption and decryption of cipher text) [14, 15].
