diff -P --exclude=conf* --exclude=Makefile.in -u -r ../gmp-4.0.orig/Makefile.am ./Makefile.am --- ../gmp-4.0.orig/Makefile.am Fri Nov 30 17:37:22 2001 +++ ./Makefile.am Mon Dec 10 16:44:59 2001 @@ -232,8 +232,8 @@ libgmp_la_SOURCES = gmp-impl.h longlong.h \ assert.c compat.c errno.c extract-dbl.c insert-dbl.c memory.c \ mp_bpl.c mp_clz_tab.c mp_minv_tab.c mp_set_fns.c \ - rand.c randclr.c randdef.c randlc.c randlc2s.c randlc2x.c randraw.c \ - rands.c randsd.c randsdui.c version.c + rand.c randclr.c randdef.c randlc.c randlc2s.c randlc2x.c randbbs.c \ + randraw.c rands.c randsd.c randsdui.c version.c libgmp_la_DEPENDENCIES = @TAL_OBJECT@ \ $(MPF_OBJECTS) $(MPZ_OBJECTS) $(MPN_OBJECTS) $(MPQ_OBJECTS) \ $(PRINTF_OBJECTS) $(SCANF_OBJECTS) diff -P --exclude=conf* --exclude=Makefile.in -u -r ../gmp-4.0.orig/gmp-h.in ./gmp-h.in --- ../gmp-4.0.orig/gmp-h.in Thu Nov 29 08:55:30 2001 +++ ./gmp-h.in Tue Dec 11 16:48:09 2001 @@ -219,7 +219,8 @@ typedef enum { GMP_RAND_ALG_DEFAULT = 0, - GMP_RAND_ALG_LC = GMP_RAND_ALG_DEFAULT /* Linear congruential. */ + GMP_RAND_ALG_LC = GMP_RAND_ALG_DEFAULT, /* Linear congruential. */ + GMP_RAND_ALG_BBS /* Blum Blum Shub. */ } gmp_randalg_t; /* Linear congruential data struct. */ @@ -230,6 +231,12 @@ unsigned long int _mp_m2exp; /* If != 0, modulus is 2 ^ m2exp. */ } __gmp_randata_lc; +/* Blum Blum Shub data struct. */ +typedef struct { + mpz_t _mp_m; /* Modulus. */ + unsigned long int _mp_k; /* Number of bits in modulus. */ +} __gmp_randata_bbs; + /* Random state struct. */ typedef struct { @@ -237,6 +244,7 @@ gmp_randalg_t _mp_alg; /* Algorithm used. */ union { /* Algorithm specific data. */ __gmp_randata_lc *_mp_lc; /* Linear congruential. */ + __gmp_randata_bbs *_mp_bbs; /* Blum Blum Shub. */ } _mp_algdata; } __gmp_randstate_struct; typedef __gmp_randstate_struct gmp_randstate_t[1]; @@ -415,6 +423,9 @@ #define gmp_randinit_lc_2exp_size __gmp_randinit_lc_2exp_size int __GMP_DECLSPEC gmp_randinit_lc_2exp_size _PROTO ((gmp_randstate_t, unsigned long)); +#define gmp_randinit_bbs __gmp_randinit_bbs +void __GMP_DECLSPEC gmp_randinit_bbs _PROTO ((gmp_randstate_t, mpz_srcptr)); + #define gmp_randseed __gmp_randseed void __GMP_DECLSPEC gmp_randseed _PROTO ((gmp_randstate_t, mpz_srcptr)); diff -P --exclude=conf* --exclude=Makefile.in -u -r ../gmp-4.0.orig/randbbs.c ./randbbs.c --- ../gmp-4.0.orig/randbbs.c Wed Dec 31 19:00:00 1969 +++ ./randbbs.c Tue Dec 11 17:23:52 2001 @@ -0,0 +1,59 @@ +/* gmp_randinit_bbs (state, m) -- Initialize a random state for a + Blum Blum Shub generator with modulus M. + +Copyright 2001 Free Software Foundation, Inc. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or (at your +option) any later version. + +The GNU MP Library 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. + +You should have received a copy of the GNU Lesser General Public License +along with the GNU MP Library; see the file COPYING.LIB. If not, write to +the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, +MA 02111-1307, USA. */ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" + +void +gmp_randinit_bbs (gmp_randstate_t rstate, + mpz_srcptr m) +{ + mp_ptr mp; + mp_size_t size; + unsigned int nbits; + + mpz_init_set_ui (rstate->_mp_seed, 4); + _mpz_realloc (rstate->_mp_seed, ABSIZ (m)); + + /* Allocate algorithm specific data. */ + rstate->_mp_algdata._mp_bbs = (__gmp_randata_bbs *) + (*__gmp_allocate_func) (sizeof (__gmp_randata_bbs)); + + mpz_init_set (rstate->_mp_algdata._mp_bbs->_mp_m, m); + + mp = PTR (m); + size = ABSIZ (m); + + ASSERT_ALWAYS ( (size > 1) || (size == 1 && *mp > 1 ) ); + + /* Count the bits in the modulus. */ + count_leading_zeros (nbits, mp[size - 1]); + nbits = size * BITS_PER_MP_LIMB - nbits; + + /* The number of valid bits is the log of the length. */ + for( rstate->_mp_algdata._mp_bbs->_mp_k = 0; nbits >>= 1; + rstate->_mp_algdata._mp_bbs->_mp_k++ ) + ; + + rstate->_mp_alg = GMP_RAND_ALG_BBS; +} diff -P --exclude=conf* --exclude=Makefile.in -u -r ../gmp-4.0.orig/randclr.c ./randclr.c --- ../gmp-4.0.orig/randclr.c Mon Jul 9 19:16:09 2001 +++ ./randclr.c Mon Dec 10 16:52:22 2001 @@ -36,12 +36,10 @@ (*__gmp_free_func) (rstate->_mp_algdata._mp_lc, sizeof (*rstate->_mp_algdata._mp_lc)); break; -#if 0 case GMP_RAND_ALG_BBS: - mpz_clear (rstate->algdata.bbs->bi); - (*__gmp_free_func) (rstate->algdata.bbs, sizeof (*rstate->algdata.bbs)); + mpz_clear (rstate->_mp_algdata._mp_bbs->_mp_m); + (*__gmp_free_func) (rstate->_mp_algdata._mp_bbs, sizeof (*rstate->_mp_algdata._mp_bbs)); break; -#endif /* 0 */ default: ASSERT (0); diff -P --exclude=conf* --exclude=Makefile.in -u -r ../gmp-4.0.orig/randraw.c ./randraw.c --- ../gmp-4.0.orig/randraw.c Mon Jul 9 19:19:23 2001 +++ ./randraw.c Tue Dec 11 18:26:32 2001 @@ -257,6 +257,30 @@ } #endif /* RAWRANDEBUG */ +/* bbs (rp, state) -- Generate next number in BBS sequence. Return the + number of valid bits in the result. */ + +static +unsigned long int +bbs (mp_ptr rp, gmp_randstate_t rstate) +{ + mp_size_t size; + mp_limb_t nbits; + + /* compute seed^2 mod m */ + mpz_powm_ui (rstate->_mp_seed, rstate->_mp_seed, 2, rstate->_mp_algdata._mp_bbs->_mp_m); + + /* Copy the low k bits to rp (k was computed when the modulus was set). */ + MPN_COPY (rp, PTR (rstate->_mp_seed), (rstate->_mp_algdata._mp_bbs->_mp_k + BITS_PER_MP_LIMB - 1) / BITS_PER_MP_LIMB); + + /* Mask off top bits if needed. */ + if (rstate->_mp_algdata._mp_bbs->_mp_k % BITS_PER_MP_LIMB != 0) + rp[rstate->_mp_algdata._mp_bbs->_mp_k / BITS_PER_MP_LIMB] + &= ~ ((~(mp_limb_t) 0) << rstate->_mp_algdata._mp_bbs->_mp_k % BITS_PER_MP_LIMB); + + return rstate->_mp_algdata._mp_bbs->_mp_k; +} + void _gmp_rand (mp_ptr rp, gmp_randstate_t rstate, unsigned long int nbits) { @@ -267,16 +291,17 @@ switch (rstate->_mp_alg) { case GMP_RAND_ALG_LC: + case GMP_RAND_ALG_BBS: { unsigned long int rbitpos; int chunk_nbits; mp_ptr tp; mp_size_t tn; - TMP_DECL (lcmark); + TMP_DECL (randmark); - TMP_MARK (lcmark); + TMP_MARK (randmark); - chunk_nbits = rstate->_mp_algdata._mp_lc->_mp_m2exp / 2; + chunk_nbits = rstate->_mp_alg == GMP_RAND_ALG_LC ? rstate->_mp_algdata._mp_lc->_mp_m2exp / 2 : rstate->_mp_algdata._mp_bbs->_mp_k; tn = (chunk_nbits + BITS_PER_MP_LIMB - 1) / BITS_PER_MP_LIMB; tp = (mp_ptr) TMP_ALLOC (tn * BYTES_PER_MP_LIMB); @@ -291,7 +316,10 @@ mp_limb_t savelimb, rcy; /* Target of of new chunk is not bit aligned. Use temp space and align things by shifting it up. */ - lc (tp, rstate); + if (rstate->_mp_alg == GMP_RAND_ALG_LC) + lc (tp, rstate); + else + bbs (tp, rstate); savelimb = r2p[0]; rcy = mpn_lshift (r2p, tp, tn, rbitpos % BITS_PER_MP_LIMB); r2p[0] |= savelimb; @@ -301,9 +329,12 @@ } else { - /* Target of of new chunk is bit aligned. Let `lc' put bits - directly into our target variable. */ - lc (r2p, rstate); + /* Target of of new chunk is bit aligned. Let `lc' or `bbs' + put bits directly into our target variable. */ + if (rstate->_mp_alg == GMP_RAND_ALG_LC) + lc (r2p, rstate); + else + bbs (r2p, rstate); } rbitpos += chunk_nbits; } @@ -314,7 +345,10 @@ mp_ptr r2p = rp + rbitpos / BITS_PER_MP_LIMB; int last_nbits = nbits - rbitpos; tn = (last_nbits + BITS_PER_MP_LIMB - 1) / BITS_PER_MP_LIMB; - lc (tp, rstate); + if (rstate->_mp_alg == GMP_RAND_ALG_LC) + lc (tp, rstate); + else + bbs (tp, rstate); if (rbitpos % BITS_PER_MP_LIMB != 0) { mp_limb_t savelimb, rcy; @@ -336,10 +370,10 @@ &= ~ ((~(mp_limb_t) 0) << nbits % BITS_PER_MP_LIMB); } - TMP_FREE (lcmark); + TMP_FREE (randmark); break; } - + default: ASSERT (0); break; diff -P --exclude=conf* --exclude=Makefile.in -u -r ../gmp-4.0.orig/randsd.c ./randsd.c --- ../gmp-4.0.orig/randsd.c Tue Dec 12 17:21:00 2000 +++ ./randsd.c Mon Dec 10 16:57:56 2001 @@ -27,5 +27,28 @@ gmp_randseed (gmp_randstate_t rstate, mpz_srcptr seed) { - mpz_set (rstate->_mp_seed, seed); + switch (rstate->_mp_alg) + { + case GMP_RAND_ALG_LC: + mpz_set (rstate->_mp_seed, seed); + break; + + case GMP_RAND_ALG_BBS: + { + mpz_t ztmp; + + mpz_set (rstate->_mp_seed, seed); + + /* Find a seed, x, with gcd (x, m) == 1. */ + mpz_init (ztmp); + while (1) + { + mpz_gcd (ztmp, rstate->_mp_seed, rstate->_mp_algdata._mp_bbs->_mp_m); + if (!mpz_cmp_ui (ztmp, 1)) + break; + mpz_add_ui (rstate->_mp_seed, rstate->_mp_seed, 1); + } + } + break; + } }