AnalyticBridge

A Data Science Central Community

New, state-of-the-art random number generator: simple, strong and fast

This article discusses a random number generator with an infinite period.

One of the best random sets of digits (extensively tested for randomness by hundreds of scientists using thousands of tests both in small and high dimensions) is the decimals of Pi. Despite its random character being superior to most algorithms currently implemented (current algorithms typically use recursive congruence relations or compositions of random permutations, and exhibit periodicity), decimals of Pi have two big challenges, making it useless as a random number generator:

If everybody knows that decimals of Pi are used in many high-security encryption algorithms (to generate undecipherable randomness) then guess what... it loses this very great "undecipherable-ness" property
Computing millions of decimals of Pi is very difficult, it takes a lot of time, much more time than traditional random number generation

Here is my answer to these two challenges, and as a result, a proposal for a new random number generator, which overcome these two difficulties:

Regarding speed, we have now extremely fast algoorithms to compute decimals of Pi, see for instance [1] and [2] below
Regarding using Pi, we should switch to much less popular numbers that can be computed via a very similar formula, in order to preserve speed and making reverse engineering impossible in encryption algorithms. An example of a fantastic random digit generator would be to use the digits of a number defined by formula [1], with a change like this: replace the numerators 4, -2, -1, -1 by 3, 1, -2, -2. You get the idea how trillions of random generators could be developed, using variations of formula [1].

Fast formulas to compute Pi:

[1] The formula,

$\pi = \sum_{k=0}^\infty \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right),$

is remarkable because it allows extracting any individual hexadecimal or binary digit of π without calculating all the preceding ones.

[2] The Chudnovsky brothers found in 1987 that

$\frac{426880 \sqrt{10005}}{\pi} = \sum_{k=0}^\infty \frac{(6k)! (13591409 + 545140134k)}{(3k)!(k!)^3 (-640320)^{3k}}\!$

which delivers 14 digits per term.

PS: this is a reply to the following article: Classical random number generators result in identity theft, according to IEEE, see http://www.analyticbridge.com/profiles/blogs/classical-random-numbe...

0 members like this

Comment

You need to be a member of AnalyticBridge to add comments!

Join AnalyticBridge

Comment by Jeffrey Strickland on October 19, 2014 at 10:05pm: I have one minor issue with some wording about random number generation. First, they are actually pseudo-random. Second, since infinity is not numerical, random number generators cannot achieve infinity. The can theoretically achieve the largest countable number, aleph-1, if we had the computational capacity to do so. I would just caution using infinity and random number generation in the same context. Though every number contains the concept of infinity, even 1.00000000..., infinity is not a number, we cannot count to it, and thus it is not possible to achieve the period computationally. Infinity is that which lies beyond the countable and uncountable.

Comment by Fabian Bastin on February 13, 2012 at 10:07pm: I forgot that for those who really want randomness, they can put quantum physics in their PC! http://www.idquantique.com/true-random-number-generator/quantis-usb...

A bit expensive, but...

Comment by Fabian Bastin on February 13, 2012 at 9:58pm: The first question for a random number generator is what is the purpose? If one is looking for statistical performance, for instance for simulation, very efficient generators (MRG or Mersenne-Twister) are known, and should be used. There are many statistical tests that can be used to evaluate them. TestU01 is a free software that implements dozens of them, and can identify bad generators (e.g. those proposed in Excel, VB, GNU Glibc,...). The IEEE article clearly do not address this (simulation) concern. If one is just looking for use in cryptography, the statistical properties are much less relevant, and the technique complexity is then more important. The important issue is not only to hide the seed, but also make the technique difficult to discover by an intruder. Modern generator have huge periods (the MT19935 has a period of 2^19937) so it is already virtually impossible to predict the number if one just had a small sequence. Combine different kind of generators, and the modern ones are fast (faster then the computer of pi decimals), and you have a very strong tool.

Comment by Vincent Granville on October 18, 2011 at 10:54am: Another idea: use continued fractions to approximate Pi. Let us denote by p(n) he n-th approximant: p(n) = A(n) / B(n), where A(n) and B(n) are integers defined by simple recurrence relations. Modify these recurrence relations very slightly, et voila: we created a new interesting number, with (hopefully) random digits.

Or consider a simple continued fraction such as

F = 1 / (1 + 1 / ( 1 + 2 / ( 1 + 3 / ( 1 + 4 / ( 1 + 5 / ( 1 + 6 / 1 + .. ) ) ) ) ) )

Despite the very strong pattern in the construction of F, I am sure that its digits show very good randomness properties.

Comment by Vincent Granville on September 13, 2011 at 3:53pm

It would be interesting to study the function F(a,b,c,d) defined by formula [1], by replacing the numbers 4, -2, -1, -1 (numerator) by a, b, c, d. Of course, F(4,-2,-1,-1) = Pi.

Do interesting numbers share the two properties listed below? Could the number e=2.71..(or some other beautiful numbers) be a special case of F?

AnalyticBridge

New, state-of-the-art random number generator: simple, strong and fast

You need to be a member of AnalyticBridge to add comments!

Resources

On Data Science Central