diff --git a/library/bignum.c b/library/bignum.c
index c81ee5b..1fea9b6 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( const 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,