random

Calc Software Package for Number Calc

NAME
    random - Blum-Blum-Shub pseudo-random number generator

SYNOPSIS
    random([[min, ] max])

TYPES
    min		integer
    max		integer

    return	integer

DESCRIPTION
    Generate a pseudo-random number using a Blum-Blum-Shub generator.
    We return a pseudo-random number over the half closed interval [min,max).
    By default, min is 0 and max is 2^64.

    While the Blum-Blum-Shub generator is not painfully slow, it is not
    a fast generator.  For a faster, but lesser quality generator
    (non-cryptographically strong) see the additive 55 generator
    (see the rand help page).

    Other arg forms:

	random()	Same as rand(0, 2^64)
	random(max)	Same as rand(0, max)

    The random generator generates the highest order bit first.	 Thus:

	random(256)

    will produce the save value as:

	(random(8) << 5) + random(32)

    when seeded with the same seed.

    The basic idea behind the Blum-Blum-Shub generator is to use
    the low bit bits of quadratic residues modulo a product of
    two 3 mod 4 primes.	 The lowest int(log2(log2(p*q))) bits are used
    where log2() is log base 2 and p,q are two primes 3 mod 4.

    The Blum-Blum-Shub generator is described in the papers:

	Blum, Blum, and Shub, "Comparison of Two Pseudorandom Number
	Generators", in Chaum, D. et. al., "Advances in Cryptology:
	Proceedings Crypto 82", pp. 61-79, Plenum Press, 1983.

	Blum, Blum, and Shub, "A Simple Unpredictable Pseudo-Random
	Number Generator", SIAM Journal of Computing, v. 15, n. 2,
	1986, pp. 364-383.

	U. V. Vazirani and V. V. Vazirani, "Trapdoor Pseudo-Random
	Number Generators with Applications to Protocol Design",
	Proceedings of the 24th	 IEEE Symposium on the Foundations
	of Computer Science, 1983, pp. 23-30.

	U. V. Vazirani and V. V. Vazirani, "Efficient and Secure
	Pseudo-Random Number Generation", Proceedings of the 24th
	IEEE Symposium on the Foundations of Computer Science,
	1984, pp. 458-463.

	U. V. Vazirani and V. V. Vazirani, "Efficient and Secure
	Pseudo-Random Number Generation", Advances in Cryptology -
	Proceedings of CRYPTO '84, Berlin: Springer-Verlag, 1985,
	pp. 193-202.

	Sciences 28, pp. 270-299.

	Bruce Schneier, "Applied Cryptography", John Wiley & Sons,
	1st edition (1994), pp 365-366.

    This generator is considered 'strong' in that it passes all
    polynomial-time statistical tests.	The sequences produced are
    random in an absolutely precise way.  There is absolutely no better
    way to predict the sequence than by tossing a coin (as with TRULY
    random numbers) EVEN IF YOU KNOW THE MODULUS!  Furthermore, having
    a large chunk of output from the sequence does not help.  The BITS
    THAT FOLLOW OR PRECEDE A SEQUENCE ARE UNPREDICTABLE!

    Of course the Blum modulus should have a long period.  The default
    Blum modulus as well as the compiled in Blum moduli have very long
    periods.  When using your own Blum modulus, a little care is needed
    to avoid generators with very short periods.  See the srandom()
    help page for information for more details.

    To compromise the generator, an adversary must either factor the
    modulus or perform an exhaustive search just to determine the next
    (or previous) bit.	If we make the modulus hard to factor (such as
    the product of two large well chosen primes) breaking the sequence
    could be intractable for todays computers and methods.

    The Blum generator is the best generator in this package.  It
    produces a cryptographically strong pseudo-random bit sequence.
    Internally, a fixed number of bits are generated after each
    generator iteration.  Any unused bits are saved for the next call
    to the generator.  The Blum generator is not too slow, though
    seeding the generator via srandom(seed,plen,qlen) can be slow.
    Shortcuts and pre-defined generators have been provided for this
    reason.  Use of Blum should be more than acceptable for many
    applications.

    The goals of this package are:

	all magic numbers are explained

	    I distrust systems with constants (magic numbers) and tables
	    that have no justification (e.g., DES).  I believe that I have
	    done my best to justify all of the magic numbers used.

	 full documentation

	    You have this source file, plus background publications,
	    what more could you ask?

	large selection of seeds

	    Seeds are not limited to a small number of bits.  A seed
	    may be of any size.

	the strength of the generators may be tuned to meet the need

	    By using the appropriate seed and other arguments, one may
	    increase the strength of the generator to suit the need of
	    the application.  One does not have just a few levels.

    For a detailed discussion on seeds, see the srandom help page.

    It should be noted that the factors of the default Blum modulus
    is given in the source.  While this does not reduce the quality
    of the generator, knowing the factors of the Blum modulus would
    help someone determine the next or previous bit when they did
    not know the seed.	If this bothers you, feel free to use one
    of the other compiled in Blum moduli or provide your own. See
    the srandom help page for details.


EXAMPLE
    ; print srandom(0), random(), random(), random()
    RANDOM state 9203168135432720454 13391974640168007611 13954330032848846793

    ; print random(123), random(123), random(123), random(123), random(123)
    22 83 66 88 67

    ; print random(2,12), random(2^50,3^50), random(0,2), random(-400000,120000)
    10 483381144668580304003305 0 -70235

LIMITS
    min < max

LINK LIBRARY
    void zrandom(long cnt, ZVALUE *res)
    void zrandomrange(ZVALUE low, ZVALUE high, ZVALUE *res)
    long irandom(long max)

SEE ALSO
    seed, srand, randbit, isrand, rand, srandom, israndom

## Copyright (C) 1999  Landon Curt Noll
##
## Calc is open software; you can redistribute it and/or modify it under
## the terms of the version 2.1 of the GNU Lesser General Public License
## as published by the Free Software Foundation.
##
## Calc is distributed in the hope that it will be useful, but WITHOUT
## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
## or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
## Public License for more details.
##
## A copy of version 2.1 of the GNU Lesser General Public License is
## distributed with calc under the filename COPYING-LGPL.  You should have
## received a copy with calc; if not, write to Free Software Foundation, Inc.
## 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
##
## @(#) $Revision: 29.3 $
## @(#) $Id: random,v 29.3 2006/05/07 07:25:46 chongo Exp $
## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/random,v $
##
## Under source code control:	1997/02/17 01:18:22
## File existed as early as:	1997
##
## chongo <was here> /\oo/\	http://www.isthe.com/chongo/
## Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/