fp_prime_random_ex.c

00001 /* TomsFastMath, a fast ISO C bignum library.
00002  * 
00003  * This project is meant to fill in where LibTomMath
00004  * falls short.  That is speed ;-)
00005  *
00006  * This project is public domain and free for all purposes.
00007  * 
00008  * Tom St Denis, tomstdenis@gmail.com
00009  */
00010 #include <tfm.h>
00011 
00012 /* This is possibly the mother of all prime generation functions, muahahahahaha! */
00013 int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat)
00014 {
00015    unsigned maskAND, maskOR_msb, maskOR_lsb;
00016    int res, err, bsize, maskOR_msb_offset;
00017 
00018    /* sanity check the input */
00019    if (size <= 1 || t <= 0) {
00020       return FP_VAL;
00021    }
00022 
00023    /* TFM_PRIME_SAFE implies TFM_PRIME_BBS */
00024    if (flags & TFM_PRIME_SAFE) {
00025       flags |= TFM_PRIME_BBS;
00026    }
00027 
00028    /* calc the byte size */
00029    bsize = (size>>3)+(size&7?1:0);
00030 
00031    /* we need a buffer of bsize bytes */
00032 #if 0
00033    tmp = malloc(bsize);
00034    if (tmp == NULL) {
00035       return FP_MEM;
00036    }
00037 #endif
00038    //DG alloc on stack
00039    uint8_t tmp[bsize];
00040 
00041    /* calc the maskAND value for the MSbyte*/
00042    maskAND = 0xFF >> (8 - (size & 7));
00043 
00044    /* calc the maskOR_msb */
00045    maskOR_msb        = 0;
00046    maskOR_msb_offset = (size - 2) >> 3;
00047    if (flags & TFM_PRIME_2MSB_ON) {
00048       maskOR_msb     |= 1 << ((size - 2) & 7);
00049    } else if (flags & TFM_PRIME_2MSB_OFF) {
00050       maskAND        &= ~(1 << ((size - 2) & 7));
00051    }
00052 
00053    /* get the maskOR_lsb */
00054    maskOR_lsb         = 1;
00055    if (flags & TFM_PRIME_BBS) {
00056       maskOR_lsb     |= 3;
00057    }
00058 
00059    do {
00060       /* read the bytes */
00061       if (cb(tmp, bsize, dat) != bsize) {
00062          err = FP_VAL;
00063          goto error;
00064       }
00065  
00066       /* work over the MSbyte */
00067       tmp[0]    &= maskAND;
00068       tmp[0]    |= 1 << ((size - 1) & 7);
00069 
00070       /* mix in the maskORs */
00071       tmp[maskOR_msb_offset]   |= maskOR_msb;
00072       tmp[bsize-1]             |= maskOR_lsb;
00073 
00074       /* read it in */
00075       fp_read_unsigned_bin(a, tmp, bsize);
00076 
00077       /* is it prime? */
00078       res = fp_isprime(a);
00079       if (res == FP_NO) continue;
00080 
00081       if (flags & TFM_PRIME_SAFE) {
00082          /* see if (a-1)/2 is prime */
00083          fp_sub_d(a, 1, a);
00084          fp_div_2(a, a);
00085  
00086          /* is it prime? */
00087          res = fp_isprime(a);
00088       }
00089    } while (res == FP_NO);
00090 
00091    if (flags & TFM_PRIME_SAFE) {
00092       /* restore a to the original value */
00093       fp_mul_2(a, a);
00094       fp_add_d(a, 1, a);
00095    }
00096 
00097    err = FP_OKAY;
00098 error:
00099 #if 0
00100    free(tmp);
00101 #endif
00102    return err;
00103 }
00104 
00105 /* $Source: /cvs/libtom/tomsfastmath/src/numtheory/fp_prime_random_ex.c,v $ */
00106 /* $Revision: 1.1 $ */
00107 /* $Date: 2007/01/24 21:25:19 $ */