help/srandom

   1 NAME
   2     srandom - seed the Blum-Blum-Shub pseudo-random number generator
   3
   4 SYNOPSIS
   5     srandom([state])
   6     srandom(seed)
   7     srandom(seed, newn)
   8     srandom(seed, ip, iq, trials)
   9
  10 TYPES
  11     state       random state
  12     seed        integer
  13     newn        integer
  14     ip          integer
  15     iq          integer
  16     trails      integer
  17
  18     return      random state
  19
  20 DESCRIPTION
  21     Seed the pseudo-random number using the Blum-Blum-Shub generator.
  22
  23     There are two primary values contained inside generator state:
  24
  25         Blum modulus:
  26
  27                 A product of two primes.  Each prime is 3 mod 4.
  28
  29         Quadratic residue:
  30
  31                 Some integer squared modulo the Blum modulus.
  32
  33     Seeding the generator involves changing the Quadratic residue
  34     and in most cases the Blum modulus as well.
  35
  36     In addition to the two primary values values, an internal buffer of
  37     unused random output is kept.  When the generator is seeded, any
  38     buffered random output is tossed.
  39
  40     In each of the following cases, srandom returns the previous state
  41     of the generator.  Depending on what args are supplied, a new
  42     generator state is established.  The exception is the no-arg state.
  43
  44     0 args:                             srandom()
  45
  46         Returns the current generator state.  Unlike all of the other
  47         srandom calls, this call does not modify the generator, nor
  48         does it flush the internal bits.
  49
  50     1 arg (state arg):                  srandom(state)
  51
  52         sets the generator to 'state', where 'state' is a previous
  53         return of srandom().
  54
  55     1 arg (0 seed):                     srandom(0)
  56
  57         Sets the generator to the initial startup state.  This a
  58         call of srandom(0) will restore the generator to the state
  59         found when calc starts.
  60
  61     1 arg (seed >= 2^32):               srandom(21609139158123209^9+17)
  62
  63         The seed value is used to compute the new quadratic residue.
  64         The seed passed will be successively squared mod the Blum
  65         modulus until we get a smaller value (modulus wrap).  The
  66         calc resource file produces an equivalent effect:
  67
  68                 /* assume n is the current Blum modulus */
  69                 r = seed;
  70                 do {
  71                         last_r = r;
  72                         r = pmod(r, 2, n);
  73                 } while (r > last_r);
  74                 /* r is the new Quadratic residue */
  75
  76         In this form of srandom, the Blum modulus is not changed.
  77
  78         NOTE: [1,2^32) seed values and seed<0 values
  79               are reserved for future use.
  80
  81     2 args (seed, newn>=2^32):          srandom(seed, newn)
  82
  83         The newn value is used as the new Blum modulus.  This modulus
  84         is assumed to be a product of two primes that are both 3 mod
  85         4.  The newn value is not factored, it is only checked to see
  86         if it is 1 mod 4.
  87
  88         In this call form, newn value must be >= 2^32.
  89
  90         The seed arg is used to establish the initial quadratic value
  91         once newn has been made the Blum moduli.  The seed must
  92         be either 0 or >= 2^32.  If seed == 0, the initial quadratic
  93         residue used with srandom(0) is used with the new Blum moduli.
  94         If seed >= 2^32, then srandom(seed, newn) has the same effect as:
  95
  96                 srandom(0, newn);    /* set Blum modulus & def quad res */
  97                 srandom(seed);       /* set quadratic residue */
  98
  99         Use of newn values that are not the product of two 3 mod 4
 100         primes will result in a non-cryptographically strong generator.
 101         While the generator will produce values, their quality will
 102         be suspect.
 103
 104         The period of the generator determines how many bits will
 105         be produced before it repeats.  The period is determined
 106         by the Blum modulus.  Some newn values (that are a product
 107         of two 3 mod 4 primes) can produce a generator with a
 108         very short period making is useless for most applications.
 109
 110         When Blum modulus is p*q, the period of a generator is:
 111
 112             lcm(factors of p-1 and q-1)
 113
 114         One can construct a generator with a maximal period when 'p'
 115         and 'q' have the fewest possible factors in common.  The
 116         quickest way to select such primes is only use 'p' and 'q' when
 117         '(p-1)/2' and '(q-1)/2' are both primes.  Assuming that
 118         fp=(p-1)/2, fq=(q-1)/2, p and q are all primes 3 mod 4, the
 119         period of the generator is the longest possible:
 120
 121             lcm(factors of p-1 and q-1) == lcm(2,fp,2,fq) = 2*fp*fq = ~n/2
 122
 123         The following calc resource file:
 124
 125             /* find first Blum prime: p */
 126             fp = int((ip-1)/2);
 127             do {
 128                 do {
 129                     fp = nextcand(fp+2, 1, 0, 3, 4);
 130                     p = 2*fp+1;
 131                 } while (ptest(p, 1, 0) == 0);
 132             } while (ptest(p, trials) == 0 || ptest(fp, trials));
 133
 134             /* find second Blum prime: q */
 135             fq = int((iq-1)/2);
 136             do {
 137                 do {
 138                     fq = nextcand(fq+2, 1, 0, 3, 4);
 139                     q = 2*fq+1;
 140                 } while (ptest(q, 1, 0) == 0);
 141             } while (ptest(q, trials) == 0 || ptest(fq, trials));
 142
 143             /* seed the generator */
 144             srandom(ir, p*q);
 145
 146         Where:
 147             ip
 148                 initial search location for the Blum prime 'p'
 149             iq
 150                 initial search location for the Blum prime 'q'
 151             ir
 152                 initial Blum quadratic residue generator.  The 'ir'
 153                 must be 0 or >= 2^32, preferably large some random
 154                 value < p*q.  The following may be useful to set ir:
 155
 156                         srand(p+q);
 157                         ir = randbit(highbit(p)+highbit(q))
 158             trials
 159                 number of pseudo prime tests that a candidate must pass
 160                 before being considered a probable prime (must be >0, try 25)
 161
 162         The calc standard resource file seedrandom.cal will produce a
 163         seed a generator.  If the config value custom("resource_debug")
 164         is 0 or 1, then the selected Blum modulus and quadratic residue
 165         will be printed.  If the global value is 1, then p and q are
 166         also printed.  The resource file defines the function:
 167
 168                 seedrandom(seed1, seed2, size [, trials])
 169
 170         Where:
 171             seed1
 172                 A random number >= 10^20 and perhaps < 10^93.
 173             seed2
 174                 A random number >= 10^20 and perhaps < 10^93.
 175             size
 176                 Minimal Blum modulus size in bits,  This must be >= 32.
 177                 A value of 512 might be a good choice.
 178             trials
 179                 number of pseudo prime tests that a candidate must pass
 180                 before being considered a probable prime (must be >0, try 25).
 181                 Using the default value of 25 might be a good choice.
 182
 183         Unfortunately finding optimal values can be very slow for large
 184         values of 'p' and 'q'.  On a 200Mhz r4k, it can take as long as
 185         1 minute at 512 bits, and 5 minutes at 1024 bits.
 186
 187         For the sake of speed, you may want to use to use one of the
 188         pre-compiled in Blum moduli via the [1
 189         If you don't want to use a pre-compiled in Blum moduli you can
 190         compute your own values ahead of time.  This can be done by a
 191         method of your own choosing, or by using the seedrandom.cal
 192         resource file in the following way:
 193
 194             1) calc                        # run calc
 195             2) read seedrandom             # load seedrandom
 196             3) config("resource_debug",0)  # we want the modulus & quad res only
 197             4) seedrandom( ~pound out 20-93 random digits on the keyboard~,
 198                            ~pound out 20-93 random digits on the keyboard~,
 199                            512 )
 200             5) save the seed and newn values for later use
 201
 202         NOTE: [1,2^32) seed values, seed<0 values, [21,2^32) newn values
 203               and newn<=0 values are reserved for future use.
 204
 205     2 args (seed, 1>=newn>=20):         srandom(seed, newn)
 206
 207         The newn is used to select one of 20 pre-computed Blum moduli.
 208
 209         The seed arg is used to establish the initial quadratic value
 210         once newn has been made the Blum moduli.  The seed must be
 211         either 0 or >= 2^32.  If seed == 0, the pre-compiled quadratic
 212         residue for the given newn is selected.  If seed >= 2^32, then
 213         srandom(seed, newn) has the same effect as:
 214
 215                 srandom(0, newn);    /* set Blum modulus & def quad res */
 216                 srandom(seed);       /* set quadratic residue */
 217
 218         Note that unlike the newn>=2^32 case, a seed if 0 uses the
 219         pre-compiled quadratic residue for the selected pre-compiled
 220         Blum moduli.
 221
 222         The pre-defined Blum moduli and quadratic residues were selected
 223         by LavaRnd, a hardware random number generator.  See the URL:
 224
 225             http://www.LavaRnd.org/
 226
 227         for an explanation of how the LavaRnd random number generator works.
 228         For more information, see the comments at the top of the calc
 229         source file, zrandom.c.
 230
 231         The purpose of these pre-defined Blum moduli is to provide users with
 232         an easy way to use a generator where the individual Blum primes used
 233         are not well known.  True, these values are in some way "MAGIC", on
 234         the other hand that is their purpose!  If this bothers you, don't
 235         use them.
 236
 237         The value 'newn' determines which pre-defined generator is used.
 238
 239             newn ==  1: (Blum modulus bit length 130)
 240             newn ==  2: (Blum modulus bit length 137)
 241             newn ==  3: (Blum modulus bit length 147)
 242             newn ==  4: (Blum modulus bit length 157)
 243             newn ==  5: (Blum modulus bit length 257)
 244             newn ==  6: (Blum modulus bit length 259)
 245             newn ==  7: (Blum modulus bit length 286)
 246             newn ==  8: (Blum modulus bit length 294)
 247             newn ==  9: (Blum modulus bit length 533)
 248             newn == 10: (Blum modulus bit length 537)
 249             newn == 11: (Blum modulus bit length 542)
 250             newn == 12: (Blum modulus bit length 549)
 251             newn == 13: (Blum modulus bit length 1048)
 252             newn == 14: (Blum modulus bit length 1054)
 253             newn == 15: (Blum modulus bit length 1055)
 254             newn == 16: (Blum modulus bit length 1062)
 255             newn == 17: (Blum modulus bit length 2062)
 256             newn == 18: (Blum modulus bit length 2074)
 257             newn == 19: (Blum modulus bit length 2133)
 258             newn == 20: (Blum modulus bit length 2166)
 259
 260         See the comments near the top of the source file, zrandom.c, for the
 261         actual pre-compiled values.
 262
 263         The Blum moduli associated with 1 <= newn < 9 are subject
 264         to having their Blum moduli factored, depending in their size,
 265         by small PCs in a reasonable to large supercomputers/highly
 266         parallel processors over a long time.  Their value lies in their
 267         speed relative the the default Blum generator.  As of Feb 1997,
 268         the Blum moduli associated with 13 <= newn < 20 appear to
 269         be well beyond the scope of hardware and algorithms,
 270         and 9 <= newn < 12 might be factorable with extreme difficulty.
 271
 272         The following table may be useful as a guide for how easy it
 273         is to factor the modulus:
 274
 275              1 <= newn <= 4   PC using ECM in a short amount of time
 276              5 <= newn <= 8   Workstation using MPQS in a short amount of time
 277              8 <= newn <= 12  High end supercomputer or high parallel processor
 278                               using state of the art factoring over a long time
 279             12 <= newn <= 16  Beyond Feb 1997 systems and factoring methods
 280             17 <= newn <= 20  Well beyond Feb 1997 systems and factoring methods
 281
 282         In other words, use of newn == 9, 10, 11 and 12 is likely to
 283         work just fine for all but the truly paranoid.
 284
 285         NOTE: [1,2^32) seed values, seed<0 values, [21,2^32) newn values
 286               and newn<=0 values are reserved for future use.
 287
 288     4 args (seed, ip>=2^16, iq>=2^16, trials):  srandom(seed, ip, iq, 25)
 289
 290         The 'ip' and 'iq' args are used to find simples prime 3 mod 4
 291
 292         The call srandom(seed, ip, iq, trials) has the same effect as:
 293
 294             srandom(seed,
 295                     nextcand(ip, trials,0, 3,4)*nextcand(iq, trials,0, 3,4));
 296
 297         Note that while the newn is very likely to be a product of
 298         two primes both 3 mod 4, there is no guarantee that the period
 299         of the generator will be long.  The likelihood is that the
 300         period will be long, however.  See one of the 2 arg srandom
 301         calls above for more information on this issue.
 302
 303         NOTE: [1,2^32) seed values, seed<0 values, [21,2^32) newn values,
 304               newn<=0 values, ip<2^16 and iq<2^16 are reserved for future use.
 305
 306     See the random help file for details on the generator.
 307
 308 EXAMPLE
 309     > srandom(0x8d2dcb2bed3212844f4ad31)
 310             RANDOM state
 311     > state = srandom();
 312     > print random(123), random(123), random(123), random(123), random(123)
 313     42 58 57 82 15
 314     > print random(123), random(123), random(123), random(123), random(123)
 315     90 121 109 114 80
 316     > state2 = srandom(state);
 317     > print random(123), random(123), random(123), random(123), random(123)
 318     42 58 57 82 15
 319     > print random(123), random(123), random(123), random(123), random(123)
 320     90 121 109 114 80
 321     > state3 = srandom();
 322     > print state3 == state2;
 323     1
 324     > print random();
 325     2101582493746841221
 326
 327 LIMITS
 328     integer seed == 0 or >= 2^32
 329     for newn >= 2^32: newn % 4 == 1
 330     for small newn: 1 <= newn <= 20
 331     ip >= 2^16
 332     iq >= 2^16
 333
 334 LINK LIBRARY
 335     RAND *zsrandom(ZVALUE *pseed, MATRIX *pmat55)
 336     RAND *zsetrandom(RAND *state)
 337
 338 SEE ALSO
 339     seed, srand, randbit, isrand, random, srandom, israndom
 340