fipsmodule/bn/miller_rabin_tests.txt

# This file contains test vectors for whether B is a Miller-Rabin composite
# witness for W. W must be odd and B must satisfy 1 <= B <= W-1.
#
# The following Python function may be used to check values.
#
#  def is_miller_rabin_witness(w, b):
#      # Variable names taken from FIPS 186-4 C.3.1 but the algorithm skips a
#      # couple of optimizations in the FIPS formulation.
#      m = w - 1
#      a = 0
#      while m&1 == 0:
#          a += 1
#          m //= 2
#      # b is a composite witness for w iff the following are true:
#      # - b^m != 1 (mod w)
#      # - b^(m*2^j) != -1 (mod w), for 0 <= j < a
#      z = pow(b, m, w)
#      if z == 1:
#         # b^m = 1 (mod w)
#         return False
#      for j in range(a):
#         if z == w-1:
#             # b^(m*2^j) = -1 (mod w)
#             return False
#         z = (z * z) % w
#      # At this point, z is b^(w-1) (mod w). If z is not 1, w has failed the
#      # Fermat test and is composite. If z is 1, the value of z immediately
#      # before it became 1 is a non-trivial root of unity and w is composite.
#      return True

# Exhaustively test a small prime.

Result = PossiblyPrime
W = 7
B = 1

Result = PossiblyPrime
W = 7
B = 2

Result = PossiblyPrime
W = 7
B = 3

Result = PossiblyPrime
W = 7
B = 4

Result = PossiblyPrime
W = 7
B = 5

Result = PossiblyPrime
W = 7
B = 6


# Random large inputs which try to cover a few cases. The nontrivial square root
# case appears to be difficult to hit randomly.

# b^m = w-1
Result = PossiblyPrime
W = d6b4ffc7cf70b2a2fc5d6023015875504d40e3dcce7c2e6b762c3de7bb806a5074144e7054198dabf53d23108679ccc541d5a99efeb1d1abaf89e0dbcead2a8b
B = fabbafdbec6494ddb5ea4bf458536e87082369b0e53a200ed413f3e64b2fddc7c57c565710fbe73fae5b188fce97d8dcca74c2b5d90906c96d3c2c358a735cd

# b^m = w-1
Result = PossiblyPrime
W = 52cc61c42b341ad56dc11495e7cb2fe31e506b9e99522efbf44cd7c28468d3833c5e360f3c77b0aa43c0495c4e14665ab0d7cee9294c722f0de47d4401828401
B = 3bdc9639c0fc2e77ab48d46e0b4ac6529c11c900e8fe4d82d75767c0556feb23d3f42d4924d16876a743feb386b7b84c7fd16a6c252f662faf0024d19972e62f

# b^m = w-1
Result = PossiblyPrime
W = cff9897aa7dce0f2afad262b2de57d301305de717f3539c537c4ce062f8cb70df13fbc1eb4a3b9f0958a8810d1ca9042b4f23334b285a15fee3fc66498761d4b
B = 9ceb43132fddf9ee4104ea1cb3eb2253c1d7f803f05f0305de9e31a17dd75832f47b8bf189a9b7ca0905f2a7470d9c6349080f481ff1708696fa12d972e7d7ba

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 67d1825dad5344170e65247a87aef1634a1b32bdc22f2f04d9d2959767bb5a27610fba55cd607e0f9fdd9fbb0f7f98e40d5e1eb2f52318fb5be4dbfd30d38861
B = 260fb14724ff80984736859d8755ee98b25bcb56db9fde1db001a1e1273374034c5b75fd60b3710c7a08ce7d390776f010f384d4e32943cf0c477497d53e9e05

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = ad0bc85b58aaa204177aa9431a40929beb1cbea2dd6f66a25cc54600013213b225ba881805661df43f4208965ada7aacc8095d07d3cbef1a7bbfaae8b745f731
B = 3d9310f20e9c80269fa6830c7e1a6f02fc5c58646001a9ef6b8b3e496602ff22c3dcb2ddb6a221723fc1722ce237fb46f7a7bb2945e415c8839b15a972f076c9

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = b25c917f55f6c7b596921daba919f35039e5d805119c1587e99849dd7104460c86214f162a6f17aea847bc7f3859e59f2991d457059511972ef373d4bc75e309
B = a1f10b261dee84619b0423201d46af19eef9ec0612cf947c4d5c36c0c4b28207f75967e69452eabad0a5dcd28f27f7a8a7ed9c8b3e5026c6e0ba5634d94c2d44

# b^m = 1
Result = PossiblyPrime
W = d3eeb0eff05b6992e9fa61b02755e155f4aae28c6e45ddb874edd86acdd2d83d18a20e0e00d8b8bc94b92d14fc3f41ced6ababe8ac98c7730c075dbe0f699369
B = 6b7717269c6225203681a1cacec87cacd83003ec6e9e3f04effcc4f86634770c0860e1f2770b8f303719a44949664a1094205a99d95a0856758fed66d690105e

