Better cofactor selection in outer gcdext loop.

1 files changed, 19 insertions, 15 deletions

diff --git a/mpn/generic/gcdext.c b/mpn/generic/gcdext.c
index 645cdff5a..6b5509f18 100644
--- a/mpn/generic/gcdext.c
+++ b/mpn/generic/gcdext.c
@@ -388,25 +388,29 @@ mpn_gcdext (mp_ptr gp, mp_ptr up, mp_size_t *usizep,
 	}
     }
 
-  if (mpn_zero_p (ap, n))
+  if (UNLIKELY (mpn_cmp (ap, bp, n) == 0))
     {
-      MPN_COPY (gp, bp, n);
-      MPN_NORMALIZE_NOT_ZERO (u0, un);
-      MPN_COPY (up, u0, un);
-      *usizep = -un;
+      /* Must return the smallest cofactor, +u1 or -u0 */
+      int c;
 
-      TMP_FREE;
-      return n;
-    }
-  else if (mpn_zero_p (bp, n))
-    {
       MPN_COPY (gp, ap, n);
-      MPN_NORMALIZE_NOT_ZERO (u1, un);
-      MPN_COPY (up, u1, un);
-      *usizep = un;
 
-      TMP_FREE;
-      return n;
+      MPN_CMP (c, u0, u1, un);
+      ASSERT (c != 0);
+      if (c < 0)
+	{
+	  MPN_NORMALIZE (u0, un);
+	  MPN_COPY (up, u0, un);
+	  *usizep = -un;
+	}
+      else
+	{
+	  MPN_NORMALIZE_NOT_ZERO (u1, un);
+	  MPN_COPY (up, u1, un);
+	  *usizep = un;
+	}
+
+      return n;      
     }
   else if (mpn_zero_p (u0, un))
     {