mirror of
https://github.com/lcn2/calc.git
synced 2025-08-16 01:03:29 +03:00
db77e29a23
Converted all ASCII tabs to ASCII spaces using a 8 character tab stop, for all files, except for all Makefiles (plus rpm.mk). The `git diff -w` reports no changes.
182 lines
7.0 KiB
Plaintext
182 lines
7.0 KiB
Plaintext
NAME
|
|
random - Blum-Blum-Shub pseudo-random number generator
|
|
|
|
SYNOPSIS
|
|
random([[min, ] beyond])
|
|
|
|
TYPES
|
|
min integer
|
|
beyond 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,beyond) ((min <= return < beyond))
|
|
|
|
By default, min is 0 and beyond 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 subtractive 100 generator
|
|
(see the rand help page).
|
|
|
|
Other arg forms:
|
|
|
|
random() Same as random(0, 2^64)
|
|
random(beyond) Same as random(0, beyond)
|
|
|
|
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 < beyond
|
|
|
|
LINK LIBRARY
|
|
void zrandom(long cnt, ZVALUE *res)
|
|
void zrandomrange(ZVALUE low, ZVALUE beyond, ZVALUE *res)
|
|
long irandom(long beyond)
|
|
|
|
SEE ALSO
|
|
seed, srand, randbit, isrand, rand, srandom, israndom
|
|
|
|
## Copyright (C) 1999-2007,2021 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.
|
|
## 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
|
##
|
|
## 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/
|