Improved prime number test
authorWerner Koch <wk@gnupg.org>
Thu, 27 Nov 1997 11:44:11 +0000 (11:44 +0000)
committerWerner Koch <wk@gnupg.org>
Thu, 27 Nov 1997 11:44:11 +0000 (11:44 +0000)
cipher/primegen.c
configure.in
mpi/mpi-div.c
mpi/mpi-internal.h
mpi/mpi-scan.c

index 0173b3d..d69f09a 100644 (file)
@@ -28,7 +28,7 @@
 #include "cipher.h"
 
 static int no_of_small_prime_numbers;
 #include "cipher.h"
 
 static int no_of_small_prime_numbers;
-static int rabin_miller( MPI n );
+static int is_not_prime( MPI n, unsigned nbits, int steps, int *count );
 static MPI gen_prime( unsigned nbits, int mode );
 
 
 static MPI gen_prime( unsigned nbits, int mode );
 
 
@@ -50,7 +50,6 @@ generate_public_prime( unsigned  nbits )
 static MPI
 gen_prime( unsigned  nbits, int secret )
 {
 static MPI
 gen_prime( unsigned  nbits, int secret )
 {
-
     unsigned  nlimbs;
     MPI prime, val_2, val_3, result;
     int i;
     unsigned  nlimbs;
     MPI prime, val_2, val_3, result;
     int i;
@@ -111,22 +110,9 @@ gen_prime( unsigned  nbits, int secret )
                continue;  /* stepping (fermat test failed) */
            if( DBG_CIPHER )
                fputc('+', stderr);
                continue;  /* stepping (fermat test failed) */
            if( DBG_CIPHER )
                fputc('+', stderr);
-           /* and a second one */
-           count2++;
-           mpi_powm( result, val_3, prime, prime );
-           if( mpi_cmp_ui(result, 3) )
-               continue;  /* stepping (fermat test failed) */
-           if( DBG_CIPHER )
-               fputc('+', stderr);
 
 
-           /* perform Rabin-Miller tests */
-           for(i=5; i > 0; i-- ) {
-               if( DBG_CIPHER )
-                   fputc('+', stderr);
-               if( rabin_miller(prime) )
-                   break;
-           }
-           if( !i ) {
+           /* perform stronger tests */
+           if( !is_not_prime(prime, nbits, 5, &count2 ) ) {
                if( !mpi_test_bit( prime, nbits-1 ) ) {
                    if( DBG_CIPHER ) {
                        fputc('\n', stderr);
                if( !mpi_test_bit( prime, nbits-1 ) ) {
                    if( DBG_CIPHER ) {
                        fputc('\n', stderr);
@@ -136,7 +122,7 @@ gen_prime( unsigned  nbits, int secret )
                }
                if( DBG_CIPHER ) {
                    fputc('\n', stderr);
                }
                if( DBG_CIPHER ) {
                    fputc('\n', stderr);
-                   log_debug("performed %u simple and %u Fermat/Rabin-Miller tests\n",
+                   log_debug("performed %u simple and %u stronger tests\n",
                                        count1, count2 );
                    log_mpidump("found prime: ", prime );
                }
                                        count1, count2 );
                    log_mpidump("found prime: ", prime );
                }
@@ -158,8 +144,53 @@ gen_prime( unsigned  nbits, int secret )
  * Return 1 if n is not a prime
  */
 static int
  * Return 1 if n is not a prime
  */
 static int
-rabin_miller( MPI n )
+is_not_prime( MPI n, unsigned nbits, int steps, int *count )
 {
 {
-    return 0;
+    MPI x = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI y = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI z = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI a2 = mpi_alloc_set_ui( 2 );
+    MPI q;
+    unsigned i, j, k;
+    int rc = 1;
+
+    mpi_sub_ui( nminus1, n, 1 );
+
+    /* find q and k, so that n = 1 + 2^k * q */
+    q = mpi_copy( nminus1 );
+    k = mpi_trailing_zeros( q );
+    mpi_tdiv_q_2exp(q, q, k);
+
+    for(i=0 ; i < steps; i++ ) {
+       ++*count;
+       do {
+           mpi_set_bytes( x, nbits, get_random_byte, 0 );
+       } while( mpi_cmp( x, n ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
+       mpi_powm( y, x, q, n);
+       if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
+           for( j=1; j < k; j++ ) {
+               mpi_powm(y, y, a2, n);
+               if( !mpi_cmp_ui( y, 1 ) )
+                   goto leave; /* not a prime */
+               if( !mpi_cmp( y, nminus1 ) )
+                   break;  /* may be a prime */
+           }
+           if( j == k )
+               goto leave;
+       }
+       if( DBG_CIPHER )
+           fputc('+', stderr);
+    }
+    rc = 0; /* may be a prime */
+
+  leave:
+    mpi_free( x );
+    mpi_free( y );
+    mpi_free( z );
+    mpi_free( nminus1 );
+    mpi_free( q );
+
+    return rc;
 }
 
 }
 
index 2f77c06..4575bc8 100644 (file)
@@ -18,8 +18,8 @@ AC_ARG_ENABLE(m-debug,
 [  --enable-m-debug    Enable debugging of memory allocation])
 if test "$enableval" = y || test "$enableval" = yes; then
     AC_DEFINE(M_DEBUG)
 [  --enable-m-debug    Enable debugging of memory allocation])
 if test "$enableval" = y || test "$enableval" = yes; then
     AC_DEFINE(M_DEBUG)
-    CFLAGS="-g"
 fi
 fi
+CFLAGS="-g"
 
 dnl
 AC_CANONICAL_HOST
 
 dnl
 AC_CANONICAL_HOST
index 2b39cb4..5273757 100644 (file)
@@ -278,6 +278,37 @@ mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den)
        mpi_free_limb_space(marker[--markidx]);
 }
 
        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
 
 /****************
  * Check wether dividend is divisible by divisor
index 2748dda..93ed688 100644 (file)
@@ -54,6 +54,13 @@ typedef int mpi_size_t;        /* (must be a signed type) */
            (d)[_i] = (s)[_i];          \
     } while(0)
 
            (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;                  \
 #define MPN_COPY_DECR( d, s, n ) \
     do {                               \
        mpi_size_t _i;                  \
index 8626032..b9745e1 100644 (file)
@@ -22,6 +22,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "mpi-internal.h"
 #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
 
 /****************
  * 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 */
 }
 
     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;
+
+}
+
+