Introduction
Here is
proposed a floating point cryptographically secure pseudo random number
generator (csprng) on uniform distribution with the x values between zero and
one. It’s safe, fast, with a large period and good statistical randomness
quality. Algorithm, randomness, performance, periodicity,
cryptography and other issues, are explained
forward.
Algorithm
The
algorithm is: an=an-1-xn-1 and xn=FRAC(anxn-1+.5) better explained with a PowerBASIC CC5 implementation
on the next lines, that generate 16777216 pseudo random numbers (80bit).
|
FUNCTION
PBMAIN LOCAL m, n
AS LONG, a, x AS EXT FOR n=1 TO
134217728 STEP 262144 FOR m=1 TO
262144 STEP 8 a=a+x x=FRAC(a*x+.5) NEXT a=a*x NEXT END FUNCTION |
Randomness
Several
statistical tests done with George Marsaglia’s Diehard battery of tests, was
not find any 0.00000 or 1.00000, p-values. Comparative tests done with binary
files containing true random numbers generated by physical sources, such as
atmospheric noise from RANDOM.ORG, atomic
radiation from HotBits, and
chaotic source from LAVArnd, given
good results.
performance
The performance depends on hardware,
software, optimization, et al. Running the code above on Windows XP/SP3 / Intel
Centrino processor at 2.0 GHz, the algorithm generates 277000000 Bytes/sec
or 7.22 cycles/Byte. This
value can be improved if optimized and/or implemented in assembly language.
Periodicity
As an is incremented by xn-1, then xn must be different from xn-1. To explain
that, see this simple example: Take
two different small sets from the whole sequence with one repeated number on
each set, and n<m, as follows:
|
xn-2 0.234546748574634 xn-1 0.783564763234561 xn 0.674863564797320 xm-2 0.356464763212724 xm-1 0.783564763234561 xm 0.098743643223776 |
Let R the
repeated number (Red) on the sets. xn=FRAC(an*R+.5) the next number after R on the first set
(green), xm=FRAC(am*R+.5), the next number after R on the second set
(blue). To do xn=xm, must be an=am, and
that is impossible, because
an<am. In another way, If two
random numbers at different points in a long sequence were identical, then the
preceding and succeeding random numbers will be different. For a 64 bit
precision, and n=1 we have a period of 2^64. For n=2, a period of (2^64)*((2^64)-1). For
n=3, a period of (2^64)*((2^64)-1)^2. So, for (b)=bit precision and (n)
outcomes, the period is P=(2^b)*((2^b)-1)^(n-1) ~ 2^(64n). For example, for a
precision b=64 bit and n=1000, we have a period P=(2^64)*((2^64)-1)^999 ~ 2^64000.
Precision
This
algorithm can run in any floating point precision (IEEE 754), like
Single (32 bit), Double (64 bit), Long double (80
bit), Quadruple (128
bit), or High up to
precision(33219280 bit), if necessary.
Application
You can i.e.
get 10.000
decimal pseudo random numbers or i.e. pick a bet
on Euromillions game. In both, use the refresh button on your web browser, to
give new values. Bellow is showed a little example in JavaScript language,
that it’s the same code used in this site, to generate 10.000 pseudo random
numbers, with the initial seeds extracted from the new Date () function
|
<SCRIPT
LANGUAGE="JavaScript"> var seed=new
Date () var seed=
seed.getTime () var
seed=seed.toString(); var s=seed.length; var r="" for (u=0; u<s; u++) { var r=r+seed.charAt(s-u) } var x=eval( "." + r ) var a=x/3 for
(n=1; n<10001; n++) { var a=a+x var x=a*x+.5-Math.floor(a*x+.5) document.write(x +
"<BR>") } </SCRIPT> |
Cryptography
Combined
with (XOR), this
algorithm is safe for cryptography. If you want to try it, go to Alvo a small
application that encrypt/decrypt any kind of file.
|
|
|
/\|_\/() |
|
|
|
|
|
KEYNOTE.PS |
|
KODAKGALLERY_COMáSLIDESHOW.MHT |
|
LIVRO1.XLS |
|
LIVRO2.XLS |
|
MAKE.TXT |
|
MAKEWHAT.EXE |
|
MDYANKSE-1-06.2-TT.ZIP |
|
MELD.EXE |
|
MONKEY.PS |
|
MUNDIAL.XLS |
|
MWC1.PS |
|
O MEU TEMA
FAVORITO.THEME |
|
OGALLERY_SLIDESHOW.MHT |
|
PERCENTAGENS
DE PONTOS.XLS |
|
PONTO E
BANCA.XLS |
|
|
|
|
|
|
|
|
Conclusion
Simple
and elegant, tiny and fast this algorithm offers no difficulties on implementation,
in any system/platform or programming language. I believe it can be used with
various applications, for its statistical quality and encryption
safety. Criticism or suggestions, contact me.
RibeiroAlvo