pd.if.org Git - zpackage/blob - tomsfastmath/src/numtheory/fp_prime_random_ex.c

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@gmail.com
   9  */
  10 #include <tfm_private.h>
  11
  12 /* This is possibly the mother of all prime generation functions, muahahahahaha! */
  13 int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat)
  14 {
  15    unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb;
  16    int res, err, bsize, maskOR_msb_offset;
  17
  18    /* sanity check the input */
  19    if (size <= 1 || cb == NULL || t <= 0 || t > FP_PRIME_SIZE) {
  20       return FP_VAL;
  21    }
  22
  23    /* TFM_PRIME_SAFE implies TFM_PRIME_BBS */
  24    if (flags & TFM_PRIME_SAFE) {
  25       flags |= TFM_PRIME_BBS;
  26    }
  27
  28    /* calc the byte size */
  29    bsize = (size>>3)+(size&7?1:0);
  30
  31    /* we need a buffer of bsize bytes */
  32    tmp = malloc(bsize);
  33    if (tmp == NULL) {
  34       return FP_MEM;
  35    }
  36
  37    /* calc the maskAND value for the MSbyte*/
  38    maskAND = 0xFF >> ((8 - (size & 7)) & 7);
  39
  40    /* calc the maskOR_msb */
  41    maskOR_msb        = 0;
  42    maskOR_msb_offset = (size - 2) >> 3;
  43    if (flags & TFM_PRIME_2MSB_ON) {
  44       maskOR_msb     |= 1 << ((size - 2) & 7);
  45    } else if (flags & TFM_PRIME_2MSB_OFF) {
  46       maskAND        &= ~(1 << ((size - 2) & 7));
  47    }
  48
  49    /* get the maskOR_lsb */
  50    maskOR_lsb         = 1;
  51    if (flags & TFM_PRIME_BBS) {
  52       maskOR_lsb     |= 3;
  53    }
  54
  55    do {
  56       /* read the bytes */
  57       if (cb(tmp, bsize, dat) != bsize) {
  58          err = FP_VAL;
  59          goto error;
  60       }
  61
  62       /* work over the MSbyte */
  63       tmp[0]    &= maskAND;
  64       tmp[0]    |= 1 << ((size - 1) & 7);
  65
  66       /* mix in the maskORs */
  67       tmp[maskOR_msb_offset]   |= maskOR_msb;
  68       tmp[bsize-1]             |= maskOR_lsb;
  69
  70       /* read it in */
  71       fp_read_unsigned_bin(a, tmp, bsize);
  72
  73       /* is it prime? */
  74       res = fp_isprime_ex(a, t);
  75       if (res == FP_NO) continue;
  76
  77       if (flags & TFM_PRIME_SAFE) {
  78          /* see if (a-1)/2 is prime */
  79          fp_sub_d(a, 1, a);
  80          fp_div_2(a, a);
  81
  82          /* is it prime? */
  83          res = fp_isprime_ex(a, t);
  84       }
  85    } while (res == FP_NO);
  86
  87    if (flags & TFM_PRIME_SAFE) {
  88       /* restore a to the original value */
  89       fp_mul_2(a, a);
  90       fp_add_d(a, 1, a);
  91    }
  92
  93    err = FP_OKAY;
  94 error:
  95    free(tmp);
  96    return err;
  97 }
  98
  99 /* $Source$ */
 100 /* $Revision$ */
 101 /* $Date$ */