# b^m = 1
Result = PossiblyPrime
W = 64561b8d9aa50340c3a01ccb3e6e17f5023513661c012be288f3900a3ca76890e67290b9560fa1d480f9d2aacccca581b5690636665f243fa13aff5d0bff12d3
B = 1f5ff70d3d60671ebc5fbfca731898a04438053dbc3c841e6335f487e457d92d9efb5d506d5bef6872d58d12b9a41c950bfc38d12ed977c90eacdd6535b811a0

# b^m = 1
Result = PossiblyPrime
W = 69c63fbf44df21b0ed0ee929a740c12d1f3f064da0dcd9d509f31fa45fa27d1a759ab5a9f6f1040d7ee90a0b1e68f779273c41ea1c1198fd547ff6bd70c7e787
B = 5f7996a9bbfd8fd88e472220b70077bfdacdd63d88885134431f024c2acb7126827b174eb093eb5313f07bb5461de9b0feb7d77ca2c39c2a323a150f33ea525f

# End of iteration
Result = Composite
W = 28cc3e08c44571c6dcb98a9ab8b4f3e2b16e1f884997d94a3188bcbb7f1b7cdaecdae8329c013ec8f75dc00004da0039943e4262cd080b16a42910102e00dddb
B = 512061ab1c69931c2fa0bb89d8d09f3c9209230bf927ddd6fb6a72075f967ed3c4dbb5f437bf4d31ca7344782b22011ad56609dc19aed65319bababfc13dd7

# End of iteration
Result = Composite
W = 4eeb7b4d371c45fe8586fee3b1efd792176b70f6cc2698dfa1dd028366626febe0199c3c5f77a5c3cad0057a04767383051d41965255d03681b2a37edad34a9b
B = 4afc2e85f84017b3fd6967a227eb74c8297b40ea02733d9513bff9b3f01081963f25872f4254afc4e9321eea35b2a1e42eadb186fcc84f2f30f4a994350b93b8

# End of iteration
Result = Composite
W = 8e35a959555dd2eb66c65cee3c264071d20671f159e1f9896f1d0ceb041905fcf053eacc189de317c3ee6f93901223cbf30d5b7ddbbdab981790e2f6397e6803
B = 44c0153759309ec4e5b1e59d57c1b126545ef7ea302b6e43561df4d16068b922389d6924f01c945d9080d1f93a0732599bdedae72d6d590839dc0884dd860441


# 0x6c1 = 1729 = 7 * 13 * 19 is a Fermat pseudoprime.

# Found non-trivial square root
Result = Composite
W = 6c1
B = b8

# End of iteration
Result = Composite
W = 6c1
B = 111

# End of iteration
Result = Composite
W = 6c1
B = 11d

# Found non-trivial square root
Result = Composite
W = 6c1
B = 19c

# Found non-trivial square root
Result = Composite
W = 6c1
B = 223

# End of iteration
Result = Composite
W = 6c1
B = 3aa

# Found non-trivial square root
Result = Composite
W = 6c1
B = 653


# 1729 has a number of false witnesses.

# b^m = 1
Result = PossiblyPrime
W = 6c1
B = 78

# b^m = 1
Result = PossiblyPrime
W = 6c1
B = eb

# b^m = w-1
Result = PossiblyPrime
W = 6c1
B = 178

# b^m = w-1
Result = PossiblyPrime
W = 6c1
B = 178

# b^m = w-1
Result = PossiblyPrime
W = 6c1
B = 1aa

# b^m = 1
Result = PossiblyPrime
W = 6c1
B = 271

# b^m = 1
Result = PossiblyPrime
W = 6c1
B = 2b2


# 1 and W-1 are always nonwitnesses.
Result = PossiblyPrime
W = 6c1
B = 1

Result = PossiblyPrime
W = 6c1
B = 6c0


# https://kconrad.math.uconn.edu/blurbs/ugradnumthy/millerrabin.pdf, examples
# 3.1 and 3.2 has a complete list of false witnesses for 65 = 0x41 and
# 85 = 0x55.

# b^m = 1
Result = PossiblyPrime
W = 41
B = 1

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 41
B = 8

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 41
B = 12

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 41
B = 2f

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 41
B = 39

# b^m = w-1
Result = PossiblyPrime
W = 41
B = 40

# b^m = 1
Result = PossiblyPrime
W = 55
B = 1

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 55
B = d

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 55
B = 26

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 55
B = 2f

# Some b^(m*2^j) = w-1
Result = PossiblyPrime
W = 55
B = 48

# b^m = w-1
Result = PossiblyPrime
W = 55
B = 54

# Other witnesses for 65 and 85 will report composite:

# Found non-trivial square root
Result = Composite
W = 41
B = 2c

# End of iteration
Result = Composite
W = 41
B = 16

# End of iteration
Result = Composite
W = 41
B = 14

# End of iteration
Result = Composite
W = 41
B = 2

# End of iteration
Result = Composite
W = 41
B = 3a

# End of iteration
Result = Composite
W = 55
B = 40

# End of iteration
Result = Composite
W = 55
B = 7

# End of iteration
Result = Composite
W = 55
B = 23

# End of iteration
Result = Composite
W = 55
B = 2e

# End of iteration
Result = Composite
W = 55
B = 2a