rts/gmp/rand.c

   1 /* gmp_randinit (state, algorithm, ...) -- Initialize a random state.
   2
   3 Copyright (C) 1999, 2000  Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 2.1 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
  19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20 MA 02111-1307, USA. */
  21
  22 #include <stdio.h> /* for NULL */
  23 #if __STDC__
  24 # include <stdarg.h>
  25 #else
  26 # include <varargs.h>
  27 #endif
  28
  29 #include "gmp.h"
  30 #include "gmp-impl.h"
  31
  32 /* Array of CL-schemes, ordered in increasing order of the first
  33    member (the 'm2exp' value).  The end of the array is indicated with
  34    an entry containing all zeros.  */
  35
  36 /* All multipliers are in the range 0.01*m and 0.99*m, and are
  37 congruent to 5 (mod 8).
  38 They all pass the spectral test with Vt >= 2^(30/t) and merit >= 1.
  39 (Up to and including 196 bits, merit is >= 3.)  */
  40
  41 struct __gmp_rand_lc_scheme_struct
  42 {
  43   unsigned long int m2exp;      /* Modulus is 2 ^ m2exp. */
  44   char *astr;                   /* Multiplier in string form. */
  45   unsigned long int c;          /* Adder. */
  46 };
  47
  48 struct __gmp_rand_lc_scheme_struct __gmp_rand_lc_scheme[] =
  49 {
  50   {32, "43840821",           1},
  51   {33, "85943917",           1},
  52   {34, "171799469",          1},
  53   {35, "343825285",          1},
  54   {36, "687285701",          1},
  55   {37, "1374564613",         1},
  56   {38, "2749193437",         1},
  57   {39, "5497652029",         1},
  58   {40, "10995212661",        1},
  59   {56, "47988680294711517",  1},
  60   {64, "13469374875402548381", 1},
  61   {100, "203786806069096950756900463357", 1},
  62   {128, "96573135900076068624591706046897650309", 1},
  63   {156, "43051576988660538262511726153887323360449035333", 1},
  64   {196, "1611627857640767981443524165616850972435303571524033586421", 1},
  65   {200, "491824250216153841876046962368396460896019632211283945747141", 1},
  66   {256, "79336254595106925775099152154558630917988041692672147726148065355845551082677", 1},
  67   {0, NULL, 0}                  /* End of array. */
  68 };
  69
  70 void
  71 #if __STDC__
  72 gmp_randinit (gmp_randstate_t rstate,
  73               gmp_randalg_t alg,
  74               ...)
  75 #else
  76 gmp_randinit (va_alist)
  77      va_dcl
  78 #endif
  79 {
  80   va_list ap;
  81 #if __STDC__
  82 #else
  83   __gmp_randstate_struct *rstate;
  84   gmp_randalg_t alg;
  85 #endif
  86
  87 #if __STDC__
  88   va_start (ap, alg);
  89 #else
  90   va_start (ap);
  91
  92   rstate = va_arg (ap, __gmp_randstate_struct *);
  93   alg = va_arg (ap, gmp_randalg_t);
  94 #endif
  95
  96   switch (alg)
  97     {
  98     case GMP_RAND_ALG_LC:       /* Linear congruential.  */
  99       {
 100         unsigned long int size;
 101         struct __gmp_rand_lc_scheme_struct *sp;
 102         mpz_t a;
 103
 104         size = va_arg (ap, unsigned long int);
 105
 106         /* Pick a scheme.  */
 107         for (sp = __gmp_rand_lc_scheme; sp->m2exp != 0; sp++)
 108           if (sp->m2exp / 2 >= size)
 109             break;
 110
 111         if (sp->m2exp == 0)     /* Nothing big enough found.  */
 112           {
 113             gmp_errno |= GMP_ERROR_INVALID_ARGUMENT;
 114             return;
 115           }
 116
 117         /* Install scheme.  */
 118         mpz_init_set_str (a, sp->astr, 0);
 119         gmp_randinit_lc_2exp (rstate, a, sp->c, sp->m2exp);
 120         mpz_clear (a);
 121         break;
 122       }
 123
 124 #if 0
 125     case GMP_RAND_ALG_BBS:      /* Blum, Blum, and Shub. */
 126       {
 127         mpz_t p, q;
 128         mpz_t ztmp;
 129
 130         /* FIXME: Generate p and q.  They must be ``large'' primes,
 131            congruent to 3 mod 4.  Should we ensure that they meet some
 132            of the criterias for being ``hard primes''?*/
 133
 134         /* These are around 128 bits. */
 135         mpz_init_set_str (p, "148028650191182616877187862194899201391", 10);
 136         mpz_init_set_str (q, "315270837425234199477225845240496832591", 10);
 137
 138         /* Allocate algorithm specific data. */
 139         rstate->data.bbs = (__gmp_rand_data_bbs *)
 140           (*_mp_allocate_func) (sizeof (__gmp_rand_data_bbs));
 141
 142         mpz_init (rstate->data.bbs->bi); /* The Blum integer. */
 143         mpz_mul (rstate->data.bbs->bi, p, q);
 144
 145         /* Find a seed, x, with gcd (x, bi) == 1. */
 146         mpz_init (ztmp);
 147         while (1)
 148           {
 149             mpz_gcd (ztmp, seed, rstate->data.bbs->bi);
 150             if (!mpz_cmp_ui (ztmp, 1))
 151               break;
 152             mpz_add_ui (seed, seed, 1);
 153           }
 154
 155         rstate->alg = alg;
 156         rstate->size = size;            /* FIXME: Remove. */
 157         mpz_set (rstate->seed, seed);
 158
 159         mpz_clear (p);
 160         mpz_clear (q);
 161         mpz_clear (ztmp);
 162         break;
 163       }
 164 #endif /* 0 */
 165
 166     default:                    /* Bad choice. */
 167       gmp_errno |= GMP_ERROR_UNSUPPORTED_ARGUMENT;
 168     }
 169
 170   va_end (ap);
 171 }