Move monty_invert to numthry.h and use it in CurveGFp as well

4 files changed, 48 insertions, 51 deletions

diff --git a/src/math/ec_gfp/curve_gfp.h b/src/math/ec_gfp/curve_gfp.h
index 9d10c2028..d6c2f2a8c 100644
--- a/src/math/ec_gfp/curve_gfp.h
+++ b/src/math/ec_gfp/curve_gfp.h
@@ -37,7 +37,7 @@ class BOTAN_DLL CurveGFp
          {
          const BigInt r = BigInt::power_of_2(p_words * BOTAN_MP_WORD_BITS);
 
-         p_dash = (((r * inverse_mod(r, p)) - 1) / p).word_at(0);
+         p_dash = monty_inverse(p.word_at(0));
 
          r2  = (r * r) % p;
          a_r = (a * r) % p;
diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index 38d683f1c..e3c673ea5 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -8,6 +8,7 @@
 #include <botan/numthry.h>
 #include <botan/reducer.h>
 #include <botan/internal/bit_ops.h>
+#include <botan/internal/mp_core.h>
 #include <algorithm>
 
 namespace Botan {
@@ -298,6 +299,45 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
    return D;
    }
 
+word monty_inverse(word input)
+   {
+   word b = input;
+   word x2 = 1, x1 = 0, y2 = 0, y1 = 1;
+
+   // First iteration, a = n+1
+   word q = bigint_divop(1, 0, b);
+   word r = (MP_WORD_MAX - q*b) + 1;
+   word x = x2 - q*x1;
+   word y = y2 - q*y1;
+
+   word a = b;
+   b = r;
+   x2 = x1;
+   x1 = x;
+   y2 = y1;
+   y1 = y;
+
+   while(b > 0)
+      {
+      q = a / b;
+      r = a - q*b;
+      x = x2 - q*x1;
+      y = y2 - q*y1;
+
+      a = b;
+      b = r;
+      x2 = x1;
+      x1 = x;
+      y2 = y1;
+      y1 = y;
+      }
+
+   // Now invert in addition space
+   y2 = (MP_WORD_MAX - y2) + 1;
+
+   return y2;
+   }
+
 /*
 * Modular Exponentiation
 */
diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h
index 7d0330ef6..a34d855b2 100644
--- a/src/math/numbertheory/numthry.h
+++ b/src/math/numbertheory/numthry.h
@@ -107,6 +107,13 @@ BigInt BOTAN_DLL power_mod(const BigInt& b,
 */
 BigInt BOTAN_DLL ressol(const BigInt& x, const BigInt& p);
 
+/*
+* Compute -input^-1 mod 2^MP_WORD_BITS. Returns zero if input
+* is even. If input is odd, input and 2^n are relatively prime
+* and an inverse exists.
+*/
+word BOTAN_DLL monty_inverse(word input);
+
 /**
 * @param x a positive integer
 * @return count of the zero bits in x, or, equivalently, the largest
diff --git a/src/math/numbertheory/powm_mnt.cpp b/src/math/numbertheory/powm_mnt.cpp
index 1928cef9d..53e75d2b1 100644
--- a/src/math/numbertheory/powm_mnt.cpp
+++ b/src/math/numbertheory/powm_mnt.cpp
@@ -11,56 +11,6 @@
 
 namespace Botan {
 
-namespace {
-
-/*
-* Compute -input^-1 mod 2^MP_WORD_BITS. We are assured that the
-* inverse exists because input is odd (checked by checking that the
-* modulus is odd in the Montgomery_Exponentiator constructor, and
-* input is the low word of the modulus and thus also odd), and thus
-* input and 2^n are relatively prime.
-*/
-word monty_inverse(word input)
-   {
-   word b = input;
-   word x2 = 1, x1 = 0, y2 = 0, y1 = 1;
-
-   // First iteration, a = n+1
-   word q = bigint_divop(1, 0, b);
-   word r = (MP_WORD_MAX - q*b) + 1;
-   word x = x2 - q*x1;
-   word y = y2 - q*y1;
-
-   word a = b;
-   b = r;
-   x2 = x1;
-   x1 = x;
-   y2 = y1;
-   y1 = y;
-
-   while(b > 0)
-      {
-      q = a / b;
-      r = a - q*b;
-      x = x2 - q*x1;
-      y = y2 - q*y1;
-
-      a = b;
-      b = r;
-      x2 = x1;
-      x1 = x;
-      y2 = y1;
-      y1 = y;
-      }
-
-   // Now invert in addition space
-   y2 = (MP_WORD_MAX - y2) + 1;
-
-   return y2;
-   }
-
-}
-
 /*
 * Set the exponent
 */