inverse_mod - avoid mutable zero_bits, avoid making needless copies of

the arguments

1 files changed, 12 insertions, 11 deletions

diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index c6816219f..5a87b4466 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -209,28 +209,29 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
       throw Invalid_Argument("inverse_mod: arguments must be non-negative");
 
    if(n.is_zero() || (n.is_even() && mod.is_even()))
-      return 0;
+      return 0; // fast fail checks
 
-   BigInt x = mod, y = n, u = mod, v = n;
+   //const BigInt x = mod, y = n;
+   BigInt u = mod, v = n;
    BigInt A = 1, B = 0, C = 0, D = 1;
 
    while(u.is_nonzero())
       {
-      size_t zero_bits = low_zero_bits(u);
-      u >>= zero_bits;
-      for(size_t i = 0; i != zero_bits; ++i)
+      const size_t u_zero_bits = low_zero_bits(u);
+      u >>= u_zero_bits;
+      for(size_t i = 0; i != u_zero_bits; ++i)
          {
          if(A.is_odd() || B.is_odd())
-            { A += y; B -= x; }
+            { A += n; B -= mod; }
          A >>= 1; B >>= 1;
          }
 
-      zero_bits = low_zero_bits(v);
-      v >>= zero_bits;
-      for(size_t i = 0; i != zero_bits; ++i)
+      const size_t v_zero_bits = low_zero_bits(v);
+      v >>= v_zero_bits;
+      for(size_t i = 0; i != v_zero_bits; ++i)
          {
          if(C.is_odd() || D.is_odd())
-            { C += y; D -= x; }
+            { C += n; D -= mod; }
          C >>= 1; D >>= 1;
          }
 
@@ -239,7 +240,7 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
       }
 
    if(v != 1)
-      return 0;
+      return 0; // no modular inverse
 
    while(D.is_negative()) D += mod;
    while(D >= mod) D -= mod;