Add BigInt::reduce_below

2 files changed, 33 insertions, 0 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index e5f8974d5..50e93c38d 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -247,6 +247,30 @@ BigInt BigInt::operator-() const
    return x;
    }
 
+void BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
+   {
+   if(p.is_negative())
+      throw Invalid_Argument("BigInt::reduce_below mod must be positive");
+
+   const size_t p_words = p.sig_words();
+
+   if(size() < p_words + 1)
+      grow_to(p_words + 1);
+
+   if(ws.size() < p_words + 1)
+      ws.resize(p_words + 1);
+
+   for(;;)
+      {
+      word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
+
+      if(borrow)
+         break;
+
+      m_reg.swap(ws);
+      }
+   }
+
 /*
 * Return the absolute value of this number
 */
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 611c2e2dd..71629b3aa 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -216,6 +216,15 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      bool operator !() const { return (!is_nonzero()); }
 
      /**
+     * Return *this below mod
+     *
+     * Assumes that *this is (if anything) only slightly larger than
+     * mod and performs repeated subtractions. It should not be used if
+     * *this is much larger than mod, instead of modulo operator.
+     */
+     void reduce_below(const BigInt& mod, secure_vector<word> &ws);
+
+     /**
      * Zeroize the BigInt. The size of the underlying register is not
      * modified.
      */