Add a constant time divide variant for dividing by uint8_t

Originally wrote it for div-by-word but that ends up requiring a dword
type which we don't always have. And uint8_t covers the most important
cases of n = 10 and n = 58 (whenever I get around to writing base58).
We could portably support up to div-by-uint32, but I don't think we need it.

Nicely for n = 10, this is actually faster than the variable time division.

2 files changed, 22 insertions, 0 deletions

diff --git a/src/tests/data/bn/divide.vec b/src/tests/data/bn/divide.vec
index f1220561e..0a6dd2423 100644
--- a/src/tests/data/bn/divide.vec
+++ b/src/tests/data/bn/divide.vec
@@ -159,3 +159,7 @@ In1 = 0x123F71E77499975C79EE4C4F7B275A4410863CEDC3E244724D5AF83A8A2DD73C5D5913E9
 In2 = 0x78B294AD98589FDCC2D53FCB0FC9F0E70E4E30323832D5669F66E15
 Output = 0x26B426C03F76F97048D5DE0B8D9DBD02F4DC
 
+In1 = 1996953214196350189568
+In2 = 13331618315827609940
+Output = 149
+
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 9d8a88497..d85115e03 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -405,6 +405,16 @@ class BigInt_Div_Test final : public Text_Based_Test
          e /= b;
          result.test_eq("a /= b", e, c);
 
+         if(b.bytes() == 1)
+            {
+            const uint8_t b8 = b.byte_at(0);
+
+            Botan::BigInt ct_q;
+            uint8_t ct_r;
+            Botan::ct_divide_u8(a, b8, ct_q, ct_r);
+            result.test_eq("ct_divide_u8 q", ct_q, c);
+            }
+
          Botan::BigInt ct_q, ct_r;
          Botan::ct_divide(a, b, ct_q, ct_r);
          result.test_eq("ct_divide q", ct_q, c);
@@ -449,6 +459,14 @@ class BigInt_Mod_Test final : public Text_Based_Test
             result.test_eq("a % b (as word)", a % b_word, expected);
             }
 
+         if(b.bytes() == 1)
+            {
+            Botan::BigInt ct_q;
+            Botan::uint8_t ct_r;
+            Botan::ct_divide_u8(a, b.byte_at(0), ct_q, ct_r);
+            result.test_eq("ct_divide_u8 r", ct_r, expected);
+            }
+
          Botan::BigInt ct_q, ct_r;
          Botan::ct_divide(a, b, ct_q, ct_r);
          result.test_eq("ct_divide r", ct_r, expected);