Improved prime number test

3 files changed, 64 insertions, 0 deletions

diff --git a/mpi/mpi-div.c b/mpi/mpi-div.c
index 2b39cb4c..52737574 100644
--- a/mpi/mpi-div.c
+++ b/mpi/mpi-div.c
@@ -278,6 +278,37 @@ mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den)
 	mpi_free_limb_space(marker[--markidx]);
 }
 
+void
+mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count )
+{
+    mpi_size_t usize, wsize;
+    mpi_size_t limb_cnt;
+
+    usize = u->nlimbs;
+    limb_cnt = count / BITS_PER_MPI_LIMB;
+    wsize = usize - limb_cnt;
+    if( limb_cnt >= usize )
+	w->nlimbs = 0;
+    else {
+	mpi_ptr_t wp;
+	mpi_ptr_t up;
+
+	RESIZE_IF_NEEDED( w, wsize );
+	wp = w->d;
+	up = u->d;
+
+	count %= BITS_PER_MPI_LIMB;
+	if( count ) {
+	    mpihelp_rshift( wp, up + limb_cnt, wsize, count );
+	    wsize -= !wp[wsize - 1];
+	}
+	else {
+	    MPN_COPY_INCR( wp, up + limb_cnt, wsize);
+	}
+
+	w->nlimbs = wsize;
+    }
+}
 
 /****************
  * Check wether dividend is divisible by divisor
diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
index 2748ddad..93ed688a 100644
--- a/mpi/mpi-internal.h
+++ b/mpi/mpi-internal.h
@@ -54,6 +54,13 @@ typedef int mpi_size_t;        /* (must be a signed type) */
 	    (d)[_i] = (s)[_i];		\
     } while(0)
 
+#define MPN_COPY_INCR( d, s, n) 	\
+    do {				\
+	mpi_size_t _i;			\
+	for( _i = 0; _i < (n); _i++ )	\
+	    (d)[_i] = (d)[_i];		\
+    } while (0)
+
 #define MPN_COPY_DECR( d, s, n ) \
     do {				\
 	mpi_size_t _i;			\
diff --git a/mpi/mpi-scan.c b/mpi/mpi-scan.c
index 8626032a..b9745e1a 100644
--- a/mpi/mpi-scan.c
+++ b/mpi/mpi-scan.c
@@ -22,6 +22,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "mpi-internal.h"
+#include "longlong.h"
 
 /****************
  * Scan through an mpi and return byte for byte. a -1 is returned to indicate
@@ -86,3 +87,28 @@ mpi_putbyte( MPI a, unsigned index, int c )
     abort(); /* index out of range */
 }
 
+
+/****************
+ * Count the number of zerobits at the low end of A
+ */
+unsigned
+mpi_trailing_zeros( MPI a )
+{
+    unsigned n, count = 0;
+
+    for(n=0; n < a->nlimbs; n++ ) {
+	if( a->d[n] ) {
+	    unsigned nn;
+	    mpi_limb_t alimb = a->d[n];
+
+	    count_trailing_zeros( nn, alimb );
+	    count += nn;
+	    break;
+	}
+	count += BITS_PER_MPI_LIMB;
+    }
+    return count;
+
+}
+
+