"[...] on the day all combinations are exhausted, the result should remain secret, and in any case the universe will have completed its cycle - and we will all be consumed in the dazzling glory of the great Metacyclosynchrotron."

Umberto Eco, Foucault's Pendulum

## =======

Preface

=======

On March 13th, 1997, the idea of a generator for the calculation of pseudo-random numbers emerged. Inspired by Donald Knuth's algorithm P [1], the generator basically operates on permutations. In fact, no arithmetic operations are required, hence the name: naRND "non-arithmetic random". The algorithm is open source and is published under the 3-clause BSD license [2].

Due to variations in length and number of permutations used, naRND is more a family of generators than a single generator. Each generator derived from naRND is referred to as naPRNG "non-arithmetic pseudo-random number generator".

***Special note**

Random numbers are useful, often even necessary, e.g. for simulations, cryptography and statistics, to name but a few. Each of them requires special qualities. There is no theoretical proof that one of the naPRNGs described here satisfies one of these requirements.

Although theoretical studies are missing, many configurations of naRND passed the empirical tests including the BigCrush test battery [3] (see [Tests]->[TestU01]). In addition, the algorithm is very flexible and available as open source. In the hope that the algorithm is useful, this site publishes the documentation of the algorithm and of the test results, and provides downloading of source code, release version, random data samples and detailed test results.

Any feedback is very welcome!

## =============

Documentation

=============

### ---------

Algorithm

---------

Regardless of the fact that the current implementation is based on circularly linked nodes, it is easier to understand the algorithm implemented with arrays and index pointers. Accordingly, each naPRNG consists of

- a number of S arrays (S >= 1), denoted as "S-Box" (i.e. substitution box), each containing a permutation of R (R >= 2) items / references {0, 1, ..., R-1},
- two references, denoted "Last" and "Iterator" and
- a set of instructions how an iteration step is performed to obtain the next random item.

There are two operation modes V1 "Version 1" and V2 "Version 2", which affect the generation of the random items. In addition, two substitution modes "Strict" and "Loose" are defined. The operation modes are described in the following pseudocodes. The substitution mode is explained in the context of the implementation using nodes (see [Documentation]->[Pseudocode]->[Node-based]).

The values S := 4 and R := 256 were chosen as the standard for the number of substitution boxes and the number of items / references. Thus, in the strict mode, a substitution box is a permutation of exactly all the different values represented by one byte.

The notation for an naPRNG is defined as "naPRNG [OperationMode, SubstitutionMode] [NumberOfSubstitutionBoxes, NumberOfReferences]".

In 2007 it turned out that there is another generator that works similar to an naPRNG with a single S-Box. This generator is RC4 [4], designed by Ron Rivest in 1987. For a comparison of RC4 with the present algorithm, a generic version of ARC4 (Alleged RC4) was implemented (see [Documentation]->[Library]->[ARC4Test]) and systematically tested for period lengths (see [Tests]->[Periods]->[ARC4]).

***Special note**

