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
@@ -77,6 +77,43 @@
     }
 }
 
+// Use LCG to probe pseudorandom flag patterns:
+//  first  0x00000000,
+//   then  0x14057b7e,
+//   then  0x1a08ee11,
+//         ...
+// 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 195 iterations with all four flags off.
+class LCGflags {
+    uint64_t state;
+
+    uint64_t Advance() {
+        uint64_t oldstate = state;
+        state = oldstate * 6364136223846793005 + 1442695040888963407;
+        return oldstate;
+    }
+
+public:
+    LCGflags(uint64_t initialstate = 0) : state(initialstate) {}
+
+    uint32_t GetFlags() { return Advance() >> 32; }
+};
+
+BOOST_AUTO_TEST_CASE(test_lcg) {
+    LCGflags lcg;
+    // We want that the first iteration is all-0 flags which is a special
+    // case we want for sure being done.
+    BOOST_REQUIRE_EQUAL(lcg.GetFlags(), 0x00000000);
+    for (int i = 0; i < 99; i++) {
+        lcg.GetFlags();
+    }
+    // Make sure the LCG is producing expected value after many iterations.
+    // This ensures mul and add overflows are acting as expected on this
+    // architecture.
+    BOOST_REQUIRE_EQUAL(lcg.GetFlags(), 0xf306b780);
+}
+
 BOOST_AUTO_TEST_CASE(checksignatureencoding_test) {
     valtype minimalSig{0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01};
     valtype highSSig{
@@ -164,9 +201,10 @@
          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++) {
+    LCGflags lcg;
+    for (int i = 0; i < 4096; i++) {
+        uint32_t flags = lcg.GetFlags();
+
         ScriptError err = SCRIPT_ERR_OK;
 
         // Empty sig is always valid.
@@ -331,9 +369,10 @@
          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++) {
+    LCGflags lcg;
+    for (int i = 0; i < 4096; i++) {
+        uint32_t flags = lcg.GetFlags();
+
         ScriptError err = SCRIPT_ERR_OK;
 
         // Compressed pubkeys are always valid.