Module Name: othersrc
Committed By: agc
Date: Mon Nov 23 05:56:01 UTC 2015
Update of /cvsroot/othersrc/external/bsd/ibbs
In directory ivanova.netbsd.org:/tmp/cvs-serv12751
Log Message:
Import an integer-based version of the Blum Blum Shub random number
generator into othersrc.
IBBS - Integer Blum Blum Shub Random Number Generator
=====================================================
This is a small Blum Blum Shub implementation which uses a Mersenne
Twister to take 4 bytes of entropy (retrieved from the microseconds
part of gettimeofday(2)), and generates 2 prime numbers and a seed from
this. Each prime number and seed is 16 bits. A deterministic prime
check is used to ensure we are dealing with safe/unsafe prime numbers.
Since 16 bits are used for the two primes, care is taken to avoid
cycles in the BBS output. If a cycle is detected, the generator is
re-seeded, and output starts again.
The RNG seems to be quite efficient, generating numbers at 10 MBps
on a NetBSD VM running in Fusion hosted on Mac OS X.
Blum Blum Shub
==============
More information can be found in:
https://en.wikipedia.org/wiki/Blum_Blum_Shub
In short, it's a simple, but slow (in theory), random number generator.
Time to generate random data
============================
% time ./ibbs -n 1000000000 -o 1.out
99.453u 1.379s 1:41.53 99.3% 0+0k 0+128io 0pf+0w
%
% bc
scale = 5
1000000000 / 101
9900990.09900
Looks like almost 10MB/s. Tests run on a NetBSD-7.99.21 VM running
under Fusion hosted on an early 2015 Mac Book Pro.
How random is it?
=================
For the dieharder tests, a file with 10^9 random bytes was generated
and handed to dieharder.
2 WEAK tests using dieharder-2 - these seem to vary in successive runs
of tests. 1 FAILED test using dieharder-2. Every test seems to fail
this test, though, so something is weird with it.
For dieharder-3, it's much easier to egrep output:
% grep PASSED dist/dieharder.out | wc -l
109
% egrep '(FAILED|WEAK)' dist/dieharder.out
marsaglia_tsang_gcd| 0| 10000000| 100|0.00374452| WEAK
sts_runs| 2| 100000| 100|0.99938591| WEAK
sts_serial| 12| 100000| 100|0.99799268| WEAK
rgb_lagged_sum| 29| 1000000| 100|0.00041886| WEAK
rgb_lagged_sum| 31| 1000000| 100|0.00000006|
FAILED
%
If you're worried about a random number generator failing these tests,
please note the p-value, and read the dieharder man page, specifically
the section on p-values.
Provenance
==========
The Mersenne Twister code comes from (the BSD-licensed):
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
and is used with thanks.
Inspiration for the BBS code came from Pate Williams, who wrote some
code based on multiple-precision numbers. However, ibbs has no
common code with that.
Reproducible Results
====================
The API has been structured so that it's possible to have multiple
ibbs generators in action at any one time. It's also possible to
seed the ibbs generator so that it produces reproducible results
(assuming the same seed is used, of course). Standard operation
will be to have differing results on each run if ibbs_srandom()
is not used.
I'd be really interested to hear other people's opinions on this code; I have
no idea how predictable this random number generator is - the focus was on
producing something which could be used earlier in the boot sequence, or on
smaller, embedded CPUs.
Status:
Vendor Tag: CROOKS
Release Tags: ibbs-base
N othersrc/external/bsd/ibbs/Makefile
N othersrc/external/bsd/ibbs/bin/Makefile
N othersrc/external/bsd/ibbs/dist/Makefile
N othersrc/external/bsd/ibbs/dist/dieharder.out
N othersrc/external/bsd/ibbs/dist/README
N othersrc/external/bsd/ibbs/dist/libibbs.3
N othersrc/external/bsd/ibbs/dist/ibbs.1
N othersrc/external/bsd/ibbs/dist/ibbs.c
N othersrc/external/bsd/ibbs/dist/ibbs.h
N othersrc/external/bsd/ibbs/dist/mersenne.h
N othersrc/external/bsd/ibbs/dist/main.c
N othersrc/external/bsd/ibbs/dist/mt19937ar.c
N othersrc/external/bsd/ibbs/dist/provenance
N othersrc/external/bsd/ibbs/lib/shlib_version
N othersrc/external/bsd/ibbs/lib/Makefile
No conflicts created by this import
