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

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

                Qn = ((Qn-1   R) ⋅ P) mod M

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

             R mod 8 = 5
             P mod 8 = 3
             M =
2n  ≥ 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

Qn = ((Qn-1   R1) + (P ⋅ s) + (R2 + (P s))  mod M
   s = (s + 1 + (s ⋅ 23)) mod M

An unbiased complete Cycle Length of all Integers between 0 and 2n 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
                mod 2 = 1
             M = 2n  ≥ 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


Copyright (c) 2011, Karl-Uwe Frank
All rights reserved.


Redistribution and Use in source and binary Form of this Algorithm (pqRNG and/or pqRNGr2), with or without Modification, are permitted without a Fee for private, research, academic, or other non-commercial Purposes as long as the Copyright is mentioned as "Copyright (c) 2011, Karl-Uwe Frank". Any Use of this Algorithm by a Commercial Enterprise or in any Commercial Product requires a written Commercial Licence. Adverteam Ltd (UK) is granted the exclusive unlimited Worldwide Right to deal with all Commercial Issues regarding this Algorithm as selling Commercial Licences and collecting Royalty Fees. In Terms for Commercial Usage the Copyright on this Algorithm has been transferred to Adverteam Ltd. (UK), Company Registration No. 3542561, http://www.Adverteam.co.uk.

In any Form of Publication mentioning this Algorithm, one may give the Citation as:
© Karl-Uwe Frank, Adverteam Ltd. "pqRNG - an unbiased Random Number Generator with entire Cycle Length."
© Karl-Uwe Frank, Adverteam Ltd. "pqRNGr2 - an unbiased Random Number Generator with entire Cycle Length."

THIS ALGORITHM IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
First published: 2011-11-02, 14:20:23 GMT
Last update:     2011-12-12, 23:14:20 GMT