Strong pseudoprimes for "Primality test"

[weilycoder]

• https://judge.yosupo.jp/problem/primality_test

It is well known that when using the Miller–Rabin primality test for 64-bit integers, we only need to test with the base set $\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}$ to ensure correctness. However, if any of these bases are omitted, the algorithm may no longer be reliable.

To verify this, I tried removing each base one by one and ran the corresponding code. Unfortunately, all the modified versions were still accepted by the online judge—meaning they passed all test cases without detecting the incorrect implementations.

Therefore, I would like to provide a list of strong pseudoprimes that can be used to hack these incomplete versions of the Miller–Rabin test.

• For the algorithm without base 2:

327490017037567
1568970154017181
2572458837835321
9848626400055301
31904683808220541
59469576459970141
66510298255323781
97489065784524121
138423753103464533
147489203101794181

• For the algorithm without base 325:

1411807385341
149251536924661
548682148033207
1218406862772067
4612252004425621
4664852830965601
5397002552661301
5758349211061021
7228785694024261
9036938694845881

• For the algorithm without base 9375:

443538368977861
600931003849021
844376232342961
956576019772621
1249436276765353
2658508721224021
3498575484219427
4405189345093153
4909685312621953
5170964326119901

• For the algorithm without base 28178:

4341937413061
134241542443357
274311004325221
930902631647761
5157224922526951
10400979360216061
13811639076478981
15648765378749821
16196702270683357
23282264781147191

• For the algorithm without base 450775:

5517315475561
6198534518881
678190622066821
1017577016060221
3871743176258821
5486537078669791
8497129681217633
16125255651342241
22348134516425581
31229713668351061

• For the algorithm without base 9780504:

3933464309633
88134267054217
6955596610077781
9859984670114881
9950976450370621
11498260951309861
18872895708032941
20510974954976941
33028766723304901
74230341983719741

• For the algorithm without base 1795265022:

107528788110061
4124056415015881
6172200677022841
16017371501248981
42651094922680843
53731576226425987
61106861709915451
62659844695824967
65545040248120261
89451666695775361

However, I believe there still exist variants using certain fixed sets of bases that cannot guarantee correctness, and I'm unable to cover all of them here.