commit files needed for zpm-fetchurl

[zpackage] / tomsfastmath / src / numtheory / fp_prime_random_ex.c

diff --git a/tomsfastmath/src/numtheory/fp_prime_random_ex.c b/tomsfastmath/src/numtheory/fp_prime_random_ex.c
new file mode 100644 (file)
index 0000000..52b90e2
--- /dev/null
+++ b/tomsfastmath/src/numtheory/fp_prime_random_ex.c
@@ -0,0 +1,101 @@
+/* TomsFastMath, a fast ISO C bignum library.
+ *
+ * This project is meant to fill in where LibTomMath
+ * falls short.  That is speed ;-)
+ *
+ * This project is public domain and free for all purposes.
+ *
+ * Tom St Denis, tomstdenis@gmail.com
+ */
+#include <tfm_private.h>
+
+/* This is possibly the mother of all prime generation functions, muahahahahaha! */
+int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat)
+{
+   unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb;
+   int res, err, bsize, maskOR_msb_offset;
+
+   /* sanity check the input */
+   if (size <= 1 || cb == NULL || t <= 0 || t > FP_PRIME_SIZE) {
+      return FP_VAL;
+   }
+
+   /* TFM_PRIME_SAFE implies TFM_PRIME_BBS */
+   if (flags & TFM_PRIME_SAFE) {
+      flags |= TFM_PRIME_BBS;
+   }
+
+   /* calc the byte size */
+   bsize = (size>>3)+(size&7?1:0);
+
+   /* we need a buffer of bsize bytes */
+   tmp = malloc(bsize);
+   if (tmp == NULL) {
+      return FP_MEM;
+   }
+
+   /* calc the maskAND value for the MSbyte*/
+   maskAND = 0xFF >> ((8 - (size & 7)) & 7);
+
+   /* calc the maskOR_msb */
+   maskOR_msb        = 0;
+   maskOR_msb_offset = (size - 2) >> 3;
+   if (flags & TFM_PRIME_2MSB_ON) {
+      maskOR_msb     |= 1 << ((size - 2) & 7);
+   } else if (flags & TFM_PRIME_2MSB_OFF) {
+      maskAND        &= ~(1 << ((size - 2) & 7));
+   }
+
+   /* get the maskOR_lsb */
+   maskOR_lsb         = 1;
+   if (flags & TFM_PRIME_BBS) {
+      maskOR_lsb     |= 3;
+   }
+
+   do {
+      /* read the bytes */
+      if (cb(tmp, bsize, dat) != bsize) {
+         err = FP_VAL;
+         goto error;
+      }
+
+      /* work over the MSbyte */
+      tmp[0]    &= maskAND;
+      tmp[0]    |= 1 << ((size - 1) & 7);
+
+      /* mix in the maskORs */
+      tmp[maskOR_msb_offset]   |= maskOR_msb;
+      tmp[bsize-1]             |= maskOR_lsb;
+
+      /* read it in */
+      fp_read_unsigned_bin(a, tmp, bsize);
+
+      /* is it prime? */
+      res = fp_isprime_ex(a, t);
+      if (res == FP_NO) continue;
+
+      if (flags & TFM_PRIME_SAFE) {
+         /* see if (a-1)/2 is prime */
+         fp_sub_d(a, 1, a);
+         fp_div_2(a, a);
+
+         /* is it prime? */
+         res = fp_isprime_ex(a, t);
+      }
+   } while (res == FP_NO);
+
+   if (flags & TFM_PRIME_SAFE) {
+      /* restore a to the original value */
+      fp_mul_2(a, a);
+      fp_add_d(a, 1, a);
+   }
+
+   err = FP_OKAY;
+error:
+   free(tmp);
+   return err;
+}
+
+/* $Source$ */
+/* $Revision$ */
+/* $Date$ */