"[...] 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.

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 [2] (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
---------

Although the current implementation is based on circularly linked nodes, it is easier to understand the algorithm implemented with arrays and index pointers. Each naPRNG consists of

There are two operation modes V1 "Version 1" and V2 "Version 2", with effect on 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 [3], 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 reproduced. 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 numbers referenced by Last and Iterator.

----------
Pseudocode
----------

Standard V1
-----------

In the following pseudocode, an 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 bis 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 assignemt of the reference Last (l). Furthermore, as the test results of the BigCrush test battery [2] suggest, the assignment of z is adapted, although V1 generally 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

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]

Using arrays, the elements of the S-Boxes work as index pointers (references) as well as for for output (items). For naNodes, the references are internal references to other naNodes, while the items are exclusively used 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, referenced by Iterator. Next step is to swap the references of Iterator N1 with N7, the reference of Last. Set Last to the new reference of Iterator N7 whilst the Iterator itself is set to its next node N1. The output again is 0, the item of N0, referenced by the current Iterator.

In the following, naPRNGs are considered either as S-Boxes or as node structures. Both implementations are equivalent to each other.

---------------
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 are the same permutation, the generator is in an 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 R. If S (S > 1) S-Boxes are assumed, the first S-1 S-Boxes 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]).

*Special note

For generators of version V1 it is strongly recommended to select more than 1 S-Box. Otherwise the generator shows 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 reproduced? In fact, it is very easy to achieve this. 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.

According to the above example, the generator has 4 items 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. With 12 references, each item must occur 3 times. If the distribution of the items is not proportional, the output will vary in the same way.

----------
C# Library
----------

naRND
-----

This is the basic, generic class for the library. The algorithm is based on nodes consisting of the essential elements (see [Documentation]->[Algorithm]->[Node-based]) as well as some additional elements as

The total index helps to identify the Iterator and Last index for a visualization of the state as for test purposes.

In addition, the class contains an array with a quick reference to each node. This is used to speed up initialization and to speed up the reproduction of the previous state.

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

naStrict
--------

With the class naStrict, each naPRNG can be generated in the strict substitution mode. All naPRNGs used in the C# Applications are derived from this class.

napRND
------

As the "p" indicates, this is the simulation of a parallel random number generator.

naPool
------

naPool provides a static V2 standard generator. The Flush function saves the state to the hard disk drive.

naCrypt
-------

A standard V2 version generator that shows some of the capabilities of naPRNGs, such as creating permutations or secure random numbers.

naTest
------

This is a special implementation for calculating the period lengths of naPRNGs.

naTools
-------

The naTools class provides some simple 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 length as compared to naRND.

---------------
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 or napRND in version V1 or V2, 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. The binary output is available for all generators, as is the output as text on the screen. When the "State" option is visible for output, the state is also displayed on the screen.

States can be opened or saved. Ensure that the appropriate generator is selected when a particular state is loaded.

Application Tools

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 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 number zi and zi+1, defined as di := |(zi - zi+1)|.

Application Period

Crypt
-----

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

*Special note

Please make sure you back up your data before using this program. It is just a demonstrator and it is not proven that it works properly in all cases and there is no evidence that the encryption is sufficient. Use at your own risk.

Application Crypt

=====
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 taken into account because they are not to 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 length 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)

Detailed results for period lengths, June 8th, 2016

ARC4
----

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

Detailed results for period lengths, March 1st, 2016

-------
Diehard
-------

The standard generators of versions V1 and V2 were tested with the Diehard test battery [4]. 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.

Detailed results for Diehard, February 24th, 2014

-------
TestU01
-------

As one of the hardest tests, the BigCrush test battery [2] 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. 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:

(Still running ...)

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

Detailed results for BigCrush on Bytes, February 24th, 2017

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:

(Still running ...)

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              

Detailed results for BigCrush on Nibbles, February 23rd, 2017

=========
Downloads
=========

----------
C# Release
----------

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

C# Release Version, February 17th, 2017

--------
C# Suite
--------

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

C# Suite, February 17th, 2017

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 retained as an illustrative material.

C# Suite, October 30th, 2013

--------
C Source
--------

This source code comes with many limitations since the initial state will always be the identity permutation. It was written to perform tests with TestU01 [2].

C Source for TestU01, February 14th, 2017

----
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.

Size: MByte

==========
References
==========

-----------------------------
References and external links
-----------------------------

==========
Disclaimer
==========

--------------------------------------------
Limitation of liability for internal content
--------------------------------------------

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.

------------------------------------------
Limitation of liability for external links
------------------------------------------

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.