diff --git a/include/polarssl/bignum.h b/include/polarssl/bignum.h
index 9bed027..b63a242 100644
--- a/include/polarssl/bignum.h
+++ b/include/polarssl/bignum.h
@@ -58,7 +58,7 @@
 #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    -0x000E  /**< The input arguments are not acceptable. */
 #define POLARSSL_ERR_MPI_MALLOC_FAILED                     -0x0010  /**< Memory allocation failed. */
 
-#define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
+#define MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
 
 /*
  * Maximum size MPIs are allowed to grow to in number of limbs.
diff --git a/library/bignum.c b/library/bignum.c
index 2a97a59..4de2e9a 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1797,40 +1797,27 @@
 };
 
 /*
- * Miller-Rabin primality test  (HAC 4.24)
+ * Small divisors test (X must be positive)
+ *
+ * Return values:
+ * 0: no small factor (possible prime, more tests needed)
+ * 1: certain prime
+ * POLARSSL_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
+ * other negative: error
  */
-int mpi_is_prime( mpi *X,
-                  int (*f_rng)(void *, unsigned char *, size_t),
-                  void *p_rng )
+static int mpi_check_small_factors( const mpi *X )
 {
-    int ret, xs;
-    size_t i, j, n, s;
-    mpi W, R, T, A, RR;
+    int ret = 0;
+    size_t i;
+    t_uint r;
 
-    if( mpi_cmp_int( X, 0 ) == 0 ||
-        mpi_cmp_int( X, 1 ) == 0 )
-        return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
-
-    if( mpi_cmp_int( X, 2 ) == 0 )
-        return( 0 );
-
-    mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
-    mpi_init( &RR );
-
-    xs = X->s; X->s = 1;
-
-    /*
-     * test trivial factors first
-     */
     if( ( X->p[0] & 1 ) == 0 )
         return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
 
     for( i = 0; small_prime[i] > 0; i++ )
     {
-        t_uint r;
-
         if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
-            return( 0 );
+            return( 1 );
 
         MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
 
@@ -1838,6 +1825,24 @@
             return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
     }
 
+cleanup:
+    return( ret );
+}
+
+/*
+ * Miller-Rabin pseudo-primality test  (HAC 4.24)
+ */
+static int mpi_miller_rabin( const mpi *X,
+                             int (*f_rng)(void *, unsigned char *, size_t),
+                             void *p_rng )
+{
+    int ret;
+    size_t i, j, n, s;
+    mpi W, R, T, A, RR;
+
+    mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
+    mpi_init( &RR );
+
     /*
      * W = |X| - 1
      * R = W >> lsb( W )
@@ -1905,9 +1910,6 @@
     }
 
 cleanup:
-
-    X->s = xs;
-
     mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
     mpi_free( &RR );
 
@@ -1915,6 +1917,34 @@
 }
 
 /*
+ * Pseudo-primality test: small factors, then Miller-Rabin
+ */
+int mpi_is_prime( mpi *X,
+                  int (*f_rng)(void *, unsigned char *, size_t),
+                  void *p_rng )
+{
+    int ret;
+    const mpi XX = { 1, X->n, X->p }; /* Abs(X) */
+
+    if( mpi_cmp_int( &XX, 0 ) == 0 ||
+        mpi_cmp_int( &XX, 1 ) == 0 )
+        return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
+
+    if( mpi_cmp_int( &XX, 2 ) == 0 )
+        return( 0 );
+
+    if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
+    {
+        if( ret == 1 )
+            return( 0 );
+
+        return( ret );
+    }
+
+    return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
+}
+
+/*
  * Prime number generation
  */
 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
@@ -1923,6 +1953,7 @@
 {
     int ret;
     size_t k, n;
+    t_uint r;
     mpi Y;
 
     if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
@@ -1952,26 +1983,45 @@
     }
     else
     {
-        MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
+        /*
+         * An necessary condition for Y and X = 2Y + 1 to be prime
+         * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
+         * Make sure it is satisfied, while keeping X = 3 mod 4
+         */
+        MPI_CHK( mpi_mod_int( &r, X, 3 ) );
+        if( r == 0 )
+            MPI_CHK( mpi_add_int( X, X, 8 ) );
+        else if( r == 1 )
+            MPI_CHK( mpi_add_int( X, X, 4 ) );
+
+        /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
+        MPI_CHK( mpi_copy( &Y, X ) );
         MPI_CHK( mpi_shift_r( &Y, 1 ) );
 
         while( 1 )
         {
-            if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
+            /*
+             * First, check small factors for X and Y
+             * before doing Miller-Rabin on any of them
+             */
+            if( ( ret = mpi_check_small_factors(  X         ) ) == 0 &&
+                ( ret = mpi_check_small_factors( &Y         ) ) == 0 &&
+                ( ret = mpi_miller_rabin(  X, f_rng, p_rng  ) ) == 0 &&
+                ( ret = mpi_miller_rabin( &Y, f_rng, p_rng  ) ) == 0 )
             {
-                if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
-                    break;
-
-                if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
-                    goto cleanup;
+                break;
             }
 
             if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
                 goto cleanup;
 
-            MPI_CHK( mpi_add_int( &Y, X, 1 ) );
-            MPI_CHK( mpi_add_int(  X, X, 2 ) );
-            MPI_CHK( mpi_shift_r( &Y, 1 ) );
+            /*
+             * Next candidates. We want to preserve Y = (X-1) / 2 and
+             * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
+             * so up Y by 6 and X by 12.
+             */
+            MPI_CHK( mpi_add_int(  X,  X, 12 ) );
+            MPI_CHK( mpi_add_int( &Y, &Y, 6  ) );
         }
     }
 
diff --git a/programs/pkey/dh_genprime.c b/programs/pkey/dh_genprime.c
index 2089fb6..f51465a 100644
--- a/programs/pkey/dh_genprime.c
+++ b/programs/pkey/dh_genprime.c
@@ -74,6 +74,8 @@
     printf( "         predefined DHM parameters from dhm.h instead!\n\n" );
     printf( "============================================================\n\n" );
 
+    printf( "  ! Generating large primes may take minutes!\n" );
+
     printf( "\n  . Seeding the random number generator..." );
     fflush( stdout );
 
diff --git a/tests/suites/test_suite_mpi.data b/tests/suites/test_suite_mpi.data
index 924f364..859a38e 100644
--- a/tests/suites/test_suite_mpi.data
+++ b/tests/suites/test_suite_mpi.data
@@ -504,11 +504,19 @@
 depends_on:POLARSSL_GENPRIME
 mpi_is_prime:10:"47":0
 
-Test mpi_is_prime #1
+Test mpi_is_prime #1a
+depends_on:POLARSSL_GENPRIME
+mpi_is_prime:10:"83726728883146151979668243326097049289208482987685965276439157162337476477581":POLARSSL_ERR_MPI_NOT_ACCEPTABLE
+
+Test mpi_is_prime #1b
+depends_on:POLARSSL_GENPRIME
+mpi_is_prime:10:"81248637410584921454869308488899267096530643632730258201256092582281263244641":POLARSSL_ERR_MPI_NOT_ACCEPTABLE
+
+Test mpi_is_prime #2a
 depends_on:POLARSSL_GENPRIME
 mpi_is_prime:10:"827131507221654563937832686696200995595835694437983658840870036586124168186967796809117749047430768825822857042432722828096779098498192459819306321073968735177531164565305635281198148032612029767584644305912099":0
 
-Test mpi_is_prime #2
+Test mpi_is_prime #2b
 depends_on:POLARSSL_GENPRIME
 mpi_is_prime:10:"827131507221654563937832686696200995595835694437983658840870036586124168186967796809117749047430768825822857042432722828096779098498192459819306321073968735177531164565305635281198148032612029767584644305912001":POLARSSL_ERR_MPI_NOT_ACCEPTABLE