factorial
randomness generator
factorial
randomness generator means that it is based on extracting the raw chaos in the
divisor sequence in other words factor sequence of consecutive natural numbers.
SATOCONOR.COM 
J.G. van der Galiën ‘A Factorial Randomness Generator
(FRAG PRNG)’ 3.1. (2004)
Full paper
SATOCONOR.COM
Journal of RANDOMICS
A Factorial Randomness Generator (FRAG
PRNG)
Extracting the raw chaos in the divisors
of natural numbers
By Johan
Gerard van der Galiën (M.Sc.)
For comments johan.van.der.galien@satoconor.com
Version 3.0 March 1, 2006 (version 1.0
December 17, 2004)
HOME of Scientia
Araneae Totius Orbis
Download
FRAG = NIARG source code
Abstract:
In
this article I describe the Factorial Randomness Generator (FRAG) that extracts
random bits from the raw chaos in the distribution of the digits of the divisor
pairs from the natural numbers.
This
extraction goes in good yield of about 25% giving analytical pure random bits
that pass 214 of 227 randomness tests. In theory this Pseudo Random Number
Generator is a-periodic. The only limitations are the used integer types for
factoring the divisor pairs. I used the PASCAL Cardinal integer type for this.
So there is a software limitation and the factored numbers can only be as big
as 232 – 1. This gives a practical period of 236. But one
can of course use a Multi Precision Integer Arithmetic Library to handle the
factored number and then the only limitation is hardware (computer memory).
Numbers
of magnitude 1060 can be factored in a reasonable amount of time by
such units. This comes down to a period of 2228.
The
mean bitrate of the PASCAL-implementation for 10 Mb random bits is 2.660 Mbits
per second. But this is initially not a constant value, which is demonstrated
by a non-linear regression model of the bitrate versus target file size. From
this model one can conclude that the asymptote of the hyperbolic relationship
is approximately at 0.23 – 0.31 Mbits per second. At target file sizes greater
than 1 Gb it comes close to this value.
1.
Introduction
The algorithm of the Factorial
Randomness Generator (FRAG) extracts random bits from the raw chaos in the
divisor pairs (other word for factor pairs) of the natural number sequence (N).
Trail divisions (brute force) find the divisor pairs. (There are of course more
efficient methods like modern ones based on the sieve of Eratosthenes.) This is
how I did the PASCAL implementation (FRAGPAS1.EXE). The raw chaos in the
divisor pairs has of course a connection to the prime factors. Because the divisor
pairs (d1, d2) are related to the prime factors (pn) through 1.1..
N = p1a*p2b*p3c*p4d*…… d1 = p1 and d2 = p1a-1*p2b*p3c*p4d*…… (1.1.)
If one knows all the prime factors of a natural
number, all the divisor pairs are determined and thus can be calculated.
One must know that there is no
mathematical formula yet to calculate either the divisor pairs or the prime
factors of a natural number. Even if there was than the calculations are
probably an enormous burden for a computer, similar as the formula of Ruiz for
the prime numbers.1 This formula is for the first hundred prime
numbers about 1000 times slower than brute force algorithms, in this case trial
divisions.2 I believe, considering this, that any factoring
algorithm will be faster than any implementation of a not yet discovered
mathematical formula for the prime factors.
For finding the divisor pairs I used
brute force because the maximum factored number that the Cardinal integer type
of PASCAL can handle is only 232 – 1 = 4,294,967,295. So I think
there is no gain in using advanced factoring methods like Williams (p – 1),
Pollard (p + 1), Lenstra and Quadratic Sieve. These factoring algorithms can
process, on a single PC, and are faster that brute force for numbers around 1020
–
2. Results
Theoretically
the capacity of the algorithm is limitless, as I will demonstrate to you in the
discussion, but there is the practical angle of how fast implementations can
produce a certain amount of random bits. For the PASCAL implementation the
measured mean bit rates for obtaining several different amounts of random bits
are shown in Table 1.
|
Target file size in bytes Ytarget |
Highest factored number Xfactor |
Mean bitrate in Mbits per second |
|
10,302 |
4,920 |
5.614 |
|
102,971 |
34,161 |
4.922 |
|
1,049,511 |
253,450 |
3.604 |
|
10,486,694 |
1,924,307 |
2.660 |
|
104,858,224 |
15,063,149 |
1.489 |
|
1,073,742,094 |
122,907,880 |
0.7424 |
Table 1: Measurements done on producing random bits files of different sizes
with the PASCAL implementation of the algorithm using Trail Division to find
the factor pairs. The mean bit rate is for a ‘State of the Art’ computer from 2004
running on Windows XP.
I used a ‘State of the Art’ computer of
2001; this is now 5 years ago, for the results of Table 1. My computer is an
AMD Athlon 700 MHz. The fastest computer in a store was a 4.0 GHz AMD (2004).
This is below the prediction by
One can find data about other RNG’s on
the Internet. Or one can do tests on random bits downloaded from the Internet
like HotBits. For two hardware RNG’s
I did a compare in Table 2.
|
|
FRAG PRNG |
Random.org |
HotBits |
|
Entropy in bits per bit |
1.000000 |
0.999976 |
0.999999 |
|
Optimum compression in % |
0 |
0 |
0 |
|
Arithmetic mean of data
bits (0.5 = random) |
0.4998 |
0.4998 |
0.4994 |
|
Error |
3.141403850 0.01% |
3.138961792 0.08% |
3.150390625 0.28% |
|
Serial correlation
coefficient (random = 0.0) |
0.000308 |
0.000417 |
-0.000128 |
|
File size |
102400 Kb |
1000 Kb |
226 Kb |
Table 2: Comparing FRAG with two hardware RNG’s found on the Internet, who all claim to be genuine random. These results were produced with aid of ENT.EXE.3 Random.org uses atmospheric noise from a FM radio, it tunes in on unused frequencies.4 HotBits uses a Quantum Mechanical source namely timing radioactive decay events of 85Krypton.5
Besides the randomness tests from
ENT.EXE I conducted 217 other tests on a numerous amount of different random
bit files from the PASCAL-implementations of the algorithm. Seven of these
tests are described by Knuth like entropy, frequency-binary,
frequency-hexadecimal, Kolmogorov-Smirnov, serial, gap and differential test.6
Additionally all 17 from the difficult to pass DIEHARD v0.2 beta test suite7
and 189 from the NIST sts-1.6 cryptographic test suite13.
1 Birthday Spacings
2 GCD
3 Gorilla
4 Overlapping Permutations
5 Ranks of 31x31 and 32x32 matrices
6 Ranks of 6x8 Matrices
7 Monkey Tests on 20-bit Words
8 Monkey Tests OPSO,OQSO,DNA
9 Count the 1`s in a Stream of Bytes
10 Count the 1`s in Specific Bytes
11 Parking Lot Test
12 Minimum Distance Test
13 Random Spheres Test
14
The Sqeeze Test
15 Overlapping Sums Test
16 Runs Up and Down Test
17 The Craps Test
Because ENT.EXE can also run in byte
mode and also calculates the chi-square distribution on the samples, which is
not shown in Table 2, there are 4 additional tests, (twice chi-square, entropy
and arithmetic mean of the data). Together with 4 tests (RABENZI18)
I developed my self this makes the total 227 tests.
Entropy = 1.000000 bits per bit.
Optimum compression would reduce the size
of this 838865792 bit file by 0 percent.
Chi square distribution for 838865792 samples is 111.50, and
randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bits is 0.4998 (0.5 = random).
Serial correlation coefficient is 0.000308 (totally uncorrelated =
0.0).
Entropy = 7.999992 bits per byte.
Optimum compression would reduce the size
of this 104858224 byte file by 0 percent.
Chi square distribution for 104858224 samples is 1098.64, and
randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 127.4488 (127.5 = random).
Serial correlation coefficient is 0.000116 (totally uncorrelated =
0.0).
Fig. 1: The ENT test
suite applied on the first 100 Mb random bits made by FRAG PRNG.3
----------------------------
Benford and Zipf randomness tests with Double and Real48 numbers
for 100MbFRAGPAS1SAMPLE1.DAT
-------------DOUBLE---------------
Total amount 64 bit chunks read = 13107278
Total amount of Double numbers between -10^308 and 10^308 =
13094515
Total amount of NaNs = 6865
----------------------------
Test for the fit with the Law of Benford (Double)
CHI-Benford Double =
1.52783511873703E+0001
CHI 8 degrees of freedom 5%
= 2.73
CHI
8 degrees of freedom 95% = 15.51
----------------------------
Test for correlation with Zipf (Double)
Slope = -8.62318325817512E-0001
Slope for an infinite random file = -0.8636655870
Intersection = -5.04338695774781E-0001
Intersection for an infinite random file = -0.5037512926
Correlation coefficient (R) = -9.99250179571464E-0001
Preliminary random criterion: -0.9992296195 < R <
-0.9990000000
-------------REAL48---------------
Total amount of 48 bit chunks read = 17476370
Total amount of Real48 numbers between -10^38 and 10^38 = 17350602
Total amount of Denormals and Zeroes = 69450
----------------------------
Test for the fit with the Law of Benford (Real48)
CHI-Benford Real48 =
1.01237847305976E+0003
CHI 8 degrees of freedom 5%
= 2.73
CHI 8 degrees of freedom 95% = 15.51
----------------------------
Test for correlation with Zipf (Real48)
Slope = -8.55831831965757E-0001
Slope for an infinite random file = -0.8636655870
Intersection = -5.06964840925233E-0001
Intersection for an infinite random file = -0.5037512926
Correlation coefficient (R) = -9.99120975093920E-0001
Preliminary random criterion: -0.9992296195 =< R =<
-0.9990000000
----------------------------
Fig. 2: RABENZI1 test suite applied on the first 10 Mb random file
made by FRAG PRNG. Tests developed by my self.8
------------------------------
Size of file 100MbFRAGPAS1SAMPLE1.DAT = 104858224 bytes
------------------------------
Entropy =
9.99999904120159E-0001 bits per bit
------------------------------
CHI-Bits =
1.11499614260159E+0002
CHI 1 degree of freedom 5% = 0.00
CHI 1 degree of freedom 95% = 3.84
------------------------------
CHI-Hexadecimal= 5.33631589869037E+0002
CHI 15 degrees of freedom 5% = 7.261
CHI 15 degrees of freedom 95% = 25.00
------------------------------
KS-analysis
KnPlusMax =
5.26067926026008E+0000
KnMinusMax =
5.26061020707130E+0000
Kn/Probability Distribution at 1% = 7.08769147510111E-0002
Kn/Probability Distribution at 5% = 1.60134202038989E-0001
Kn/Probability Distribution at 25% = 3.79252304123838E-0001
Kn/Probability Distribution at 50% = 5.88693507161224E-0001
Kn/Probability Distribution at 75% = 8.32543107060701E-0001
Kn/Probability Distribution at 95% = 1.22386191124315E+0000
Kn/Probability Distribution at 99% = 1.51741562528878E+0000
------------------------------
CHI-Serial =
1.09863689629920E+0003
CHI 255 degrees of freedom 5% = 219.0
CHI 255 degrees of freedom 95% = 293.3
----------------------------
CHI-Differential =
2.04098236945458E+0002
CHI 30 degrees of freedom 5% = 18.49
CHI 30 degrees of freedom 95% = 43.77
------------------------------
CHI-Gap =
1.37395590667575E+0004
CHI 50 degrees of freedom 5% = 34.8
CHI 50 degrees of freedom 95% = 67.5
------------------------------
Fig. 3: RANTESTS test suite applied on the first 100 Mb random bits
made by FRAG PRNG. Programmed from Knuth.6
All p-values:
0.2774,0.4830,0.6628,0.9400,0.6826,0.0428,0.0563,0.0270,0.5892,0.3442,
0.0237,0.6401,0.8491,0.3683,0.1421,0.4488,0.5246,0.2699,0.8514,0.2732,
0.9948,0.9948,0.9992,0.9967,0.9446,0.2992,0.3892,0.0562,0.9316,0.9932,
0.9167,0.3613,0.0243,0.1232,0.9101,0.8335,0.8291,0.8626,0.0835,0.2579,
0.0013,0.7632,0.2146,0.7801,0.8591,0.8016,0.5462,0.5647,0.7433,0.3419,
0.9389,0.0832,0.3410,0.5397,0.9871,0.0685,0.8984,0.5146,0.9878,0.6787,
0.7983,0.8900,0.4216,0.8588,0.3569,0.9640,0.9728,0.6788,0.8648,0.1317,
0.3608,0.7630,0.4542,0.4029,0.9717,0.9435,0.8282,0.7620,0.9785,0.8707,
0.2145,0.0848,0.2007,0.1801,0.4874,0.9720,0.6723,0.1365,0.3784,0.7572,
0.5104,0.4349,0.5131,0.7332,0.8143,0.7572,0.3281,0.2235,0.1053,0.2453,
0.8968,0.6929,0.9574,0.7443,0.9872,0.4256,0.8992,0.4456,0.3004,0.0186,
0.9632,0.9297,0.2933,0.3213,0.3747,0.3192,0.2893,0.3635,0.6346,0.2862,
0.4294,0.9459,0.0486,0.9885,0.4620,0.3066,0.6257,0.7834,0.8195,0.9700,
0.4422,0.8353,0.1367,0.3961,0.3427,0.1027,0.6748,0.9884,0.4996,0.9340,
0.7720,0.9642,0.5918,0.8548,0.2378,0.7044,0.3613,0.3546,0.7245,0.1395,
0.3013,0.7603,0.6807,0.4790,0.5274,0.5753,0.5913,0.7842,0.7047,0.0046,
0.7280,0.1401,0.7544,0.9976,0.9663,0.9055,0.1197,0.6062,0.3449,0.2764,
0.1576,0.9341,0.2467,0.9397,0.5725,0.4455,0.1576,0.1688,0.8072,0.6484,
0.1312,0.4551,0.7301,0.7475,0.5672,0.4251,0.4549,0.5841,0.6254,0.8034,
0.3391,0.5094,0.1777,0.2737,0.1770,0.9744,0.7284,0.3375,0.6030,0.0233,
0.2217,0.9446,0.2359,0.0880,0.3806,0.6287,0.0250,0.1781,0.5970,0.9682,
0.1642,0.1732,1.0000,0.0023,0.1967,0.8547,0.0906,0.0592,0.1128,0.3676,
0.0056,0.1447,0.3684,0.0008,0.4763,0.5042,0.2806,0.1881,0.4037,0.4469,
0.0254,
Overall p-value after applying KStest on 231 p-values = 0.023458
Fig. 4: DIEHARD v0.2 beta test suite applied on
the first 100 Mb random bits made by FRAG PRNG.7
------------------------------------------------------------------------------
RESULTS
FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
------------------------------------------------------------------------------
C1
C2 C3 C4
C5 C6 C7
C8 C9 C10 P-VALUE
PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
216
112 90
84 93 86
79 76 83
81 0.000000 * 0.9500 * frequency
279 142
130 100 84 72
71 52 41
29 0.000000 * 0.9540 * block-frequency
244
145 94
80 89 95
82 74 61
36 0.000000 * 0.9500 * cumulative-sums
242 129
104 84 112 105 71
70 47 36
0.000000 * 0.9490 *
cumulative-sums
149
119 98
94 84 85
90 95 87
99 0.000043 * 0.9670 runs
.87 68 115 110 114 115 103 117 99
72 0.000402 0.9850
longest-run
90 95
114 95
99 103 114 82 105 103 0.428095
0.9860 rank
92 102
95 111 96 113 87 116 104
84 0.278461 0.9920
fft
115 116
110 102 99 111 91
96 81 79
0.065639 0.9820 nonperiodic-templates
118 97
90 99 104 99 87
105 114 87 0.342451
0.9770 nonperiodic-templates
106 97 105
96 119 102 98 87 98 92
0.645448 0.9880 nonperiodic-templates
99 120 113 115 107 77
94 98 81
96 0.036352 0.9860
nonperiodic-templates
98 108 117
87 81 99 103 105 112 90
0.233162 0.9910 nonperiodic-templates
108 101
115 93
79 101 90 93 113 107
0.244236 0.9850 nonperiodic-templates
117 102
101 102 120 94 90
92 99 83
0.220159 0.9860 nonperiodic-templates
109
114 94
97 94 81 107 116
98 90 0.257004
0.9890 nonperiodic-templates
111 111
119 90
99 104 94 80 109
83 0.084037 0.9790
nonperiodic-templates
98 104 104 102 112 90 89
100 92 109 0.788728
0.9930 nonperiodic-templates
96 102 102 120
85 101 108 85 107 94
0.331408 0.9910 nonperiodic-templates
92
99 93 95 101 122
96 86 107 109 0.378705
0.9800 nonperiodic-templates
100 96 100 109 102 102 100 95 116
80 0.548314 0.9820
nonperiodic-templates
107 90 104 117 111 101 93 102
80 95 0.308561
0.9900 nonperiodic-templates
91 108
85 92 128 101 108 91 95
101 0.125927 0.9940
nonperiodic-templates
90 105
89 100 109 93 106 98 99
111 0.800005 0.9920
nonperiodic-templates
100 104
114 94
98 102 89 108 103 88
0.745908 0.9870 nonperiodic-templates
101
110 96 106 95 102 106
95 97 92
0.957612 0.9900 nonperiodic-templates
96 114 111
97 99 92
97 97 98
99 0.890582 0.9890
nonperiodic-templates
114
112 99 107 95
92 94 87 93
107 0.552383 0.9840
nonperiodic-templates
100 98 115
92 105 84 106 98 102 100
0.721777 0.9910 nonperiodic-templates
93
97 80 99 110 112 102 113 90 104
0.357000 0.9930 nonperiodic-templates
84 94
104 85
90 111 111 103 115 103 0.263572 0.9920
nonperiodic-templates
102
105 88
98 83 120 120 89 105
90 0.087692 0.9900
nonperiodic-templates
92 108
97 115 95 106 104 94 102
87 0.691081 0.9970
nonperiodic-templates
74 108 108 108 100 103 95 100 107
97 0.383827 0.9920
nonperiodic-templates
95 89
103 105 103 79 98 97
120 111 0.234373 0.9910
nonperiodic-templates
109 83
84 99 85 117 110
98 102 113 0.116065 0.9830
nonperiodic-templates
108 101
105 100 102 87 94 105
98 100 0.952152 0.9880
nonperiodic-templates
93
99 97 102 112 100 100 104
101 92
0.968863 0.9920 nonperiodic-templates
108 92 94
107 98
91 95 103 112 100 0.854708
0.9860 nonperiodic-templates
97 120 104
90 96 98 99
104 103 89 0.645448
0.9860 nonperiodic-templates
104 103
112 89
92 117 97 95 102
89 0.532132 0.9900
nonperiodic-templates
91
95 92 87 99
102 96 120 108 110 0.415422
0.9910 nonperiodic-templates
97 93
100 110 109 112 90 93 86
110 0.506194 0.9840
nonperiodic-templates
95
96 99 116 90 91
100 100 109 104 0.763677 0.9890
nonperiodic-templates
115
102 83
96 108 108 111 92 91 94 0.380407
0.9930 nonperiodic-templates
98
94 96 99 107 102 101 108 101 94
0.989425 0.9860 nonperiodic-templates
101 100
102 109 102 105 108 76 88 109
0.366918 0.9900 nonperiodic-templates
82 103
99 99 115 102 96 98
107 99
0.705466 0.9940 nonperiodic-templates
99
85 81 104 90 112 110 104 104 111 0.275709
0.9860 nonperiodic-templates
114 96 102 104
92 106 94 100 100 92
0.889118 0.9840 nonperiodic-templates
105 91 93
101 99 109 98 94
100 110 0.925287 0.9870
nonperiodic-templates
108 85 80
129 101 103 98 99 95
102 0.072514 0.9830
nonperiodic-templates
111 98 96
101 105 104 108 91 90 96 0.880145
0.9860 nonperiodic-templates
112
103 94 104 84 99
111 103 99 91
0.664168 0.9900 nonperiodic-templates
99 104 108 101 101 106 96
94 96 95
0.989425 0.9950 nonperiodic-templates
107 85
96 86 105 112 100 99 105 105
0.630872 0.9840 nonperiodic-templates
112 89 112
93 119 85 91 101 117
81 0.038062 0.9870
nonperiodic-templates
102 96
94 98 87 115
99 106 104 99 0.827279
0.9880 nonperiodic-templates
110
117 76
86 108 97 100 99 102 105
0.179584 0.9890 nonperiodic-templates
121 98 97
114 101 104 113 88 85
79 0.057875 0.9860
nonperiodic-templates
91
97 97 96 81
107 118 104 110 99 0.378705
0.9940 nonperiodic-templates
105 92 87
102 95 107 103 103 104 102 0.927677
0.9870 nonperiodic-templates
101 92 113 112
93 96 96 93
109 95
0.725829 0.9940 nonperiodic-templates
110 97 110
96 96 105 103 102 104 77
0.510153 0.9830 nonperiodic-templates
112 95
90 92 92 102 109 106 103 99
0.809249 0.9910 nonperiodic-templates
98 95
101 106 109 98 93 102 112
86 0.794391 0.9850
nonperiodic-templates
115 86 88
103 112 112 103 92 95 94 0.353733
0.9920 nonperiodic-templates
115
104 95 100 89 110
95 94 93 105
0.717714 0.9860 nonperiodic-templates
108 84 115
84 101 105 91 101 110 101 0.342451
0.9930 nonperiodic-templates
100 95
97 95 99 110
91 100 100 113 0.904708 0.9920
nonperiodic-templates
106 99 99
102 105 100 92 107 93 97 0.983938
0.9900 nonperiodic-templates
104 105
106 93
87 102 106 111 87 99
0.713641 0.9950 nonperiodic-templates
104
107 96
87 93 109 99 103
99 103 0.911413 0.9900
nonperiodic-templates
94 105
84 115 110 97 97 96
102 100 0.657933 0.9910
nonperiodic-templates
93 106 106
85 118 93 88 108 107
96 0.357000 0.9920
nonperiodic-templates
118
110 98 102 101 90 116
86 92 87
0.203351 0.9880 nonperiodic-templates
118 89
96 92 107 109 94
94 89 112 0.357000
0.9870 nonperiodic-templates
98 97
107 113 98 85 103 105 100 94
0.807412 0.9850 nonperiodic-templates
96
91 94 104 95 102 116 114 97
91 0.616305 0.9920
nonperiodic-templates
124 88 107 103
95 95 114 83 114
77 0.015707 0.9830
nonperiodic-templates
105 111
104 101 99 89 106
97 92 96
0.904708 0.9850 nonperiodic-templates
134
118 99 102 91 106 103
92 83 72
0.001165 0.9860 nonperiodic-templates
114 118
108 107 96 110 93
94 82 78
0.058612 0.9820 nonperiodic-templates
127 115
107 98 103 98
90 79 78 105
0.014051 0.9880 nonperiodic-templates
113
108 96
86 102 123 113 85 89 85 0.045971
0.9830 nonperiodic-templates
112 99
95 99 97
95 96 112 96
99 0.922855 0.9790
nonperiodic-templates
102
108 87
95 105 103 112 100 106 82 0.534146
0.9850 nonperiodic-templates
102 99
79 82 106 101 115 112 100
104 0.217857 0.9890
nonperiodic-templates
125 97 92
100 103 94 104 101 97 87 0.402962
0.9850 nonperiodic-templates
103 111
100 102 100 87 109 94
98 96 0.883171
0.9860 nonperiodic-templates
102 89 90
108 95 104 105 104 104 99
0.919131 0.9860 nonperiodic-templates
93 118
93 97 98
97 97 102 105 100 0.849708
0.9900 nonperiodic-templates
102 94 110 101 102 88 107
96 107 93 0.873987
0.9960 nonperiodic-templates
89 105 117 108
88 89 107 99 88
110 0.305599 0.9940
nonperiodic-templates
104 87 98
107 108 98 108 98 88
104 0.803720 0.9900
nonperiodic-templates
90
98 84 104 111 89 104 105 110 105 0.550347
0.9860 nonperiodic-templates
91 111 104
98 117 104 106 80 90 99 0.301194
0.9900 nonperiodic-templates
95
93 87 100 98 101 112
98 111 105 0.796268 0.9880
nonperiodic-templates
93 93
108 99 115 91 83
106 102 110 0.439122 0.9900
nonperiodic-templates
109
109 83 101 95 100 106 108 95
94 0.701366 0.9890
nonperiodic-templates
112 109
110 111 92 101 80 107
89 89 0.212184
0.9870 nonperiodic-templates
95 118
96 100 99 110 102 92 93 95
0.731886 0.9890 nonperiodic-templates
105 93 95
105 92
99 107 115 106 83 0.546283
0.9880 nonperiodic-templates
120 85 83
101 90 104 108 99 109 101
0.225998 0.9870 nonperiodic-templates
112
109 92 104 111 109 79
87 99 98
0.260930 0.9860 nonperiodic-templates
110
105 94 100 98 102
95 96 101 99
0.989425 0.9860 nonperiodic-templates
100 101
101 89 107 95 114 107 100 86
0.701366 0.9910 nonperiodic-templates
99 104 104 102
96 101 109 92 96 97 0.987079
0.9870 nonperiodic-templates
105
110 82 101 93 114
91 92 98 114
0.319084 0.9860 nonperiodic-templates
120 94 103
86 118 103 81 93 98
104 0.120909 0.9930
nonperiodic-templates
108 72 118
92 122 106 96 104 94 88 0.019993
0.9770 nonperiodic-templates
82 111
93 113 97 86 102 115 102 99
0.274341 0.9920 nonperiodic-templates
111
100 96 117 89
89 88 119 100 91
0.184549 0.9850 nonperiodic-templates
97 104 108 116 111 104 89
93 91 87
0.435430 0.9880 nonperiodic-templates
118 84 111 103 108 105 84 80
114 93
0.048716 0.9840 nonperiodic-templates
99 104 103 100
90 114 108 92 78 112
0.291091 0.9900 nonperiodic-templates
113 75 100
93 95 96 101 100 106 121 0.136499
0.9900 nonperiodic-templates
93 116
96 87 95 99
101 104 105 104 0.765632 0.9890
nonperiodic-templates
108 92 110 105 110 92 99
107 98
79 0.426272 0.9860
nonperiodic-templates
108 92 110
94 105 99 104 103 81 104
0.645448 0.9870 nonperiodic-templates
95 101 108 105 110 90 97
112 82 100 0.542228
0.9870 nonperiodic-templates
99 107
94 118 109 77 98 90
101 107 0.228367 0.9960
nonperiodic-templates
98
84 96 110 103 94 95
121 115 84 0.134172
0.9950 nonperiodic-templates
91 100 101 125 109 89
99 93 99 94 0.353733
0.9890 nonperiodic-templates
96 113
92 110 97 84 103 102 114 89
0.397688 0.9870 nonperiodic-templates
114 96 105
89 95 101 101 87 105 107
0.711601 0.9870 nonperiodic-templates
99 118 110
76 101 114 100 84 95 103
0.094285 0.9870 nonperiodic-templates
107 104
104 101 81 89 101 111 112 90
0.410055 0.9930 nonperiodic-templates
105
102 83 104 114 95 98
105 96
98 0.735908 0.9860
nonperiodic-templates
100
110 99
92 102 95 106 109 96
91 0.906069 0.9890
nonperiodic-templates
97 109
94 100 101 100 102 98 100 99
0.998058 0.9880 nonperiodic-templates
88 101
96 86 112 95 104
94 119 105 0.380407 0.9900
nonperiodic-templates
95 114
87 104 114 103 93 108 87
95 0.420827 0.9870
nonperiodic-templates
101 96 127 103
93 101 98 90 86
105 0.255705 0.9900
nonperiodic-templates
88 103 101
93 100 109 93 96 106 111
0.829047 0.9880 nonperiodic-templates
95 96
113 95 114 121 89 103
78 96 0.090388
0.9860 nonperiodic-templates
97 107
87 100 107 99 103 87 123
90 0.286836 0.9900
nonperiodic-templates
93
97 96 103 115 118 105 90 94 89
0.424453 0.9870 nonperiodic-templates
98 90
111 109 113 99 85 102
99 94 0.593478
0.9940 nonperiodic-templates
113 109
100 103 93 117 94
87 93 91
0.408275 0.9820 nonperiodic-templates
104
101 84 117 118 101 93
87 93 102 0.238035
0.9860 nonperiodic-templates
106 91 92
110 109 96 97 100 111
88 0.686955 0.9810
nonperiodic-templates
104 94 92
101 113 99 108 103 82 104
0.637119 0.9890 nonperiodic-templates
129 92 104 100
87 104 81 114 92 97 0.043368
0.9840 nonperiodic-templates
104
102 97 101 115 85 84
106 107 99 0.512137
0.9880 nonperiodic-templates
98 87
106 103 120 102 86 95 115
88 0.206629 0.9870
nonperiodic-templates
117 94 104
92 95 90 90
106 107 105 0.595549 0.9900
nonperiodic-templates
115 97
97 90 111 112 89
98 92 99
0.536163 0.9860 nonperiodic-templates
108 86 110 109 109 95 98
102 97
86 0.574903 0.9900
nonperiodic-templates
94 81
103 115 82 105 99 115 108
98 0.174728 0.9910
nonperiodic-templates
106
120 72
97 105 89 105 99 115
92 0.050305 0.9800
nonperiodic-templates
122
116 81
99 102 95 96 89
107 93
0.134944 0.9810 nonperiodic-templates
105 95 84
107 110 116 93 105 97 88 0.402962
0.9860 nonperiodic-templates
103 101
109 106 99 108 106 81
92 95 0.660012
0.9950 nonperiodic-templates
131 99
93 81 107 114 90
98 95 92
0.034031 0.9810 nonperiodic-templates
135
116 98 106 91 105 103
91 82 73
0.001070 0.9860 nonperiodic-templates
113 95
98 90 84 101
96 119 102 102 0.401199 0.9920
overlapping-templates
124 101
100 91 104 111 101 75 102
91 0.089301 0.9860
universal
147
100 99
92 99 96 84
104 88
91 0.000999 0.9850
apen
3
3 2 6
6 3 4
7 5 5
0.689019 1.0000 random-excursions
1
3 8 5
3 7 3
4 4 6
0.311542 1.0000 random-excursions
4
3 4 6
6 4 5
6 3 3
0.911413 1.0000 random-excursions
6
6 4 4
3 2 4
5 5 5
0.911413 1.0000 random-excursions
6
6 5 2
5 6 2
3 6 3
0.637119 1.0000 random-excursions
2
2 7 3
4 12 1
5 4 4
0.006196 0.9773 random-excursions
2
5 5 5
3 6 3
7 6 2
0.585209 1.0000 random-excursions
5
8 3 4
7 6 2 3 5
1 0.242986 1.0000
random-excursions
4
5 4 3
2 3 6
4 10 3
0.213309 1.0000 random-excursions-variant
4
5 3 3
6 1 4
3 7 8
0.311542 1.0000 random-excursions-variant
2
6 4 6
5 2 6 1 8
4 0.242986 1.0000
random-excursions-variant
3
5 6 1
9 3 2
5 3 7
0.122325 1.0000 random-excursions-variant
1
5 8 2
1 5 7
4 5 6
0.141256 1.0000 random-excursions-variant
0
4 7 3
5 4 8
4 5 4
0.275709 1.0000 random-excursions-variant
1
1 7 4
4 5 10
6 4 2
0.035174 1.0000 random-excursions-variant
3
2 4 8
3 8 9
2 4 1
0.025193 1.0000 random-excursions-variant
4
7 2 1
4 7 3
4 7 5
0.311542 1.0000 random-excursions-variant
7
9 1 3
5 3 2
1 5 8
0.025193 1.0000 random-excursions-variant
6
5 9 4
3 3 4
4 1 5
0.311542 1.0000 random-excursions-variant
7 4 8
3 5 5
0 2 8
2 0.048716 1.0000
random-excursions-variant
6
7 6 4
6 4 3
5 2 1
0.437274 1.0000 random-excursions-variant
6
5 8 5
6 5 3
1 3 2
0.311542 1.0000 random-excursions-variant
5
3 6 10
5 4 6
2 1 2
0.066882 1.0000 random-excursions-variant
5
4 6 6
5 9 1
3 2 3
0.186566 1.0000 random-excursions-variant
7
1 9 7
2 2 2
5 5 4
0.057146 1.0000 random-excursions-variant
6
6 4 7
2 4 1
6 3 5
0.437274 1.0000 random-excursions-variant
149
122 94 107 100 84
81 90 91
82 0.000005 * 0.9740 serial
93 99
107 100 102 90 105 107 103 94
0.954930 0.9870 serial
91 93
101 104 103 104 104 98 98 104
0.989425 0.9900 linear-complexity
.15 7
7 8 5
8 7 12
6 8 0.340461
0.9759 lempel-ziv-compression
- - - - -
- - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - -
The
minimum pass rate for the random excursion (variant) test is approximately
0.945000
for a sample size = 44 binary sequences.
- - - - -
- - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - -
The
minimum pass rate for each statistical test with the exception of the random
excursion
(variant) test is approximately = 0.980561 for a sample size = 1000
binary
sequences.
- - - - -
- - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - -
Fig 5: The NIST Test Suite applied on the first 11
Mb random bits produced by FRAG PRNG.
3.
Discussion
In the development phase the extraction
of the raw chaos was continued until the DIEHARD v0.2 beta test suite was
passed for an 11 and 100 Mb output file.
In order to calculate how many random
bits the algorithm with a finite automaton can produce I take you on a
mathematical exercise. I postulate that one can do estimations how many random
bytes (Ytarget) can be extracted from all the factors under a
certain natural number (Xfactor) using the following approximation:
Theorema 3.1.: Ytarget
≈ cXfactora (3.1.)
Xfactor and Ytarget are taken from
Table 1.One can deduce the following linear regression relationship between the
10log() values (see Table 3).
|
10log(Xfactor) |
10log(Ytarget) |
|
3.692 |
4.0129 |
|
4.5335 |
5.01271 |
|
5.40389 |
6.020986 |
|
6.284274 |
7.0206386 |
|
7.1779158 |
8.02060249 |
|
Linear Regression Results |
|
|
Correlation Coefficient (R) |
0.99993 |
|
Intersection Y-axis (b) = 10log(c) |
-0.191396 (σ = 0.04449) |
|
Slope (a) |
1.14610 (σ = 0.007638) |
Table 3: The results of linear regression on the logarithms of the amount of random bytes produced by factoring all integers under a certain natural number are shown. (σ = Standard Deviation)
This mathematical intermezzo was all to
be able to calculate how many random bits the PASCAL and a future C
implementation of the algorithm can produce with the given software and
bitrate.limitations. For the PASCAL program there is a software limitation
since the used unsigned integer type is 32 bit. The signed 64 bit integer of my
PASCAL compiler cannot be used in a FOR TO DO loop, which is necessary several
times in my program. So I am stuck with 32 bit! Using the 232 – 1
for Cardinal as the absolute maximum for Xfactor in the regression
formula gives a Ytarget file of 70,621,883,623 bytes (66 Gb).
Because one can loop the PASCAL program when this number is reached the period
is
With the aid of non-linear regression
from DATAPLOT I found a model that accurately describes the bitrate (Zbitrate
in Mbits per second) versus Ytarget (in Mb) from the results
of measurements given in Table 1.
Zbitrate
= (A0/(A1+Ytarget0.5))+A2 (3.2.)
The parameters Ax are given
in Table 4
|
Parameter |
Value |
σ |
T |
|
A0 |
16.9530 |
0.8107 |
20.91 |
|
A1 |
3.92742 |
0.3261 |
12.04 |
|
A2 |
0.270595 |
0.02013 |
13.44 |
|
Residual σ |
0.1481233 |
||
|
Residual degrees of freedom |
3 |
||
Table 4: Parameters of the Bitrate
versus Target File Size model.
This model applies with a certainty of
greater than 99.9% because the value from the T-distribution for 3 degrees of
freedom is then 10.2. All parameters have an T value which is much larger than
10.2. Which means that with a probability of > 99.9% all parameters are
non-zero (H0 hypothesis that they are zero is rejected!).
Fig. 6: Bitrate versus
Target File Size of FRAG PRNG.
From the formula of the model and from
Fig. 6 you can clearly see that the curve has an asymptote at Zbitrate
= 0.270595 Mbits per second (σ = 0.02013).
4. Conclusions
I claim that my algorithm is a-periodic.
Proof comes from the fundamental theorem of Number Theory that says: All
natural numbers have unique combinations of prime factors:
N = p1a*p2b*p3c*……
N > 1 and a, b, c, …… > 0 (4.1.)
It can easily be understood that from
this uniqueness of the prime factors, and thus the divisor pairs as I
demonstrated in the Introduction paragraph, there is also a unique bit pattern
representing the divisor pairs of the natural numbers. This unique bit pattern
is the input for the extraction process. The output is then also unique. That
there is a need for extracting of these unique divisors comes from the fact
there is a bias in the bit pattern. This is the raw chaos. That there is raw
chaos or randomness in the sequence of divisors pairs is illustrated by the
fact that the first digit distribution obeys Benford’s and Zipf’s Law.10
Because FRAG goes consecutively from natural number to natural number, and
extracts each time the unique combination of the divisors, the algorithm has no
periodicity and so infinite capacity! I believe that the fundamental theorem of
Number Theory is proof enough for the theoretical infinite period of FRAG.
To my knowledge FRAG is the first algorithm that uses factorial
randomness and is also theoretical a-periodic. Irrational numbers like π
to have this property of a-periodicity.11 But this the first
non-irrational number based a-periodic Pseudo Random Number Generator. There
are also software PRNG’s mentioned in the literature with huge periods. Like
the linear recurrences modulo m add-with-carry
and subtract-with-borrow (22,521), GFSR and Twisted GFSR or Mersenne
Twister (219,937-1) and maximally equidistributed combined TGFSR
generators (2466 and 21,250)12
The PASCAL-implementation is only a
prototype. It is not optimized for bitrate. Writing factoring source code
especially for the purpose of this kind of RNG can do optimizations for speed.
One option is writing the algorithm in the Assembly language. My estimation is
with optimal factoring algorithm(s) in Assembly that the program will be 100
times faster.
The period for the PASCAL-implementation is 236 and for
a future C-implementation this will be about 2228.
FRAG passes 214 of 227 randomness tests. All 13 not passed test
are Chi based tests. But a genuine (P)RNG will sometimes fail for a Chi-square based
test like frequency, gap, differential etc. Because the confidence level
interval of 5% - 95% means that the probability is that one in 20 experiments
the chi-square value will be < 5% or > 95%. This remains true random
behavior. For 227 Chi-based tests a true (P)RNG will always fail 11 test as
mean if the suites are performed an infinite number of times. Entropy is also
linked to probability. But the fact that the DIEHARD shows only one p = 1 or 0
is my strongest argument that at least this 100 Mb and another 1 Gb sample is
truly random. Because the DIEHARD only fails big when there are more than six p
= 1 or 0.7
The bitrate for random target files ranging from 10 Kb to 1 Gb
lies between 5.614 - 0.7424 Mbits per second. But from the hyperbolic model
follows that the bitrate does not asymptotically goes to zero as the target
file size increases. So the decrease of the bitrate caused by factoring of
increasingly greater numbers is completely compensated by the fact that also
the amount of divisors per factored number increases, which are the input for
the extraction process. This leads to a non-zero asymptote of 0.270595 Mbits
per second (σ = 0.02013, T = 13.44) with a probability of > 99.9%. In
other words the bitrate becomes constant, as the target file size goes to
infinity, somewhere between 0.23 – 0.31 Mbits per second (95.5% probability
interval ≈ A2 ± 2σ). This is for FRAGPAS1.EXE, which uses
brute force factoring (trail divisions). It remains to be seen if advanced
factoring algorithms in combination with a large integer unit gives the same
non-zero asymptote. And maybe it is even higher than the 0.23 – 31 Mbits per
second range because the factoring is faster than trail divisions. If this is
the case then one can go very well beyond factoring 1060 numbers and
so the practical period is also beyond 2228. As a matter a fact it
is more near infinite because the greatest factored number is then only limited
by available memory of the finite automaton and not a bitrate of asymptotically
going to zero.
-o0o-
Notes
& References:
1) Ruiz S.M. ‘Applications
of Smarandache function, and prime and coprime functions’ American Research
Press Rehoboth (2002)
http://www.gallup.unm.edu/~smarandache/SMRuiz-eBook.pdf
2) Van der Galiën
J.G. ‘Are the prime numbers randomly distributed?’ Scientia Araneae Totius
Orbis 1.2. (2002)
http://www.satoconor.com/prime/prime.html
3) Walker J.
‘Ent: A pseudorandom number sequence test program’
http://www.fourmilab.ch/random
4) Random.org ‘Introduction to randomness and random numbers’
http://www.random.org/essay.html
5) Walker J.
‘HotBits: Genuine random numbers, generated by radioactive decay’
http://www.fourmilab.ch/hotbits
6) Knuth D. E.,
The art of computer programming Volume 2 / Seminumerical
algorithms,
7) Anonymous ‘DIEHARD battery of tests
of randomness v0.2 beta’
http://www.cs.hku.hk/~diehard/
8) Van der Galiën J.G. ‘Proposal for a new kind of randomness test
(RABENZI)’
SATOCONOR.COM 3.3. (2004)
http://www.satoconor.com/randomtest/randomtest.html
9) Personal
communication of Michael Scott, Shamus Software Ltd ‘Multiprecision Integer
and Rational
Arithmetic C/c++ Library M.I.R.A.C.L.’ (2004)
10) Van der
Galiën J.G. ‘Factorial randomness’ SATOCONOR.COM 2.3.
(2004)
http://www.satoconor.com/factor/factor.html
11) Van der Galiën J.G. ‘Testing the a-periodic randomness of
π’
SATOCONOR.COM 3.2. (2004)
http://www.satoconor.com/pirandom/pirandom.html
12) L'Ecuyer P. ‘Random number
generation’ Draft for a chapter of the forthcoming
handbook of computational statistics, Editors: J. E. Gentle,
Springer-Verlag (2004) http://random.mat.sbg.ac.at/literature/
13) NIST ‘Random number generation
and testing’ http://csrc.nist.gov/rng/