[PATCH 07/10] sntrup761: defer reduction in polynomial multiplication

* cipher/sntrup761.c (Rq_mult_small, R3_mult): Accumulate inner product
in int32_t and reduce once per output coefficient.
* tests/bench-slope.c (pq_algos): Use full measurement repetitions for
sntrup761.
--

Both multiplications called 'Fq_freeze'/'F3_freeze' on every multiply-
accumulate of the O(p^2) inner loop. Terms are bounded by q12 for Rq and
by one for R3, and there are at most p of them, so the accumulator stays
far from int32_t range and reduction is needed only for the result.

Benchmark on AMD Ryzen 9 9950X3D, SNTRUP761 usec/operation, quick
random disabled ('base' being state before this patch series):

             |     base   before    after   speedup    total
 keygen      |  37971.9   2900.4   1971.5     1.47x   19.26x
 encap       |   7355.8   1184.7    243.0     4.88x   30.27x
 decap       |  12207.1   3322.4    592.5     5.61x   20.60x

Remaining keygen time is in R3_recip and Rq_recip3, where reduction is
part of an element-wise running update and cannot be deferred.

Signed-off-by: Jussi Kivilinna <[email protected]>
---
 cipher/sntrup761.c  | 24 ++++++++++++++----------
 tests/bench-slope.c |  2 +-
 2 files changed, 15 insertions(+), 11 deletions(-)

diff --git a/cipher/sntrup761.c b/cipher/sntrup761.c
index 94229d79..bcb6e651 100644
--- a/cipher/sntrup761.c
+++ b/cipher/sntrup761.c
@@ -451,22 +451,24 @@ static void
 R3_mult (small * h, const small * f, const small * g)
 {
   small fg[p + p - 1];
-  small result;
+  int32_t result;
   int i, j;
 
+  /* Terms are in {-1,0,1} and there are at most p of them, so the
+     accumulator cannot overflow and needs reduction only once. */
   for (i = 0; i < p; ++i)
     {
       result = 0;
       for (j = 0; j <= i; ++j)
-	result = F3_freeze (result + f[j] * g[i - j]);
-      fg[i] = result;
+	result += f[j] * g[i - j];
+      fg[i] = F3_freeze (result);
     }
   for (i = p; i < p + p - 1; ++i)
     {
       result = 0;
       for (j = i - p + 1; j < p; ++j)
-	result = F3_freeze (result + f[j] * g[i - j]);
-      fg[i] = result;
+	result += f[j] * g[i - j];
+      fg[i] = F3_freeze (result);
     }
 
   for (i = p + p - 2; i >= p; --i)
@@ -547,22 +549,24 @@ static void
 Rq_mult_small (Fq * h, const Fq * f, const small * g)
 {
   Fq fg[p + p - 1];
-  Fq result;
+  int32_t result;
   int i, j;
 
+  /* Products are bounded by q12 and there are at most p terms, so the
+     accumulator cannot overflow and needs reduction only once. */
   for (i = 0; i < p; ++i)
     {
       result = 0;
       for (j = 0; j <= i; ++j)
-	result = Fq_freeze (result + f[j] * (int32_t) g[i - j]);
-      fg[i] = result;
+	result += f[j] * (int32_t) g[i - j];
+      fg[i] = Fq_freeze (result);
     }
   for (i = p; i < p + p - 1; ++i)
     {
       result = 0;
       for (j = i - p + 1; j < p; ++j)
-	result = Fq_freeze (result + f[j] * (int32_t) g[i - j]);
-      fg[i] = result;
+	result += f[j] * (int32_t) g[i - j];
+      fg[i] = Fq_freeze (result);
     }
 
   for (i = p + p - 2; i >= p; --i)
diff --git a/tests/bench-slope.c b/tests/bench-slope.c
index 4b296f0b..911b2b15 100644
--- a/tests/bench-slope.c
+++ b/tests/bench-slope.c
@@ -3691,7 +3691,7 @@ static const struct
 #endif
   { "sntrup761", GCRY_KEM_SNTRUP761, NULL,
     GCRY_KEM_SNTRUP761_PUBKEY_LEN, GCRY_KEM_SNTRUP761_SECKEY_LEN,
-    GCRY_KEM_SNTRUP761_ENCAPS_LEN, GCRY_KEM_SNTRUP761_SHARED_LEN, 16, 4, 0 },
+    GCRY_KEM_SNTRUP761_ENCAPS_LEN, GCRY_KEM_SNTRUP761_SHARED_LEN, 1, 1, 0 },
   { "cm6688128f", GCRY_KEM_CM6688128F, NULL,
     GCRY_KEM_CM6688128F_PUBKEY_LEN, GCRY_KEM_CM6688128F_SECKEY_LEN,
     GCRY_KEM_CM6688128F_ENCAPS_LEN, GCRY_KEM_CM6688128F_SHARED_LEN, 16, 1, 1 },
-- 
2.53.0