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

pqRNG (2011-11-02)

Pseudo Random Number Generator with unbiased entire Cycle Length of all Integers between 0 and 2n having 3 different Initialization Vectors

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

Mathematical Formula of pqRNG

                Q_n = ((Q_n-1 ⊕  R) ⋅ P) mod M

An unbiased complete Cycle Length of all Integers between 0 and 2ⁿ will be achieved if the following Conditions are complied

             R mod 8 = 5
             P mod 8 = 3
             M = 2ⁿ  ≥ 8

One Advantage of this Pseudo Random Number Generator is that we can feed it with 3 different random Values or Values of Choice for Q, P and R as IV (Initialization Vectors). Of course R and P have to be adjusted accordingly in order to gain the unbiased entire Cycle Length of M. Due to the mathematical relation between R and P the maximum Quantity of different Number Sequences pqRNG can generate will than count 2**(2*n-6) ^[1].

Below a short Example of one unbiased entire Cycle Length of M

Start IV (pqRNG)
Q = 0, P = 3, R = 13, M = 16

7, 14, 9, 12, 3, 10, 5, 8, 15, 6, 1, 4, 11, 2, 13, 0

The 32bit binary Output of pqRNG with M = 2147483647 over the Integer Interval [0, 255] passes quite remarkable all empirical and statistical Tests for Randomness as there are FIPS-140-1, Diehard Test Battery, Frequency-, Poker-, Runs-, Long-Runs and Serial-Test, also Monte Carlo Value of Pi, Arithmetic Mean, Serial Correlation Coefficient and obviously it generate a good Uniform Distribution of Zeros (0) and Ones (1).

Please find some Test Results and Download here.

Additionally an ANSI-C Source Code is avialable as of Today, which allows Anyone to verify that my Formula is working correctly in generating always all Integer Modulo 2^n in a full Cycle, in this Example Source Code all unsigned 16-bit Integer.

ANSI-C Source for pqRNG_full_Cycle_2^16_Test

Example Output: pqRNG_65536_full_Period Test

---

(2011-12-12)

This is the extended Algorithm of pqRNG named pqRNGr2

Q_n = ((Q_n-1 ⊕  R1) + (P ⋅ s) + (R2 + (P ⊕ s))  mod M
   s = (s + 1 + (s ⋅ 2³)) mod M

An unbiased complete Cycle Length of all Integers between 0 and 2ⁿ will be achieved if the following Conditions are complied

             P   mod 4 = 3
             R1 mod 8 = 5   or   R1 mod 8 = 7
             R2 mod 8 = 5   or   R2 mod 8 = 7
             s    mod 2 = 1
             M = 2ⁿ  ≥ 16

An ANSI-C Source Code is avialable which allows Anyone to verify that my Formula is working correctly in generating always all Integer Modulo 2^n in a full Cycle, in this Example Source Code all unsigned 16-bit Integer.

ANSI-C Source for pqRNGr2_full_Cycle_2^16_Test

Example Output: pqRNGr2_65536_full_Period Test

---

Annotation: This PRNG should not be considered cryptographically secure. If a cryptographically secure Keystream for Encryption is needed it should be considered to use two pqRNG and XOR the binary Output of each into a new Stream of Byte. In that Case of course the best Results are obtained if you seed both pqRNG with a Total of 6 different IV. ^[2]

---

⊕ represents the Bitwise XOR Calculation


Public Discussion about the Algorithm / Öffentliche Diskussion über den Algorithmus
The Crypto Forum (English Language) *
DevShed Forum (English language)        
Security Forums (English Language)
sci.stat.math (English Language)
sci.crypt.random-numbers (English language) *

de.comp.security.misc (German language)
Heise Forum (German language)



References
1. ↑ Correction of the maximum Quantity of different Number Sequences according to Maaartin G
2. ↑ Withdrawn because of a certain weakness against divide-and-conquer attack as mentioned by Greg Rose