If a particular state of the generator is known, all previous states can be recovered. For this reason, naRND is initially not suitable for cryptographic applications. The class naCrypt uses secure random numbers and the function GatherEntropy to compensate for this problem (see [Documentation]->[C# Library]->[naCrypt]).

Secure random numbers are only available in strict substitution mode, where the number of references is a power of 2. A secure random number is defined as the XOR of the values referenced by Last and Iterator.

### ----------

Pseudocode

----------

#### Standard V1

-----------

In the following pseudocode, one iterator is used for the S-Boxes and one for the items / references. As shown later, the node-based implementation requires only a single combined iterator. The initialization takes place in the example with the identity permutation.

Declaration: sbox[4][256]: 4 S-Boxes with 256 items / references each s: sbox Iterator | 0 <= s < 4 r: reference Iterator | 0 <= r < 256 l: Last reference z: output

Initialization: for i from 0 to 3 for j from 0 to 255 sbox[i][j] := j s := 0 r := 0 l := 255, l can not be chosen freely (*)

Iteration: swap sbox[s][r] and sbox[s][l] l := sbox[s][r] s := (s + 1) mod 4 if s equals 0 r := (r + 1) mod 256 z := sbox[s][r]

(*) Considering a combined Iterator (see [Documentation]->[Pseudocode]->[Node-based]), Last is the node which was referenced by the Iterators last position.

#### Standard V2

-----------

Declaration and initialization are identical to mode V1, but the value of l can be chosen freely (0 <= l < 256). The main difference to V1 is the assignment of the reference Last (l). Furthermore, as the test results of the BigCrush test battery [3] suggest, the assignment of z is adapted. In general, V1 seems to be the better choice (see [Tests]->[TestU01]):

Iteration: swap sbox[s][r] and sbox[s][l] l := sbox[s][l] s := (s + 1) mod 4 if s equals 0 r := (r + 1) mod 256 z := sbox[s][l]

#### Node-based

----------

As mentioned above, the node-based implementation does not require both iterators. The following figure shows the positions the combined iterator runs through, beginning with the upper left corner:

* __ __ __ ___ | | | | | | | | | S-Box[0]: 0 | 1 | 2 | ... | R-1 | | | | | | | | S-Box[1]: 0 | 1 | 2 | ... | R-1 | | | | | | | | ... . . . . . . ... . . | | | | | | | | S-Box[S-1]: 0 | 1 | 2 | ... | R-1 |__| |__| |__| |__| | *

A naNode "non-arithmetic node" is definde as a container which consists of

- a reference to the next naNode (i.e. iterating through the structure),
- a reference to a naNode on the same level (i.e. the same S-Box) as the next naNode and
- an item to be returned as the output.

The figure below shows the structure of such a node, where "i", "j" and "k" are the indices of the nodes:

Ni [next node Nj] [referenced node Nk] [item Zi]

For arrays, the elements of the S-Boxes act as index pointers (references) and output (items). For naNodes, the references are internal references to other naNodes, while the items are used exclusively for output. This seperates the concepts of references and items. If these items are the identity permutation of {0, 1, 2, ..., R-1}, the output is identical to the array-based implementation. This configuration is called "Strict", any other "Loose".

The naPRNG [V1, Strict] [2, 4] can be represented by 8 naNodes. When these nodes are arranged like the elements in the S-Boxes, the relationship between the two implementations becomes obvious. The figure below shows the generator initialized by the identity permutation:

N0 [N1] N2 [N3] N4 [N5] N6 [N7] [N1] [N3] [N5] [N7] [0] [1] [2] [3] N1 [N2] N3 [N4] N5 [N6] N7 [N0] [N0] [N2] [N4] [N6] [0] [1] [2] [3]

Let the Iterator be at the position of N0 and Last be equal to N6, then the current output is 0, the value of the node N1, which is referenced by Iterator. First, swap the references of Iterator, which points to N1, with the reference of Last, which points to N7. In the following step, set Last to the new reference of Iterator, which is now N7, while the Iterator itself is set to its next node N1. The output is again 0, the item of N0, referenced by the current Iterator.

In the following, naPRNGs are considered either as S-Boxes or as node structures. In strict substitution mode, both implementations are equivalent to each other. The application Tools (see [Documentation]->[Applications]->[Tools]) represents the configuration shown in the last example in a different and simpler way, which resembles rather an implementation with arrays than with nodes:

Identity -> Iteration 1 -> Iteration 2 S 0 1 2 3 3 1 2 0 S 3 1 2 0 0 1 2 3 S 0 1 2 3 3 1 2 0 R L R L R L

Here, "S" and "R" denote the position of the Iterator, while "S" and "L" represent the position of Last.

### ---------------

Recommendations

---------------

This chapter provides recommendations and limitations for the use of naPRNGs based on empirical tests and practical considerations.

#### Initialization

--------------

If all the S-Boxes of a generator represent the same permutation, the generator is in a state denoted as "Isostate". As the investigation of period lengths shows, generators initialized by such an Isostate generate longer period lengths on average (see [Tests]->[Periods]->[naRND]).

The initialization used in the pseudocodes applies the identity permutation for all the S-Boxes so that the generator is also in an Isostate. The first outputs of a generator initialized with the identity permutation tend not to be very random. It is recommended to discard the first S*R*R items. If a generator is randomly initialized, it is very likely that the period length is sufficient, but it is also possible to end with very short period lengths.

***Special note**

Every naPRNG has exactly one state which leads to a period length of S*R and corresponding quasi periods of length R. If S (S > 1) S-Boxes are assumed, the first S-1 S-Boxes of this special state represent the identity permutation. The elements of the last S-Box represent the identitiy permutation rotated one position to the left. The current state of Last and Iterator is not important in this context.

#### Dimensions

----------

The recommended values for the number of substitution boxes and references are S := 4 and R := 256. Presumably, larger values for R and S lead to longer periods and more random behaviour on the global scale (see [Tests]->[TestU01]), although there are exceptions when S is a fraction of R.

***Special note**

For generators of version V1 it is strongly recommended to select more than one S-Box. Otherwise the generator will show very short period lengths.

#### Substitution mode

-----------------

Generators in strict mode provide random values between 0 and R-1. What if, for example, a random stream of {"A", "C", "G", "T") ist to be generated? In fact, it is very easy to achieve this. Please note that the substitution mode of this type of generator is "Loose". In addition to the S-Boxes, the same set of arrays with the items to be returned must be passed as an argument during initialization. The algorithm does not need an additional step to return items instead of values because the values in strict mode are themselves items. The given example will look like this:

N0 [N1] N2 [N3] N4 [N5] N6 [N7] [N1] [N3] [N5] [N7] ["A"] ["C"] ["G"] ["T"] N1 [N2] N3 [N4] N5 [N6] N7 [N0] [N0] [N2] [N4] [N6] ["A"] ["C"] ["G"] ["T"]

According to the above example, the generator has 4 references per S-Box and thus a value of R of 4. This generator is quite poor due to its period length. To prevent this, simply set R to a multiple of 4. For example, if 12 references are chosen, each item must occur 3 times. If the distribution of the items is not proportional, the output will vary in the same way. Besides, it might also be appropriate to set different items for each S-Box.

### ----------

C# Library

----------

#### naRND

-----

This is the basic, generic class for the library. For specific purposes, it is likely to be more efficient to implement a native, customer-specific version of naRND, which is either based on nodes or arrays. The given implementation is based on nodes consisting of the essential elements (cf. [Documentation]->[Algorithm]->[Node-based]) as well as some additional elements as

- a total index of the node and
- a reference to the previous node.

The total index helps to identify the indices of the nodes Iterator and Last, which are needed for the visualization of the generators state and for test purposes. The reference to the previous node is used to speed up recovery of the previous state. In addition, the class contains an array with a reference to each node, e.g. for a faster and easier initialization process.

With the function GatherEntropy it is possible to influence the state of the generator by data that is passed as an argument.

#### naStrict

--------

With the class naStrict, which is derived from the class naRND, each naPRNG in strict substitution mode based on bytes can be generated. All naPRNGs used in the Applications (see [Documentation]->[Applications]) are derived from this class.

#### napRND

------

As the "p" indicates, this is the simulation of a parallel random number generator. This class represents only a first basic scheme. With arrays, a much more efficient implementation can be achieved.

#### naPool

------

naPool provides a static V2 standard generator providing bytes and integers with or without an upper bound as well as byte arrays. The Flush function saves the state to the hard disk drive. GatherEntropy is a function to influence the generators state by data passed as an argument.

#### naCrypt

-------

A standard V2 version generator that shows some of the capabilities of naPRNGs, such as creating permutations or secure random numbers. The application Crypt shows the usage of this class (see [Documentation]->[Applications]->[Crypt])

#### naTest

------

This is a special implementation for calculating the period and quasi-period lengths of naPRNGs with the application Period (see [Documentation]->[Applications]->[Period]).

#### naTools

-------

The naTools class provides some simple yet useful functions for initializing, storing, visualizing or testing naPRNGs.

#### ARC4Test

--------

This is a specific implementation of the Alleged RC4 Algorithm, which is used to compute its period lengths as compared to naRND (see [Documentation]->[Applications]->[Period]).

### ---------------

C# Applications

---------------

#### Tools

-----

With this application it is very easy to write random data to a file or to take a look at the internal state of a generator. The generator can be selected as naStrict, naTest, napRND, naPool, ARC4Test or the system generator. Depending on the selected generator, some initialization options, such as the number of S-Boxes and References, are displayed and can be modified. The binary output is available for all generators, as is the output as text on the screen. If the "State" option is available for output, the state can also be displayed on the screen and it is possible to save or load such a state.

#### Period

------

This application detects the period lengths for naPRNGs of both versions. The option "Verbose" takes into account all possible states, whereas otherwise only Isostates are considered. A computation can be cancelled, the intermediate configuration is stored, in order to continue later.

In addition to periods in the sequence of the original random numbers (z1, ..., zi), the program also recognizes "quasi-periods" in the sequence of the differences (d1, ..., di) between successive random numbers zi and zi+1, defined as di := |(zi - zi+1)|. A table of results as well as a file for download with all detailed results can be found here: [Tests]->[Periods].

#### Crypt

-----

An application for my private use and an implementation of some ideas. When the button with the logo is pressed, the option to collect entropy via mouse movements is offered.

***Special note**

Please make sure you back up your data before using this program. It is just a demonstrator. There is no proof that the application works properly in all cases. In addition, there is no evidence that the encryption used is sufficient for any purpose. Use at your own risk.

## =====

Tests

=====

### -------

Periods

-------

Many configurations have been systematically tested for period and quasi-period lengths (cf. [Documentation]->[Applications]->[Period]). The downloads contain detailed information.

#### naRND

-----

The following table shows the three smallest periods "Pi" and corresponding quasi-periods "Qi" for the configurations specified by the operation mode "V" {V1, V2}, the number of substitution boxes "S" and the number of references "R". Please note that generators of type V1 with only one S-Box are not considered as they should not be used at all (cf. [Documentation]->[Recommendations]->[Dimensions]):

V S R P1 Q1 P2 Q2 P3 Q3 -------------------------------------------------------------------------------- V1 2 2 4 2 12 6 - - 3 6 2 30 10 30 (30) 4 8 2 56 14 120 30 5 10 2 90 18 590 (590) 6 12 2 36 18 60 30 7 14 2 168 24 182 26 ----------------------------------------------------------------------- 3 2 6 3 42 21 - - 3 9 3 18 6 36 12 4 12 3 60 (60) 252 63 5 15 3 30 6 60 12 ----------------------------------------------------------------------- 4 2 8 4 120 60 - - 3 12 4 60 (60) 276 92 4 16 4 48 12 400 100 ----------------------------------------------------------------------- 5 2 10 5 30 15 70 35 3 15 5 30 10 60 (60) 4 20 5 60 (60) 140 35 -------------------------------------------------------------------------------- V2 1 2 2 1 6 3 - - 3 3 1 6 2 15 (15) 4 4 1 24 (24) 28 7 5 5 1 10 2 50 (50) 6 6 1 30 5 66 22 7 7 1 14 2 462 (462) 8 8 1 16 2 24 3 9 9 1 18 2 45 5 10 10 1 60 12 80 16 ----------------------------------------------------------------------- 2 2 4 2 28 14 - - 3 6 2 30 10 66 22 4 8 2 16 (16) 24 12 5 10 2 80 16 90 18 6 12 2 24 (24) 60 30 ----------------------------------------------------------------------- 3 2 6 3 30 15 - - 3 9 3 18 6 45 15 4 12 3 84 21 180 45 5 15 3 30 6 195 (195) ----------------------------------------------------------------------- 4 2 8 4 24 12 56 28 3 12 4 132 44 204 68 4 16 4 112 28 240 60 ----------------------------------------------------------------------- 5 2 10 5 630 315 - - 3 15 5 30 10 195 (195) 4 20 5 60 15 120 (120)

If only Isostates "Iso" are considered, the smallest related period lengths are much larger (cf. [Documentation]->[Recommendations]->[Initialization]):

V S R P1 (Iso) Q1 (Iso) ---------------------------------------------------- V1 2 2 12 6 3 30 10 4 56 14 5 90 18 6 132 22 7 182 26 ------------------------------------------- 3 2 42 21 3 36 12 4 60 (60) 5 2.357.385 471.477 ------------------------------------------- 4 2 120 60 3 276 92 4 21.392 5.348 ------------------------------------------- 5 2 30 15 3 19.230 (19.230) 4 439.940 109.985 ---------------------------------------------------- V2 2 2 28 14 3 30 10 4 16 (16) 5 280 (280) 6 1.572 786 ------------------------------------------- 3 2 30 15 3 45 15 4 708 177 5 86.280 (86.280) ------------------------------------------- 4 2 24 12 3 1.176 392 4 720 (720) ------------------------------------------- 5 2 630 315 3 195 (195) 4 99.580 (99.580)

#### ARC4

----

The algorithm of the alleged RC4 [4] was also systematically examined for period lengths. The results show a much more fragmented picture with small period lengths.

### -------

Diehard

-------

The standard generators of versions V1 and V2 were tested with the Diehard test battery [5]. Starting with the identity permutation, 10 chunks of 10 Mbyte each were tested. The program terminated with an error for the first chunk of the V2 version generator. The output used for V2 was the value referenced by Iterator (cf. [Documentation]->[Pseudocode]->[Standard V2]).

### -------

TestU01

-------

As one of the hardest tests, the BigCrush test battery [3] revealed some problems with the generators of version V2. The default output was the item referenced by the Iterator. It turned out that the use of the item referenced by Last leads to better results. Furthermore, generators with operation mode V1 generally appear to be the better choice.

#### Bytes

-----

The following table summarizes the test results obtained with the BigCrush test battery. "V" is the version / operation mode and "S" is the number of S-Boxes used. The number of references is set to R := 256, the substitution mode ist Strict. "Iter", "Last" and "Secure" indicate which output was taken as a random number (cf. [Documentation]->[Algorithm]). The entries indicate the number of failed tests. The entry "-" means that all tests were passed:

V S Iter Last Secure ------------------------------------------------ V1 2 error error error 3 - 2 - 4 - 4 1 5 - - - 6 - 1 - 7 - - - 8 - 2 - ------------------------------------------------ V2 1 17 4 1 2 9 3 2 3 5 - 1 4 4 - - 5 1 1 - 6 1 - - 7 - - - 8 2 - 3

#### Nibbles

-------

When using only 16 references, the results are as shown in the following table. An empty entry indicates that no test was applied for this configuration:

V S Iter Last Secure ------------------------------------------------ V1 4 42 5 17 6 18 7 2 8 23 ------------------------------------------------ V2 4 39 5 22 6 14 7 9 8 20

## =========

Downloads

=========

### ----------

C# Release

----------

This is the release version based on the latest C# Suite. The Microsoft .NET Framework 4 Client Profile [6] is required.

### --------

C# Suite

--------

The latest version of the source code, including the library (cf. [Documentation]->[C# Library]) and all applications (cf. [Documentation]->[C# Applications]).

There is also an older version available. Although the notation is different and many errors can be found, the implementation is based on arrays and is therefore retained as an illustrative material.

### --------

C Source

--------

This source code comes with many limitations, since the initial state is always the identity permutation. It was written to perform tests with TestU01 [3] (cf. [Tests]->[TestU01]).

### ----

Data

----

A binary file of the specified size is created for download. The standard generator naPRNG [V2, Strict] [4, 256] is used to generate the pseudo-random numbers. The output used is the value referenced by Iterator (cf. [Documentation]->[Pseudocode]->[Standard V2]).

## ==========

References

==========

- [1] Donald E. Knuth -> http://www-cs-faculty.stanford.edu/~uno/, The Art of Computer Programming, VOLUME 2 Seminumerical Algorithms, Third Edition (Addison-Wesley, 1998), xiv+762pp, Section 3.3.2
- [2] 3-clause BSD license -> https://en.wikipedia.org/wiki/BSD_licenses
- [3] P. L'Ecuyer and R. Simard, TestU01: A C Library for Empirical Testing of Random Number Generators, ACM Transactions on Mathematical Software, Vol. 33, 4, article 22, 2007 -> http://simul.iro.umontreal.ca/testu01/tu01.html
- [4] RC4 -> https://en.wikipedia.org/wiki/RC4
- [5] Diehard tests -> https://en.wikipedia.org/wiki/Diehard_tests
- [6] Download Microsoft .NET Framework 4 Client Profile -> http://www.microsoft.com/de-de/download/details.aspx?id=24872

## ==========

Disclaimer

==========

The content of our website has been compiled with meticulous care and to the best of our knowledge. However, we cannot assume any liability for the up-to-dateness, completeness or accuracy of any of the pages.

Our website contains links to the websites of third parties ("external links"). As the content of these websites is not under our control, we cannot assume any liability for such external content. In all cases, the provider of information of the linked websites is liable for the content and accuracy of the information provided. At the point in time when the links were placed, no infringements of the law were recognisable to us. As soon as an infringement of the law becomes known to us, we will immediately remove the link in question.