chiark - git - mdw - catacomb/blob - mprand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: mprand.c,v 1.1 1999/12/10 23:23:05 mdw Exp $
   4  *
   5  * Generate a random multiprecision integer
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mprand.c,v $
  33  * Revision 1.1  1999/12/10 23:23:05  mdw
  34  * Support for generating random large integers.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <mLib/alloc.h>
  41
  42 #include "grand.h"
  43 #include "mp.h"
  44 #include "mprand.h"
  45
  46 /*----- Main code ---------------------------------------------------------*/
  47
  48 /* --- @mprand@ --- *
  49  *
  50  * Arguments:   @mp *d@ = destination integer
  51  *              @unsigned b@ = number of bits
  52  *              @grand *r@ = pointer to random number source
  53  *              @mpw or@ = mask to OR with low-order bits
  54  *
  55  * Returns:     A random integer with the requested number of bits.
  56  *
  57  * Use:         Constructs an arbitrarily large pseudorandom integer.
  58  *              Assuming that the generator @r@ is good, the result is
  59  *              uniformly distributed in the interval %$[2^{b - 1}, 2^b)$%.
  60  *              The result is then ORred with the given @or@ value.  This
  61  *              will often be 1, to make the result odd.
  62  */
  63
  64 mp *mprand(mp *d, unsigned b, grand *r, mpw or)
  65 {
  66   size_t sz = (b + 7) / 8;
  67   octet *v = xmalloc(sz);
  68   unsigned m;
  69
  70   /* --- Fill buffer with random data --- */
  71
  72   r->ops->fill(r, v, sz);
  73
  74   /* --- Force into the correct range --- *
  75    *
  76    * This is slightly tricky.  Oh, well.
  77    */
  78
  79   b = (b - 1) % 8;
  80   m = (1 << b);
  81   v[0] = (v[0] & (m - 1)) | m;
  82
  83   /* --- Mask, load and return --- */
  84
  85   d = mp_loadb(d, v, sz);
  86   d->v[0] |= or;
  87   free(v);
  88   return (d);
  89 }
  90
  91 /*----- That's all, folks -------------------------------------------------*/