Improved prime number test

1 files changed, 26 insertions, 0 deletions

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;
+
+}
+
+