diff --git a/src/test/sigencoding_tests.cpp b/src/test/sigencoding_tests.cpp
--- a/src/test/sigencoding_tests.cpp
+++ b/src/test/sigencoding_tests.cpp
@@ -11,6 +11,11 @@
 
 BOOST_FIXTURE_TEST_SUITE(sigencoding_tests, BasicTestingSetup)
 
+static uint64_t next(uint64_t x) {
+    // Simple linear congruential generator by Donald Knuth.
+    return x * 6364136223846793005 + 1442695040888963407;
+}
+
 static valtype SignatureWithHashType(valtype vchSig, SigHashType sigHash) {
     vchSig.push_back(static_cast<uint8_t>(sigHash.getRawSigHashType()));
     return vchSig;
@@ -164,9 +169,24 @@
          0xcf, 0x2c, 0xe0, 0xd0, 0x3b, 0x2e, 0xf0},
     };
 
-    // If we add many more flags, this loop can get too expensive, but we can
-    // rewrite in the future to randomly pick a set of flags to evaluate.
-    for (uint32_t flags = 0; flags < (1U << 17); flags++) {
+    // Use LCG to probe pseudorandom flag patterns:
+    //  first  0x14057b7e,
+    //   then  0x1a08ee11,
+    //   then  0x9af67822,
+    //         ...
+    // With 4096 iterations, for every possible quadruple of flags you can
+    // name, there are at least 199 iterations with all four flags on, and at
+    // least 194 iterations with all four flags off.
+    uint64_t randstate = 0;
+    for (int i = 0; i < 4096; i++) {
+        randstate = next(randstate);
+        uint32_t flags = randstate >> 32;
+
+        if (i == 99) {
+            // make sure the LCG is producing expected values
+            BOOST_CHECK_EQUAL(flags, 0xf306b780);
+        }
+
         ScriptError err = SCRIPT_ERR_OK;
 
         // Empty sig is always valid.
@@ -331,9 +351,24 @@
          0xde, 0xf0, 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0},
     };
 
-    // If we add many more flags, this loop can get too expensive, but we can
-    // rewrite in the future to randomly pick a set of flags to evaluate.
-    for (uint32_t flags = 0; flags < (1U << 17); flags++) {
+    // Use LCG to probe pseudorandom flag patterns:
+    //  first  0x14057b7e,
+    //   then  0x1a08ee11,
+    //   then  0x9af67822,
+    //         ...
+    // With 4096 iterations, for every possible quadruple of flags you can
+    // name, there are at least 199 iterations with all four flags on, and at
+    // least 194 iterations with all four flags off.
+    uint64_t randstate = 0;
+    for (int i = 0; i < 4096; i++) {
+        randstate = next(randstate);
+        uint32_t flags = randstate >> 32;
+
+        if (i == 99) {
+            // make sure the LCG is producing expected values
+            BOOST_CHECK_EQUAL(flags, 0xf306b780);
+        }
+
         ScriptError err = SCRIPT_ERR_OK;
 
         // Compressed pubkeys are always valid.