35 {0x0000000000000001ull, 0x0000000000000012ull,
true},
36 {0x0000000000000001ull, 0x000000000000007eull,
true},
37 {0xffffffffffffffffull, 0x0000000000000085ull,
true},
38 {0x0000000000000001ull, 0x000000000000008eull,
true},
39 {0x950e87d7f5606615ull, 0x0000000000000001ull,
false},
40 {0x042db9232c61275dull, 0x0000000000000001ull,
false},
41 {0x6dbca290a9eab707ull, 0x0000000000000001ull,
false},
42 {0xc4fd394d4c10a4ffull, 0x0000000000000001ull,
false},
43 {0x6814a2bc786a6d2dull, 0x0000000000000001ull,
false},
44 {0xbc051c6ca26b351full, 0x0000000000000001ull,
false},
45 {0xd4c08880a5a4666dull, 0x0000000000000001ull,
false},
46 {0xfe5213e529610ae1ull, 0x0000000000000001ull,
false},
47 {0x6c50afb6e9fb123dull, 0x0000000000000001ull,
false},
48 {0xebac94af6f28d015ull, 0x0000000000000001ull,
false},
49 {0x194f9545adba52cfull, 0x0000000000000001ull,
true},
50 {0x1d4b7ef2c675ce05ull, 0x0000000000000001ull,
false},
51 {0xd998efd82733e933ull, 0x000000000000002full,
false},
52 {0xcb57d5d86df216c3ull, 0x0000000000000024ull,
false},
53 {0x8860a84722025e05ull, 0x000000000000002aull,
false},
54 {0xc5b864d733176469ull, 0x0000000000000038ull,
false},
55 {0x7a2f11088d29b147ull, 0x000000000000003bull,
true},
56 {0x2fcb9940da10faabull, 0x000000000000002bull,
false},
57 {0xb98937dfef041067ull, 0x0000000000000034ull,
false},
58 {0x4a2e3224dd4b712full, 0x0000000000000031ull,
false},
59 {0x07fdc889fa017ed7ull, 0x0000000000000024ull,
false},
60 {0x425a7de181eeadd7ull, 0x000000000000002eull,
false},
61 {0xaaabc8d366e0440dull, 0x0000000000000031ull,
false},
62 {0x1ac44b703371364full, 0x0000000000000031ull,
false},
63 {0x016590c55646e6d1ull, 0x0000000000002079ull,
false},
64 {0xf16e981a0b7a6e1dull, 0x0000000000003968ull,
false},
65 {0x1167fba4a2927979ull, 0x00000000000026d4ull,
false},
66 {0x5532c8673d01ac0full, 0x000000000000349eull,
false},
67 {0xee26cbc0358b24d3ull, 0x000000000000328full,
true},
68 {0x1a7415559bdb39b3ull, 0x0000000000002378ull,
false},
69 {0xd6257b492186c8b5ull, 0x00000000000034e5ull,
false},
70 {0x1ec1b0b1dee7539dull, 0x00000000000030c1ull,
false},
71 {0x1d790bcaeffd4d2dull, 0x00000000000030f3ull,
false},
72 {0x3537a844de18f50bull, 0x00000000000034dbull,
false},
73 {0x64b5e3f81a293b3bull, 0x0000000000003d91ull,
false},
74 {0xb047719de8eef3d7ull, 0x0000000000002a23ull,
false},
75 {0xf177d49f03ddc3bfull, 0x000000000001a52cull,
false},
76 {0x7048dacaa745fdd5ull, 0x000000000001a16dull,
false},
77 {0xfce79398852e0401ull, 0x000000000001c641ull,
false},
78 {0x80271e94760c9b75ull, 0x0000000000019ca5ull,
false},
79 {0x293f65848aa18f43ull, 0x000000000001889dull,
false},
80 {0xb0baf029520e015full, 0x000000000001f27full,
false},
81 {0x7ad955568f86a26bull, 0x000000000001d90cull,
false},
82 {0xd487d3421c720603ull, 0x000000000001a11cull,
false},
83 {0x310288290b43dbfbull, 0x0000000000011cb3ull,
false},
84 {0x6dbbac73d50ca99full, 0x000000000001d849ull,
false},
85 {0xb7a13dce8e4595dfull, 0x000000000001e023ull,
false},
86 {0xed9a76b9e91b8ec1ull, 0x0000000000012527ull,
false},
87 {0x75c33f8fcb8031ffull, 0x0000000000021662ull,
false},
88 {0xddfc20fe1e7c31d3ull, 0x00000000000355d3ull,
false},
89 {0xd17dad339930e76full, 0x000000000002fe19ull,
false},
90 {0x0deef007acfbba2bull, 0x000000000002938cull,
false},
91 {0x8fcd110ce94f47b1ull, 0x000000000002575dull,
false},
92 {0x227d512de1660a41ull, 0x0000000000035b64ull,
true},
93 {0x2abb018969cbe6ebull, 0x000000000003aa48ull,
false},
94 {0x93a8b5d809cea2a9ull, 0x000000000002ffa7ull,
false},
95 {0x602f8e87d16bc8bfull, 0x0000000000035cc1ull,
false},
96 {0x61ef7dfce376bd79ull, 0x000000000003d21eull,
false},
97 {0xff5e243c496a590bull, 0x000000000002f5c7ull,
false},
98 {0x1d2e1a2e089934a9ull, 0x000000000002f7abull,
false},
99 {0xe443e6031233f1e1ull, 0x00000000000b4a20ull,
false},
100 {0x3ede6f125ab59d11ull, 0x00000000000e5814ull,
false},
101 {0xf5d46d8127762b7bull, 0x000000000008b87cull,
false},
102 {0x60083c7dad1dd141ull, 0x00000000000f9afaull,
false},
103 {0xb7a68aa8611b9b59ull, 0x00000000000a86fcull,
false},
104 {0x7893032bd828056full, 0x000000000009c0aeull,
false},
105 {0x34c8a05ca34be96bull, 0x00000000000da10eull,
false},
106 {0x921082dfc966aed7ull, 0x00000000000eb7e2ull,
false},
107 {0x6e5d9a3007c331a3ull, 0x00000000000d4f57ull,
false},
108 {0xf7767fd63a0806a7ull, 0x000000000008a07aull,
false},
109 {0xf0723a8383f43dc5ull, 0x0000000000082414ull,
false},
110 {0x106025b5fb65e625ull, 0x00000000000d0451ull,
false},
111 {0xa0d72f15feb859ebull, 0x0000000002fa9bedull,
false},
112 {0x3b97b6c911560053ull, 0x00000000026f8eb8ull,
false},
113 {0x5fe2b11364b97757ull, 0x00000000025f7a97ull,
false},
114 {0xbf1317f85a8a9441ull, 0x00000000030cc190ull,
false},
115 {0xf0b02956ff594f79ull, 0x0000000002ac6c79ull,
false},
116 {0x2912ab9fa4002d91ull, 0x0000000002e8d474ull,
false},
117 {0x56761e8879073c59ull, 0x00000000028dcf80ull,
false},
118 {0xd0efd4ff3912a0fdull, 0x0000000003b0012bull,
false},
119 {0x8919551203d33d87ull, 0x000000000269137eull,
false},
120 {0xefb4cad164f85da9ull, 0x00000000028741a1ull,
false},
121 {0x1732b75d08d75497ull, 0x0000000003189469ull,
false},
122 {0xec5093da27623245ull, 0x000000000261eaedull,
false},
123 {0xea45cdaf628e21c9ull, 0x00000000cd8a9084ull,
false},
124 {0xc231185b0272834full, 0x00000000ab699ad2ull,
false},
125 {0x6ff327f4119ee915ull, 0x0000000098ca4c3full,
false},
126 {0x1d5d73026b06b341ull, 0x00000000f2546119ull,
false},
127 {0x511173b251af8015ull, 0x00000000c3846eceull,
false},
128 {0x1d74a080ebbfbb2bull, 0x00000000ed8b79edull,
false},
129 {0x9736b29f0b03d0e1ull, 0x00000000ade3540cull,
false},
130 {0xecbeb26fceaf0df5ull, 0x00000000d76c473aull,
false},
131 {0x6782e42f80a0f27dull, 0x00000000acafb91cull,
false},
132 {0x25e74da2f39f015full, 0x00000000a93c7ae4ull,
false},
133 {0x1a18b9b1c2c8b503ull, 0x00000000b7b2a53bull,
false},
134 {0xc0f76e59731535edull, 0x00000000cf7d9b08ull,
false},
135 {0x3e115e3e75118be1ull, 0x0000000edd801db4ull,
false},
136 {0x399246294d8fc043ull, 0x0000000cff8f5cffull,
false},
137 {0xa364f1b057f4865full, 0x0000000bf9f2dce0ull,
false},
138 {0x1fb37062a68f65c1ull, 0x0000000aca707a92ull,
false},
139 {0x3ff1295c1d296c15ull, 0x0000000c1455fcadull,
false},
140 {0xb484b8d3f354db29ull, 0x0000000d7a2ee034ull,
false},
141 {0x1a46b9e3a2663f03ull, 0x0000000d177d70d6ull,
false},
142 {0x36a208e01b1b4ee3ull, 0x00000008e33a0336ull,
false},
143 {0x9d3bd30e22749e55ull, 0x0000000f65265fe5ull,
false},
144 {0xebe4418c6286ef71ull, 0x0000000e27fcb0f2ull,
false},
145 {0xcfedc87950868c9dull, 0x00000009784ecbbbull,
false},
146 {0x106572c92038d12full, 0x0000000f2176822eull,
false},
147 {0x810287a90cffae31ull, 0x00003f23b03c1008ull,
false},
148 {0x113167635255aa79ull, 0x000027c16aab79e5ull,
false},
149 {0x559ccfb8c80ce421ull, 0x00002cff263695f9ull,
false},
150 {0xc2299345df0b305dull, 0x00002d46dac97abbull,
false},
151 {0xed1137eb5e5e1047ull, 0x000028ad8e8e8733ull,
false},
152 {0xe3bd76bf57cec991ull, 0x000030083e2681d1ull,
false},
153 {0xeee4852d330c2395ull, 0x000021512f3334bfull,
false},
154 {0xcfe680854c95ea73ull, 0x000038eac209f79dull,
false},
155 {0xa2842cb2fb44c6a3ull, 0x00002c91a0f4dd5aull,
false},
156 {0xe5fbc6d02bd667d7ull, 0x00002d0f621d1238ull,
false},
157 {0x6cb5b7d2721a1891ull, 0x00003bc198411febull,
false},
158 {0x31afaa01fdc2dbd7ull, 0x000035d827aa949bull,
false},
159 {0x332508b2d1c97795ull, 0x00b93ad7cba7ddcdull,
false},
160 {0x4930986a215c9b8bull, 0x00bcaf643fe36a17ull,
false},
161 {0x4e1309a0fc447a7full, 0x00819d6afe7f773eull,
false},
162 {0x637118bb0b0e773dull, 0x00ba17e70a7a8b0cull,
false},
163 {0x20b9122fca694c79ull, 0x00b0773e8ea50117ull,
false},
164 {0xa544b6d2cf823377ull, 0x00be2e211529057cull,
false},
165 {0x01d6aedaa22e88e9ull, 0x00e73bb93bc7eeadull,
false},
166 {0xf332dec5058c062bull, 0x00802df2f9537531ull,
false},
167 {0x26dd7c451562a837ull, 0x008c72e5f03cde37ull,
false},
168 {0xeae27c2bcf28335bull, 0x009482fa03ac665dull,
false},
169 {0x6774a90031d2ba09ull, 0x00e6b37c3fbd6d30ull,
false},
170 {0xc958935b157304b1ull, 0x009ef804a8e636c6ull,
false},
171 {0xa7d73426f0aee715ull, 0x32b01555bdca343full,
false},
172 {0x65c2195389de9f31ull, 0x3ed2bf30a8108c27ull,
false},
173 {0x938f35b2dc04bbfdull, 0x390b921100cdfa67ull,
false},
174 {0x890c62927989d7e7ull, 0x24742f054b47a18bull,
false},
175 {0xd0ae2b468f227e2full, 0x2e7d02750d3832c1ull,
false},
176 {0xa37579c44c86abf9ull, 0x331a7cd6eecff786ull,
false},
177 {0x3cd64d14ac521437ull, 0x2e1831695b4be237ull,
false},
178 {0x3d1791cf2b9550bdull, 0x3316d1c9a89a476eull,
false},
179 {0x12e2992b24380fb7ull, 0x23ee2059ccc14927ull,
false},
180 {0x9dca0bdcdd3a68c5ull, 0x3ac38dfdd6290f03ull,
false},
181 {0x0e8936d8133fee35ull, 0x2b9de39e671eaa35ull,
false},
182 {0x616eb2a9fb09b28dull, 0x2ab0308b5d235cabull,
false},
183 {0xad4cf62c94a4f317ull, 0x679daf749ca944bbull,
false},
184 {0xc1f007cd2413872bull, 0x4c7ef3d3091e9247ull,
false},
185 {0xe8ed59599a0e9c31ull, 0x581b5d6f9e716b3dull,
false},
186 {0x92852160c8b912b1ull, 0x6cd6cc248ff5b11bull,
false},
187 {0xd41339c948a6e7cbull, 0x5e3cd0009f140b4eull,
false},
188 {0x34186cdd3c3c5141ull, 0x48cdb5333343fd70ull,
false},
189 {0xbab5120ef942a0f7ull, 0x5e400b6806c1ec71ull,
false},
190 {0x28e208906796f59full, 0x7decf7dd76c9773aull,
false},
191 {0xf3d6da5c3df5a975ull, 0x51524f93fef4ca54ull,
false},
192 {0x2935e72533e01f5dull, 0x71b7e13936a1483cull,
false},
193 {0x91a6821dd6d9ac33ull, 0x799453bb6b70929bull,
true},
194 {0x1069a2114ba0d199ull, 0x58ddebc322e9dde7ull,
false},
195 {0xefb27ceed7b68265ull, 0xe57782da9744782bull,
false},
196 {0x31eed1a700b6ec29ull, 0x9a1e2d7b24252495ull,
false},
197 {0xaa1a3b8e0336d241ull, 0xbe96c928f239c6e8ull,
false},
198 {0xd977bc4f68576763ull, 0xf5c1e0efc83c98eeull,
false},
199 {0x4788ae323e2a32d9ull, 0xfa5286e53a968735ull,
false},
200 {0x10fb01d7cb2aaf85ull, 0xe18e124e9a1938b3ull,
true},
201 {0x31ee89b3b4eaa601ull, 0x94cc7b72fc3196cdull,
false},
202 {0x56ed6af7e42c893bull, 0xf6db24bb16f42afeull,
false},
203 {0xbf83c8b771312e2dull, 0xb8a2d999a2f70ca6ull,
false},
204 {0xcd2f2acc0bcd93bbull, 0xa4eaa48c2f25b957ull,
false},
205 {0x1765dee27d9f4de1ull, 0xb1546df37cf45bebull,
false},
206 {0x53f901828270094dull, 0x96ec812185e2bf7aull,
false},
207 {0xbdca6ba34ba3aec1ull, 0x0000000000000001ull,
true},
208 {0x3f48dad818d61ccfull, 0x0000000000000001ull,
true},
209 {0x5cf7913a8a83b817ull, 0x0000000000000001ull,
true},
210 {0x72e68302bf30028bull, 0x0000000000031e30ull,
true},
211 {0xe07055c2c6066ea9ull, 0x0000000000028754ull,
true},
212 {0xc331631cc701924bull, 0x000000000002327cull,
true},
213 {0x4b3ea92729448615ull, 0x00000000b86af1e9ull,
true},
214 {0xe6aa9fbe8d2ed5d5ull, 0x00000000b5db7aa4ull,
true},
215 {0xcc3727a535e6f183ull, 0x00000000d52d7c5cull,
true},
216 {0x9b5c5903c10b0041ull, 0x0000c903df44645full,
true},
217 {0x423fdaf1a4a83317ull, 0x00009f63b437842aull,
true},
218 {0x0240ea4123c4796bull, 0x0000f9ad7a912fe0ull,
true},
219 {0x181f3b48a4db2427ull, 0xc1387e39b26d94deull,
true},
220 {0x037b77e84bc2e4e5ull, 0xc36d6e1a55261cfdull,
true},
221 {0x8af483d92122f4f7ull, 0xfd2c71512c957f86ull,
true},
223 {0x51adc5b22410a5f5ull, 0x000000000002be69ull,
false},
224 {0x51adc5b22410a5f7ull, 0x000000000002be69ull,
false},
225 {0x51adc5b22410a5f9ull, 0x000000000002be69ull,
false},
226 {0x51adc5b22410a5fbull, 0x000000000002be69ull,
false},
227 {0x51adc5b22410a5fdull, 0x000000000002be69ull,
false},
228 {0x51adc5b22410a5ffull, 0x000000000002be69ull,
false},
229 {0x51adc5b22410a601ull, 0x000000000002be69ull,
false},
230 {0x51adc5b22410a603ull, 0x000000000002be69ull,
false},
231 {0x51adc5b22410a605ull, 0x000000000002be69ull,
false},
256 u64 seed = 0x6e6f747269616c32ull;
257 const uint HB[] = {1, 3, 17, 63, 64};
258 for (
size_t hb_index = 0; hb_index <
ARRAY_SIZE(HB); ++hb_index) {
259 uint hb = HB[hb_index];
260 for (
int i = 0; i < 200; ++i) {
261 mp_limb_t lo = xorshift64(&seed), hi = xorshift64(&seed);
262 if (hb < 64) hi &= ((
mp_limb_t)-1) >> (64 - hb);
271 struct prime_case {
u64 hi,
lo;
bool expect;
const char* what; } cases[] = {
272 {0x7fffffffffffffffull, 0xffffffffffffffffull,
true,
"2^127-1 Mersenne"},
273 {0xffffffffffffffffull, 0xffffffffffffff61ull,
true,
"2^128-159 largest prime < 2^128"},
274 {0x0000000000000001ull, 0x000000000000000dull,
true,
"2^64+13"},
275 {0x0000000000000001ull, 0x0000000000000001ull,
false,
"2^64+1 Fermat"},
276 {0xffffffffffffffffull, 0xffffffffffffffffull,
false,
"2^128-1 (3 divides)"},
277 {0x000000000000437aull, 0xe92817f9fc85b7e5ull,
false,
"psi_12 SPSP(2..37)"},
278 {0x000000000000437aull, 0xe92817f9fc85b7e4ull,
false,
"psi_12-1 even"},
279 {0x000000000000437aull, 0xe92817f9fc85b7d1ull,
true,
"first prime < psi_12"},
280 {0x000000000000437aull, 0xe92817f9fc85b7fbull,
true,
"first prime > psi_12"},
281 {0x000000000002be69ull, 0x51adc5b22410a5fdull,
false,
"psi_13 = SWbound"},
282 {0x000000000002be69ull, 0x51adc5b22410a68bull,
true,
"first prime > SWbound"},
283 {0x0000000000000001ull, 0x0000000000000000ull,
false,
"2^64 even"},
286 {0x800000035f5a7854ull, 0x024690fc2c1cab2dull,
true,
"prime with least|D|=211"},
287 {0x80000023e5c609bfull, 0xa5c985498fc11b3dull,
true,
"prime with least|D|=227"},
288 {0x8000000be28e524cull, 0x609ffaaa3f5d4dd5ull,
true,
"prime with least|D|=211"},
290 for (
size_t c_index = 0; c_index <
ARRAY_SIZE(cases); ++c_index) {
291 const struct prime_case c = cases[c_index];
304 int found[2] = {0, 0};
305 const int groups[2][2] = {{66, 78}, {108, 126}};
307 for (
int g = 0; g < 2; ++g) {
308 for (
int t = groups[g][0];
t <= groups[g][1] && found[g] < 2; ++
t) {
309 for (
uint k = 3;
k < 999 && found[g] < 2;
k += 2) {
320 TEST_CHECK_MSG(found[g] >= 1,
"proth prime coverage per SW side");
326 u64 seed = 0x70726f74683231ull;
327 for (
int i = 0; i < 20; ++i) {
328 u64 p = 0x100000000ull + (xorshift64(&seed) & 0xffffffffull);
331 u64 q = 0x100000000ull + (xorshift64(&seed) & 0xffffffffull);
342 u64 p = 0x000001000000000full;
356 TEST_RUN(
"numth/prime", is_prime_2_notrial);
357 TEST_RUN(
"numth/prime", is_prime_2);
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
int lmmp_is_prime_2_notrial_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数(无试除法)
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static int expect2(u64 lo, u64 hi, bool prime)
static bool proth_cert_g(uint k, int t, int nbase)
static bool ref_is_prime64(u64 n)
static mp_size_t k2t_limbs(mp_ptr dst, int t, mp_limb_t k, mp_limb_t c)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_RUN(category, name)
static void check_prime_2_agreement(mp_limb_t lo, mp_limb_t hi, const char *what)
static const struct prime_vector vec128[]
Copyright (C) 2026 HJimmyK (Jericho Knox)