Return to rand.c CVS log

Up to [local] / OpenXM_contrib / gmp

Annotation of OpenXM_contrib/gmp/rand.c, Revision 1.1.1.1

1.1       maekawa     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: }