diff --git a/crypto/fipsmodule/bn/sqrt.cc.inc b/crypto/fipsmodule/bn/sqrt.cc.inc
index 56d89e0..9b76788 100644
--- a/crypto/fipsmodule/bn/sqrt.cc.inc
+++ b/crypto/fipsmodule/bn/sqrt.cc.inc
@@ -192,20 +192,9 @@
         goto end;
       }
     } else {
-      if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) {
+      if (!BN_rand_range_ex(y, 22, p)) {
         goto end;
       }
-      if (BN_ucmp(y, p) >= 0) {
-        if (BN_usub(y, y, p)) {
-          goto end;
-        }
-      }
-      // now 0 <= y < |p|
-      if (BN_is_zero(y)) {
-        if (!BN_set_word(y, i)) {
-          goto end;
-        }
-      }
     }
 
     r = bn_jacobi(y, q, ctx);  // here 'q' is |p|
diff --git a/crypto/fipsmodule/bn/test/mod_sqrt_tests.txt b/crypto/fipsmodule/bn/test/mod_sqrt_tests.txt
index 64c752b..dc69d5d 100644
--- a/crypto/fipsmodule/bn/test/mod_sqrt_tests.txt
+++ b/crypto/fipsmodule/bn/test/mod_sqrt_tests.txt
@@ -323,6 +323,38 @@
 A = 2eee37cf06228a387788188e650bc6d8a2ff402931443f69156a29155eca07dcb45f3aac238d92943c0c25c896098716baa433f25bd696a142f5a69d5d937e81
 P = 9df9d6cc20b8540411af4e5357ef2b0353cb1f2ab5ffc3e246b41c32f71e951f
 
+# This prime is 1 mod 8, so we need Tonelli/Shanks. The least quadratic
+# non-residue is 37, so we give up on small numbers to find a non-residue.
+ModSqrt = 2e42c
+A = 2
+P = 7deb1
+
+ModSqrt = 2
+A = 4
+P = 7deb1
+
+# This prime is 1 mod 8, so we need Tonelli/Shanks. The least quadratic
+# non-residue is 67, so we give up on small numbers to find a non-residue.
+ModSqrt = fb0fab
+A = 2
+P = 2e3a719
+
+ModSqrt = 01d6df74
+A = 3
+P = 2e3a719
+
+ModSqrt = 2
+A = 4
+P = 2e3a719
+
+ModSqrt = 6d151e
+A = 5
+P = 2e3a719
+
+ModSqrt = 2573aa
+A = 12345
+P = 2e3a719
+
 
 # NotModSquare tests.
 #