2 files changed, 35 insertions, 33 deletions

diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp
index 257ece56e..466996e99 100644
--- a/src/math/numbertheory/reducer.cpp
+++ b/src/math/numbertheory/reducer.cpp
@@ -1,6 +1,6 @@
 /*
 * Modular Reducer
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2011 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -22,10 +22,8 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod)
    mod_words = modulus.sig_words();
 
    modulus_2 = Botan::square(modulus);
-   mod2_words = modulus_2.sig_words();
 
    mu = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words) / modulus;
-   mu_words = mu.sig_words();
    }
 
 /*
@@ -36,45 +34,49 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const
    if(mod_words == 0)
       throw Invalid_State("Modular_Reducer: Never initalized");
 
-   BigInt t1 = x;
-   t1.set_sign(BigInt::Positive);
-
-   if(t1 < modulus)
+   if(x.cmp(modulus, false) < 0)
       {
-      if(x.is_negative() && t1.is_nonzero())
-         return modulus - t1;
+      if(x.is_negative())
+         return x + modulus; // make positive
       return x;
       }
+   else if(x.cmp(modulus_2, false) < 0)
+      {
+      BigInt t1 = x;
+      t1.set_sign(BigInt::Positive);
+      t1 >>= (MP_WORD_BITS * (mod_words - 1));
+      t1 *= mu;
 
-   if(t1 >= modulus_2)
-      return (x % modulus);
+      t1 >>= (MP_WORD_BITS * (mod_words + 1));
+      t1 *= modulus;
 
-   t1 >>= (MP_WORD_BITS * (mod_words - 1));
-   t1 *= mu;
-   t1 >>= (MP_WORD_BITS * (mod_words + 1));
+      t1.mask_bits(MP_WORD_BITS * (mod_words + 1));
 
-   t1 *= modulus;
-   t1.mask_bits(MP_WORD_BITS * (mod_words+1));
+      BigInt t2 = x;
+      t2.set_sign(BigInt::Positive);
+      t2.mask_bits(MP_WORD_BITS * (mod_words + 1));
 
-   BigInt t2 = x;
-   t2.set_sign(BigInt::Positive);
-   t2.mask_bits(MP_WORD_BITS * (mod_words+1));
+      t2 -= t1;
 
-   t1 = t2 - t1;
+      if(t2.is_negative())
+         {
+         BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (mod_words + 1));
+         t2 += b_to_k1;
+         }
 
-   if(t1.is_negative())
+      while(t2 >= modulus)
+         t2 -= modulus;
+
+      if(x.is_positive())
+         return t2;
+      else
+         return (modulus - t2);
+      }
+   else
       {
-      BigInt b_to_k1(BigInt::Power2, MP_WORD_BITS * (mod_words+1));
-      t1 += b_to_k1;
+      // too big, fall back to normal division
+      return (x % modulus);
       }
-
-   while(t1 >= modulus)
-      t1 -= modulus;
-
-   if(x.is_negative() && t1.is_nonzero())
-      t1 = modulus - t1;
-
-   return t1;
    }
 
 }
diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h
index 05c12a440..76712074c 100644
--- a/src/math/numbertheory/reducer.h
+++ b/src/math/numbertheory/reducer.h
@@ -13,7 +13,7 @@
 namespace Botan {
 
 /**
-* Modular Reducer
+* Modular Reducer (using Barrett's technique)
 */
 class BOTAN_DLL Modular_Reducer
    {
@@ -53,7 +53,7 @@ class BOTAN_DLL Modular_Reducer
       Modular_Reducer(const BigInt& mod);
    private:
       BigInt modulus, modulus_2, mu;
-      size_t mod_words, mod2_words, mu_words;
+      size_t mod_words;
    };
 
 }