Merge GH #2482 Fix ressol loop with composite moduli

Backport of #2478

2 files changed, 23 insertions, 4 deletions

diff --git a/src/lib/math/numbertheory/ressol.cpp b/src/lib/math/numbertheory/ressol.cpp
index de89e0384..f9e7e3eb1 100644
--- a/src/lib/math/numbertheory/ressol.cpp
+++ b/src/lib/math/numbertheory/ressol.cpp
@@ -51,10 +51,23 @@ BigInt ressol(const BigInt& a, const BigInt& p)
    if(n == 1)
       return r;
 
-   // find random non quadratic residue z
-   BigInt z = 2;
-   while(jacobi(z, p) == 1) // while z quadratic residue
-      ++z;
+   // find random quadratic nonresidue z
+   word z = 2;
+   for(;;)
+      {
+      if(jacobi(z, p) == -1) // found one
+         break;
+
+      z += 1; // try next z
+
+      /*
+      * The expected number of tests to find a non-residue modulo a
+      * prime is 2. If we have not found one after 256 then almost
+      * certainly we have been given a non-prime p.
+      */
+      if(z >= 256)
+         return -BigInt(1);
+      }
 
    BigInt c = power_mod(z, (q << 1) + 1, p);
 
diff --git a/src/tests/data/bn/ressol.vec b/src/tests/data/bn/ressol.vec
index 631a718dc..5ccecaa5c 100644
--- a/src/tests/data/bn/ressol.vec
+++ b/src/tests/data/bn/ressol.vec
@@ -55,3 +55,9 @@ Output = 4
 Input = 120846049
 Modulus = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000ffff
 Output = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000d50e
+
+# https://github.com/randombit/botan/issues/2476
+
+Input = 36201062682172739133895248774702438971945580133434799509985105960684260785324273354862758698920426637444639195349626
+Modulus = 7804371375789980578453993074482915734542659201646310600434507062475783156891915333150829678341466565780783986206336267453050408740994685888001
+Output = -1