mpi: Fix the return value of mpi_invm_generic.

* mpi/mpi-inv.c (mpi_invm_generic): Return correct value.

Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>

1 files changed, 20 insertions, 7 deletions

diff --git a/mpi/mpi-inv.c b/mpi/mpi-inv.c
index a6f0ec1c..0d93b468 100644
--- a/mpi/mpi-inv.c
+++ b/mpi/mpi-inv.c
@@ -178,9 +178,10 @@ mpih_invm_pow2 (mpi_ptr_t ap, mpi_size_t asize, unsigned int k)
 static int
 mpi_invm_generic (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
 {
+    int is_gcd_one;
 #if 0
+    /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X) */
     gcry_mpi_t u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
-    int is_gcd_one;
 
     u = mpi_copy(a);
     v = mpi_copy(n);
@@ -224,11 +225,13 @@ mpi_invm_generic (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
     mpi_free(t3);
     mpi_free(u);
     mpi_free(v);
-
-    return is_gcd_one;
 #elif 0
     /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X)
-     * modified according to Michael Penk's solution for Exercise 35 */
+     * modified according to Michael Penk's solution for Exercise 35
+     * (in the first edition)
+     * In the third edition, it's Exercise 39, and it is described in
+     * page 646 of ANSWERS TO EXERCISES chapter.
+     */
 
     /* FIXME: we can simplify this in most cases (see Knuth) */
     gcry_mpi_t u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
@@ -295,7 +298,8 @@ mpi_invm_generic (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
 	    mpi_sub(t2, t2, u);
 	}
     } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
-    /* mpi_lshift( u3, k ); */
+    /* mpi_lshift( u3, u3, k ); */
+    is_gcd_one = (k == 0 && mpi_cmp_ui (u3, 1) == 0);
     mpi_set(x, u1);
 
     mpi_free(u1);
@@ -311,6 +315,10 @@ mpi_invm_generic (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
     /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X)
      * modified according to Michael Penk's solution for Exercise 35
      * with further enhancement */
+    /* The reference in the comment above is for the first edition.
+     * In the third edition, it's Exercise 39, and it is described in
+     * page 646 of ANSWERS TO EXERCISES chapter.
+     */
     gcry_mpi_t u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
     unsigned k;
     int sign;
@@ -396,7 +404,8 @@ mpi_invm_generic (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
 		mpi_sub(t2, t2, u);
 	}
     } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
-    /* mpi_lshift( u3, k ); */
+    /* mpi_lshift( u3, u3, k ); */
+    is_gcd_one = (k == 0 && mpi_cmp_ui (u3, 1) == 0);
     mpi_set(x, u1);
 
     mpi_free(u1);
@@ -414,10 +423,14 @@ mpi_invm_generic (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
     mpi_free(u);
     mpi_free(v);
 #endif
-    return 1;
+    return is_gcd_one;
 }
 
 
+/*
+ * Set X to the multiplicative inverse of A mod M.  Return true if the
+ * inverse exists.
+ */
 int
 _gcry_mpi_invm (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
 {