LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime_2.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#include "impl/inlines.h"
24#include "impl/longlong.h"
25#include "mparam.h"
26#include "lmmp/lmmpn.h"
27#include "lmmp/numth.h"
28
29/*
30 Granlund-Montgomery 试除表:奇素数 3..137 共 32 个,每行
31 [0..1] = p^(-1) mod 2^128
32 [2..3] = floor((2^128-1)/p)
33 0 <= n < 2^128 可被 p 整除 <=> n * p^(-1) <= floor((2^128-1)/p)
34*/
35static const ulong ll_trial_primes[32][4] = {
36 { 0xaaaaaaaaaaaaaaab, 0xaaaaaaaaaaaaaaaa, 0x5555555555555555, 0x5555555555555555 }, // 3
37 { 0xcccccccccccccccd, 0xcccccccccccccccc, 0x3333333333333333, 0x3333333333333333 }, // 5
38 { 0x6db6db6db6db6db7, 0xb6db6db6db6db6db, 0x4924924924924924, 0x2492492492492492 }, // 7
39 { 0x2e8ba2e8ba2e8ba3, 0xa2e8ba2e8ba2e8ba, 0x745d1745d1745d17, 0x1745d1745d1745d1 }, // 11
40 { 0x4ec4ec4ec4ec4ec5, 0xc4ec4ec4ec4ec4ec, 0x3b13b13b13b13b13, 0x13b13b13b13b13b1 }, // 13
41 { 0xf0f0f0f0f0f0f0f1, 0xf0f0f0f0f0f0f0f0, 0x0f0f0f0f0f0f0f0f, 0x0f0f0f0f0f0f0f0f }, // 17
42 { 0x86bca1af286bca1b, 0xbca1af286bca1af2, 0xe50d79435e50d794, 0x0d79435e50d79435 }, // 19
43 { 0xd37a6f4de9bd37a7, 0x4de9bd37a6f4de9b, 0x42c8590b21642c85, 0x0b21642c8590b216 }, // 23
44 { 0x34f72c234f72c235, 0xc234f72c234f72c2, 0xd3dcb08d3dcb08d3, 0x08d3dcb08d3dcb08 }, // 29
45 { 0xef7bdef7bdef7bdf, 0xdef7bdef7bdef7bd, 0x8421084210842108, 0x0842108421084210 }, // 31
46 { 0x14c1bacf914c1bad, 0xc1bacf914c1bacf9, 0x5306eb3e45306eb3, 0x06eb3e45306eb3e4 }, // 37
47 { 0x8f9c18f9c18f9c19, 0x18f9c18f9c18f9c1, 0x63e7063e7063e706, 0x063e7063e7063e70 }, // 41
48 { 0x82fa0be82fa0be83, 0xbe82fa0be82fa0be, 0xf417d05f417d05f4, 0x05f417d05f417d05 }, // 43
49 { 0x51b3bea3677d46cf, 0x3677d46cefa8d9df, 0x882b9310572620ae, 0x0572620ae4c415c9 }, // 47
50 { 0x21cfb2b78c13521d, 0x13521cfb2b78c135, 0x4873ecade304d487, 0x04d4873ecade304d }, // 53
51 { 0xcbeea4e1a08ad8f3, 0x8f2fba9386822b63, 0x15b1e5f75270d045, 0x0456c797dd49c341 }, // 59
52 { 0x4fbcda3ac10c9715, 0x14fbcda3ac10c971, 0x4325c53ef368eb04, 0x04325c53ef368eb0 }, // 61
53 { 0xf0b7672a07a44c6b, 0xc2dd9ca81e9131ab, 0x40f4898d5f85bb39, 0x03d226357e16ece5 }, // 67
54 { 0x193d4bb7e327a977, 0x4f52edf8c9ea5dbf, 0x240e6c2b4481cd85, 0x039b0ad12073615a }, // 71
55 { 0x7e3f1f8fc7e3f1f9, 0x3f1f8fc7e3f1f8fc, 0x070381c0e070381c, 0x0381c0e070381c0e }, // 73
56 { 0x9b8b577e613716af, 0xd5df984dc5abbf30, 0xa5440cf6474a8819, 0x033d91d2a2067b23 }, // 79
57 { 0xa3784a062b2e43db, 0x2818acb90f6bf3a9, 0x6f0940c565c87b5f, 0x03159721ed7e7534 }, // 83
58 { 0xf47e8fd1fa3f47e9, 0xd1fa3f47e8fd1fa3, 0xc0b81702e05c0b81, 0x02e05c0b81702e05 }, // 89
59 { 0xa3a0fd5c5f02a3a1, 0x5f02a3a0fd5c5f02, 0xa0fd5c5f02a3a0fd, 0x02a3a0fd5c5f02a3 }, // 97
60 { 0x3a4c0a237c32b16d, 0xc32b16cfd7720f35, 0xc83cd4e930288df0, 0x0288df0cac5b3f5d }, // 101
61 { 0xdab7ec1dd3431b57, 0xd0c6d5bf60ee9a18, 0x88b2f392a409f116, 0x027c45979c95204f }, // 103
62 { 0x77a04c8f8d28ac43, 0xa2b10bf66e0e5aea, 0xdc1cb5d4ef40991f, 0x02647c69456217ec }, // 107
63 { 0xa6c0964fda6c0965, 0xc0964fda6c0964fd, 0x9b02593f69b02593, 0x02593f69b02593f6 }, // 109
64 { 0x90fdbc090fdbc091, 0xc090fdbc090fdbc0, 0x43f6f0243f6f0243, 0x0243f6f0243f6f02 }, // 113
65 { 0x7efdfbf7efdfbf7f, 0xbf7efdfbf7efdfbf, 0x0408102040810204, 0x0204081020408102 }, // 127
66 { 0x03e88cb3c9484e2b, 0xf82ee6986d6f63aa, 0x7f05dcd30dadec75, 0x01f44659e4a42715 }, // 131
67 { 0xe21a291c077975b9, 0x21a291c077975b8f, 0x701de5d6e3f8868a, 0x01de5d6e3f8868a4 }, // 137
68};
69
70/* 设 d 为最大试除素数。若 x < 2^128 - d*B,则积的高 limb 单独比较(<)与
71 双 limb 比较(<=)结果一致,可省一次低位比较;近上界的输入(如从
72 2^128 递减生成素数)退回全比较 */
73#define FAST_TRIAL_BOUND (MP_ULONG_MAX - 137)
74
75static inline int ll_le(u128 a, u128 b) {
76 return a <= b;
77}
78
79static inline void mul_128(u128 a, u128 b, u128 *hi, u128 *lo) {
80#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
81 ulong a0 = _u128low(a), a1 = _u128high(a);
82 ulong b0 = _u128low(b), b1 = _u128high(b);
83 u128 p00 = (u128)a0 * b0;
84 u128 p01 = (u128)a0 * b1;
85 u128 p10 = (u128)a1 * b0;
86 u128 p11 = (u128)a1 * b1;
87 u128 mid = p01 + p10;
88 u128 cm = mid < p01; /* 129 位交叉和进位,属 hi 的第 64 位 */
89 u128 l = (mid << 64) + p00;
90 u128 cl = l < p00; /* 进位属 hi 的第 0 位 */
91 *lo = l;
92 *hi = p11 + (mid >> 64) + cl + (cm << 64);
93#else
94 ulong u[4];
95 _umul128to256_(_u128high(a), _u128low(a), _u128high(b), _u128low(b), u);
96 *lo = ((u128)u[1] << 64) | u[0];
97 *hi = ((u128)u[3] << 64) | u[2];
98#endif
99}
100
101/* a^2 -> (hi, lo):交叉积单次乘法后整体加倍(3 乘法平方) */
102static inline void sqr_128(u128 a, u128 *hi, u128 *lo) {
103#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
104 ulong a0 = _u128low(a), a1 = _u128high(a);
105 u128 p0 = (u128)a0 * a0;
106 u128 m = (u128)a0 * a1; /* 交叉积,加倍后 129 位 */
107 u128 p1 = (u128)a1 * a1;
108 u128 ml = m << 1;
109 u128 mh = m >> 127; /* 加倍进位(0/1),属 hi 的第 64 位 */
110 u128 l = (ml << 64) + p0;
111 u128 cl = l < p0;
112 *lo = l;
113 *hi = p1 + (ml >> 64) + cl + (mh << 64);
114#else
115 ulong u[4];
116 _usqr128to256_(_u128high(a), _u128low(a), u);
117 *lo = ((u128)u[1] << 64) | u[0];
118 *hi = ((u128)u[3] << 64) | u[2];
119#endif
120}
121
122/* REDC:r = (T + q*n)/B^2,T = thi*B^2 + tlo < n*B^2。n 接近 B^2 时和
123 可达 129 位,回绕进位下按模 2^128 回绕减 n 恰为真值且已 < n */
124static inline u128 mont2_redc(u128 thi, u128 tlo, u128 n, u128 ninv) {
125#if defined(LMMP_ASM_ARM64)
126 u128 q = tlo * ninv; /* u128 截断乘即 mod B^2 */
127 u128 qh, ql;
128 mul_128(q, n, &qh, &ql);
129 ulong t0 = _u128low(tlo), t1 = _u128high(tlo);
130 ulong p0 = _u128low(ql), p1 = _u128high(ql);
131 ulong k0 = (t0 + p0) < t0; /* lo 低 limb 进位(lo 值本身无消费者) */
132 ulong l1 = t1 + p1;
133 ulong k1 = l1 < t1;
134 l1 += k0;
135 k1 |= l1 < k0;
136 ulong h0 = _u128low(thi) + _u128low(qh);
137 ulong j0 = h0 < _u128low(qh);
138 h0 += k1;
139 j0 |= h0 < k1;
140 ulong h1 = _u128high(thi) + _u128high(qh);
141 ulong j1 = h1 < _u128high(qh);
142 h1 += j0;
143 j1 |= h1 < j0;
144 ulong n0 = _u128low(n), n1 = _u128high(n);
145 if (j1 || (h1 > n1) || (h1 == n1 && h0 >= n0)) {
146 ulong bw = h0 < n0; /* 借位跨 limb 传播 */
147 h0 -= n0;
148 h1 -= n1 + bw; /* j1 分支下回绕即真值 */
149 }
150 return ((u128)h1 << 64) | h0;
151#else
152 u128 q = tlo * ninv; /* u128 截断乘即 mod B^2 */
153 u128 qh, ql, lo, hi, c, c1, c2;
154 mul_128(q, n, &qh, &ql);
155 lo = tlo + ql;
156 c = lo < tlo;
157 hi = thi + qh;
158 c1 = hi < thi;
159 hi += c;
160 c2 = c && hi == 0;
161 if (c1 | c2)
162 hi -= n;
163 else if (hi >= n)
164 hi -= n;
165 return hi;
166#endif
167}
168
169static inline u128 mont2_sqr(u128 a, u128 n, u128 ninv) {
170 u128 h, l;
171 sqr_128(a, &h, &l);
172 return mont2_redc(h, l, n, ninv);
173}
174
175static inline u128 mont2_mul_2(u128 a, u128 b, u128 n, u128 ninv) {
176 u128 h, l;
177 mul_128(a, b, &h, &l);
178 return mont2_redc(h, l, n, ninv);
179}
180
181/* REDC(a*b),b 为单 limb:a 为蒙域剩余时结果出域(a_plain*b),
182 专用于转域 */
183static inline u128 mont2_redc_mul_1(u128 a, ulong b, u128 n, u128 ninv) {
184 /* T = a*b < 2^192:h<<64 回绕丢弃的高位入 thi,低位和的进位并入 thi */
185 u128 lo = (u128)_u128low(a) * b;
186 u128 h = (u128)_u128high(a) * b;
187 u128 tlo = lo + (h << 64);
188 return mont2_redc((h >> 64) + (tlo < lo), tlo, n, ninv);
189}
190
191/* 转蒙域:x*R mod n = REDC(x*R2),R2 = B^4 mod n(x 为小整数) */
192static inline u128 mont2_to_mont1(ulong x, u128 R2, u128 n, u128 ninv) {
193 return mont2_redc_mul_1(R2, x, n, ninv);
194}
195
196static inline u128 mont2_to_mont2(u128 a, u128 R2, u128 n, u128 ninv) {
197 return mont2_mul_2(a, R2, n, ninv);
198}
199
200/* 蒙域加倍/模减/模取负(操作数 < n,结果 < n):
201 129 位和的回绕进位下,回绕减 n 恰为真值且已 < n */
202static inline u128 mont2_dbl(u128 a, u128 n) {
203 u128 s = a + a;
204 if (s < a)
205 s -= n;
206 else if (s >= n)
207 s -= n;
208 return s;
209}
210
211static inline u128 mont2_sub(u128 a, u128 b, u128 n) {
212 u128 r = a - b;
213 if (a < b) r += n;
214 return r;
215}
216
217static inline u128 mont2_neg(u128 a, u128 n) {
218 return a == 0 ? a : n - a;
219}
220
221/* u128 有效位数(最高位以下位数),x != 0 */
222static inline int bitlen_2(u128 x) {
223 if (_u128high(x) != 0) return 128 - lmmp_leading_zeros_(_u128high(x));
224 return 64 - lmmp_leading_zeros_(_u128low(x));
225}
226
227/* n - 1 = d * 2^t(d 奇);n + 1 同型 */
228static inline u128 factor_2adic(u128 x, slong *t) {
229 if (_u128low(x) == 0) {
230 *t = 64 + lmmp_tailing_zeros_(_u128high(x));
231 return (u128)_u128high(x) >> (*t - 64);
232 }
233 *t = lmmp_tailing_zeros_(_u128low(x));
234 return x >> *t;
235}
236
237/* (b|A) 二进制算法:A 奇,b < A(移位/比较/减法,几次迭代) */
238static inline int jacobi_small(ulong b, ulong A) {
239 int sign = 1;
240 if (b == 0) return 0;
241 for (;;) {
242 int tz = lmmp_tailing_zeros_(b);
243 b >>= tz;
244 if ((tz & 1) && ((A & 7) == 3 || (A & 7) == 5)) sign = -sign;
245 if (b == 1) return sign;
246 if (b < A) {
247 ulong s = b;
248 b = A;
249 A = s;
250 if ((b & 3) == 3 && (A & 3) == 3) sign = -sign;
251 }
252 b -= A;
253 if (b == 0) return 0;
254 }
255}
256
257/*
258 (±Dabs|n):Dabs 奇(uint 范围),n 128 位奇。n 以双 limb 模乘链折叠
259 (r = (r*(B mod A) + limb) mod A,全程 64 位),再经二次互反律
260 (A|n) = (n|A)*(-1)^(((A-1)/2)((n-1)/2)) 归结到 jacobi_small;
261 D 为负时乘 (-1|n) 因子。gcd(|D|,n)>1 返回 0
262*/
263static inline int jacobi_D(uint Dabs, int Dneg, u128 n) {
264 ulong A = Dabs;
265 ulong Bm = (ulong)-1 % A + 1;
266 ulong b;
267 int sign = 1;
268 if (Bm >= A) Bm -= A; /* Bm = 2^64 mod A */
269 b = _u128high(n) % A;
270 b = (b * Bm + _u128low(n) % A) % A;
271 if ((A & 3) == 3 && (_u128low(n) & 3) == 3) sign = -sign;
272 sign *= jacobi_small(b, A);
273 if (sign == 0) return 0;
274 if (Dneg && (_u128low(n) & 3) == 3) sign = -sign;
275 return sign;
276}
277
278/* 二次探测第二阶段:y = b^d 已得,检查 y ∈ {1, n-1} 或 y^(2^j) = n-1
279 (0 < j < t)。one/m_1 均为蒙域剩余 */
280static inline int mont2_sprp_stage2(u128 y, slong t, u128 one, u128 m_1, u128 n, u128 ninv) {
281 if (y == one || y == m_1) return 1;
282 for (t--; t > 0; t--) {
283 y = mont2_sqr(y, n, ninv);
284 if (y == m_1) return 1;
285 }
286 return 0;
287}
288
289/*
290 基底 2 专用幂 y = 2^d(蒙域):指数最高 k 位(k <= 6)对应的 2^t
291 (t < 2^6,普通域一次移位)经一次 REDC 跳启动,其后逐位平方,
292 逢 1 蒙域加倍。ebits = d 的有效位数
293*/
294static u128 mont2_powmod_2_(u128 d, int ebits, u128 R2, u128 n, u128 ninv) {
295 int k = ebits > 6 ? 6 : ebits;
296 int bit;
297 u128 v = mont2_to_mont1((ulong)1 << (ulong)(d >> (ebits - k)), R2, n, ninv);
298 for (bit = ebits - k - 1; bit >= 0; bit--) {
299 v = mont2_sqr(v, n, ninv);
300 if ((d >> bit) & 1) v = mont2_dbl(v, n);
301 }
302 return v;
303}
304
305/*
306 模 n in (B, phi13] 的非蒙域 sloppy 算术:minv = floor(B^3/n),3-limb
307 中间积 x 的近似商
308
309 q' = mulhi_sloppy(floor(x/B), minv) 满足 q - 5 <= q' <= q
310
311 (q = floor(x/n):截断倒数欠 4 + mulhi 丢交叉低位欠 1;上侧
312 X*minv <= x*B^2/n 保证),故 0 <= x - q'*n < 6n 为非规范剩余:
313 - 双 limb 截断算术对它精确(真值非负且 6n < 2^128,回绕减丢的
314 借位恰好无影响);q'*n 的高半整体丢弃同理;
315 - bit=1 的小基底乘完全免约简:y*b < 6n*41 = 246n < 2^128 装下,
316 下一平方 (246n)^2 < 2^182 < B^3 仍在 3-limb 窗内
317 (_usqr128to192_ 契约 a < 2^96:246n < 2^91 满足);
318 - 基底 2 逢 1 双倍:2y < 12n < 2^128 无回绕。
319 链尾经 reduce2_precise 规范化后 stage2 在普通域比较 1 / n-1。
320*/
321
322/* minv = floor(B^3/n):2^192 除以 n 的商(lmmp_div_2_ 自带归一化,
323 numb 出参收余数弃用) */
324static void ll_small_preinv(u128 *minv, u128 n) {
325 ulong q[3], nn[4] = {0, 0, 0, 1}, d[2];
326
327 _u128store(d, n);
328 lmmp_div_2_(q, nn, 4, d);
329 *minv = ((u128)q[1] << 64) | q[0];
330}
331
332/* 平方 + sloppy 归约到非规范剩余 < 6n */
333static inline void ll_small_sqrmod_sloppy(
335 ulong n1, ulong n0, ulong minv1, ulong minv0
336) {
337 ulong s[3], q[2];
338 u128 t;
339
341 _umulhi128_sloppy_(s[2], s[1], minv1, minv0, q);
342 t = _umul128to128_(q[1], q[0], n1, n0);
343 _sub_ddmmss(*r1, *r0, s[1], s[0], _u128high(t), _u128low(t));
344}
345
346/* 平方 + 归约到规范剩余 [0,n)(stage2 等值比较用):sloppy 后条件减
347 收尾,剩余 < 6n 至多 5 次 */
348static inline void ll_small_sqrmod(
350 ulong n1, ulong n0, ulong minv1, ulong minv0
351) {
352 ll_small_sqrmod_sloppy(r1, r0, a1, a0, n1, n0, minv1, minv0);
353 while (*r1 > n1 || (*r1 == n1 && *r0 >= n0))
354 _sub_ddmmss(*r1, *r0, *r1, *r0, n1, n0);
355}
356
357/* 2-limb 值规范化到 [0,n):q0 = hi(x1*minv1) 是 floor(x/n) 的下偏
358 近似(q0 <= q 保证减法非负;欠至多 2 使条件减至多 2 次),
359 q0*n < 246n < 2^128 截断积即真值 */
360static inline void ll_small_reduce2_precise(ulong *r1, ulong *r0, ulong x1, ulong x0, ulong n1, ulong n0, ulong minv1) {
361 ulong t[2];
362
363 _umullo128x64_(n1, n0, _umul64to64hi_(x1, minv1), t);
364 _sub_ddmmss(x1, x0, x1, x0, t[1], t[0]);
365 while (x1 > n1 || (x1 == n1 && x0 >= n0))
366 _sub_ddmmss(x1, x0, x1, x0, n1, n0);
367 *r0 = x0;
368 *r1 = x1;
369}
370
371/* r = a*b 截断(小基底免约简乘,< 246n 装下即真值) */
372static inline void ll_small_mul1_(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong b) {
373 ulong t[2];
374
375 _umullo128x64_(a1, a0, b, t);
376 *r0 = t[0];
377 *r1 = t[1];
378}
379
380static void ll_small_2_powmod(ulong y[2], u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0) {
381 int k = ebits > 6 ? 6 : ebits;
382 int bit;
383 ulong r1 = 0, r0 = (ulong)1 << (ulong)(d >> (ebits - k));
384
385 for (bit = ebits - k - 1; bit >= 0; bit--) {
386 ll_small_sqrmod_sloppy(&r1, &r0, r1, r0, n1, n0, minv1, minv0);
387 if ((d >> bit) & 1) _add_ssaaaa(r1, r0, r1, r0, r1, r0);
388 }
389 ll_small_reduce2_precise(&y[1], &y[0], r1, r0, n1, n0, minv1);
390}
391
392/* 二次探测第二阶段(普通域规范剩余比较):y = b^d 已规范化 */
393static inline int ll_small_sprp_stage2(
394 ulong y1, ulong y0, slong t, ulong nm1_1, ulong nm1_0,
395 ulong n1, ulong n0, ulong minv1, ulong minv0
396) {
397 if ((y1 == 0 && y0 == 1) || (y1 == nm1_1 && y0 == nm1_0)) return 1;
398 for (t--; t > 0; t--) {
399 ll_small_sqrmod(&y1, &y0, y1, y0, n1, n0, minv1, minv0);
400 if (y1 == nm1_1 && y0 == nm1_0) return 1;
401 }
402 return 0;
403}
404
405/*
406 三基底交错幂 y1 = b1^d, y2 = b2^d, y3 = b3^d(非规范):指数顶部
407 3 bit 在普通域免归约计算 b^(1 b1 b2)(b <= 41,b^7 < 2^38 单
408 limb),其后逐位 sloppy 平方,逢 1 小基底免约简乘,链尾规范化。
409 ebits < 3(n-1 = 2^s 时 d = 1)退化为直接以 b 起步
410*/
412 ulong y1[2], ulong y2[2], ulong y3[2],
413 ulong b1, ulong b2, ulong b3, u128 d, int ebits,
414 ulong n1, ulong n0, ulong minv1, ulong minv0
415) {
416 ulong xr1 = 0, xr0, yr1 = 0, yr0, zr1 = 0, zr0;
417 int bit;
418
419 if (ebits >= 3) {
420 ulong bit1 = (ulong)(d >> (ebits - 2)) & 1;
421 ulong bit2 = (ulong)(d >> (ebits - 3)) & 1;
422
423 xr0 = b1 * b1;
424 yr0 = b2 * b2;
425 zr0 = b3 * b3;
426 if (bit1) {
427 xr0 *= b1;
428 yr0 *= b2;
429 zr0 *= b3;
430 }
431 xr0 = xr0 * xr0;
432 yr0 = yr0 * yr0;
433 zr0 = zr0 * zr0;
434 if (bit2) {
435 xr0 *= b1;
436 yr0 *= b2;
437 zr0 *= b3;
438 }
439 bit = ebits - 4;
440 } else {
441 xr0 = b1;
442 yr0 = b2;
443 zr0 = b3;
444 bit = ebits - 2;
445 }
446
447 for (; bit >= 0; bit--) {
448 ll_small_sqrmod_sloppy(&xr1, &xr0, xr1, xr0, n1, n0, minv1, minv0);
449 ll_small_sqrmod_sloppy(&yr1, &yr0, yr1, yr0, n1, n0, minv1, minv0);
450 ll_small_sqrmod_sloppy(&zr1, &zr0, zr1, zr0, n1, n0, minv1, minv0);
451 if ((d >> bit) & 1) {
452 ll_small_mul1_(&xr1, &xr0, xr1, xr0, b1);
453 ll_small_mul1_(&yr1, &yr0, yr1, yr0, b2);
454 ll_small_mul1_(&zr1, &zr0, zr1, zr0, b3);
455 }
456 }
457 ll_small_reduce2_precise(&y1[1], &y1[0], xr1, xr0, n1, n0, minv1);
458 ll_small_reduce2_precise(&y2[1], &y2[0], yr1, yr0, n1, n0, minv1);
459 ll_small_reduce2_precise(&y3[1], &y3[0], zr1, zr0, n1, n0, minv1);
460}
461
462/* 双基底交错幂(三链变体减一链,末轮恰剩两基底时用之——勿以重复
463 基底凑三链,重复链吃回台阶收益) */
465 ulong y1[2], ulong y2[2], ulong b1, ulong b2, u128 d, int ebits,
466 ulong n1, ulong n0, ulong minv1, ulong minv0
467) {
468 ulong xr1 = 0, xr0, yr1 = 0, yr0;
469 int bit;
470
471 if (ebits >= 3) {
472 ulong bit1 = (ulong)(d >> (ebits - 2)) & 1;
473 ulong bit2 = (ulong)(d >> (ebits - 3)) & 1;
474
475 xr0 = b1 * b1;
476 yr0 = b2 * b2;
477 if (bit1) {
478 xr0 *= b1;
479 yr0 *= b2;
480 }
481 xr0 = xr0 * xr0;
482 yr0 = yr0 * yr0;
483 if (bit2) {
484 xr0 *= b1;
485 yr0 *= b2;
486 }
487 bit = ebits - 4;
488 } else {
489 xr0 = b1;
490 yr0 = b2;
491 bit = ebits - 2;
492 }
493
494 for (; bit >= 0; bit--) {
495 ll_small_sqrmod_sloppy(&xr1, &xr0, xr1, xr0, n1, n0, minv1, minv0);
496 ll_small_sqrmod_sloppy(&yr1, &yr0, yr1, yr0, n1, n0, minv1, minv0);
497 if ((d >> bit) & 1) {
498 ll_small_mul1_(&xr1, &xr0, xr1, xr0, b1);
499 ll_small_mul1_(&yr1, &yr0, yr1, yr0, b2);
500 }
501 }
502 ll_small_reduce2_precise(&y1[1], &y1[0], xr1, xr0, n1, n0, minv1);
503 ll_small_reduce2_precise(&y2[1], &y2[0], yr1, yr0, n1, n0, minv1);
504}
505
506/* 确定性奇基底 MR(1.5-limb,基底 2 已由调用方做完):nb 个基底
507 {3,5,...} 三链交错。全部通过返回 1 */
508static int ll_small_is_prime_mr(u128 n, u128 minv, u128 d, int ebits, slong t, int nb) {
509 static const uchar bases[12] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
510 ulong n1 = _u128high(n), n0 = _u128low(n);
511 ulong minv1 = _u128high(minv), minv0 = _u128low(minv);
512 ulong nm1[2], y1[2], y2[2], y3[2];
513 int j;
514
515 _sub_ddmmss(nm1[1], nm1[0], n1, n0, 0, 1);
516
517 for (j = 0; j + 3 <= nb; j += 3) {
518 ll_small_powmod_3_(y1, y2, y3, bases[j], bases[j + 1], bases[j + 2], d, ebits,
519 n1, n0, minv1, minv0);
520 if (!ll_small_sprp_stage2(y1[1], y1[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
521 if (!ll_small_sprp_stage2(y2[1], y2[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
522 if (!ll_small_sprp_stage2(y3[1], y3[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
523 }
524 if (nb == 11) {
525 ll_small_powmod_2ch_(y1, y2, bases[9], bases[10], d, ebits, n1, n0, minv1, minv0);
526 if (!ll_small_sprp_stage2(y1[1], y1[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
527 if (!ll_small_sprp_stage2(y2[1], y2[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
528 }
529 return 1;
530}
531
532static inline int is_square_2(u128 n) {
533 ulong hi = _u128high(n), lo = _u128low(n);
534 ulong src[2], rr[2], r;
535 lmmp_debug_assert(hi != 0);
536 int nsh = lmmp_leading_zeros_(hi) / 2;
537 if (nsh) {
538 ulong limbs[2] = {lo, hi};
539 lmmp_shl_(src, limbs, 2, 2 * nsh);
540 } else {
541 src[0] = lo;
542 src[1] = hi;
543 }
544 r = lmmp_sqrt_2_(rr, src) >> nsh;
545 return (u128)r * r == n;
546}
547
548/*
549 ============ 强 Lucas-Selfridge 测试(V-only 阶梯) ============
550
551 Selfridge 方法 A:P = 1,Q = (1-D)/4,D 取 5, -7, 9, -11, ... 中
552 首个 (D|n) = -1 者;A* 脆弱区绕行——首候选 D=5 命中时改参数化
553 (P,Q)=(1,1/5)((5,5) 的 V/P^m 归一化像),使全部输入脱离 Q≡±1
554 脆弱区(见下方 Qm 构造处注释)。V 阶梯递推(蒙域):
555 V_{2k} = V_k^2 - 2Q^k
556 V_{2k+1} = V_k*V_{k+1} - Q^k
557 V_{2k+2} = V_{k+1}^2 - 2Q^{k+1}
558 Q 链同步阶梯:(Q^k, Q^{k+1}) --bit0--> ((Q^k)^2, (Q^k)^2*Q),
559 --bit1--> (Q^k*Q^{k+1}, (Q^{k+1})^2)。
560 判据(与标准 U/V 强 Lucas 测试精确一致):
561 U_d = 0,或 V_{d*2^r} = 0(0 <= r < s),d*2^s = n+1。
562 U_d = 0 经 P=1 恒等式 D*U_d = 2V_{d+1} - V_d 转为 2V_{d+1} = V_d 检出
563 (阶梯末态 Vk1 = V_{d+1};D 搜索保证 gcd(D,n)=1,等价精确成立,含平方
564 因子的 n 亦然;旧判据 V_d^2 = 4Q^d 仅在 n 无平方因子时等价,对
565 p^2*q 型 n 会多接受)。判据命中后再叠加 BFW 两项强化检查(见尾注),
566 素数接受集不变、合数严格多拒。通过返回 1;判定合数(含 gcd(|D|,n)>1)返回 0
567*/
568static int mont2_lucas_strong_(u128 n, u128 ninv, u128 R2) {
569 u128 one, Qm, Qk, Qk1, Vk, Vk1, d, u, w, r;
570 slong s, i;
571 int j, Dneg;
572 uint Dabs, Qabs;
573
574 /* 寻找 D:非完全平方的 n 其 Jacobi 特征非平凡,序列中必存在
575 (D|n) = -1(全部为 +1 当且仅当 n 为完全平方),搜索必然终止,
576 不设上界;素数的最小 |D| 经验上 < 2*log2(n)^2 量级。完全平方数
577 是唯一不终止情形,经 17 处的延迟检测排除(平方检测走库内
578 sqrt_2_ 快速路径,放在少数次未命中之后,不进常见路径)——固定
579 小上界(如旧版 201)不可行:least |D| 随素数规模按 ~2^-k 几何
580 衰减,区间 [SWbound, 2^128) 内 least |D| > 201 的素数约 2^32 个,
581 上界会把它们误判为合数 */
582 Dabs = 5;
583 Dneg = 0;
584 for (;;) {
585 j = jacobi_D(Dabs, Dneg, n);
586 if (j == 0) return 0;
587 if (j == -1) break;
588 Dabs += 2;
589 Dneg ^= 1;
590 if (Dabs == 17 && is_square_2(n)) return 0;
591 }
592
593 /* Q = (1-D)/4,可为负;d*2^s = n+1(n 奇,n+1 偶) */
594 Qabs = Dneg ? (Dabs + 1) / 4 : (Dabs - 1) / 4;
595 d = factor_2adic(n + 1, &s);
596
597 one = mont2_to_mont1(1, R2, n, ninv);
598 if (Dabs == 5 && !Dneg) {
599 /* A* 脆弱区绕行(归一化形):首候选 D=5 命中 (5|n)=-1 时
600 Selfridge 参数 (P,Q)=(1,-1) 落 BFW 实证 Q≡±1 脆弱区(伪素数
601 过代表,且 Q-Euler 检查 Q^{(n+1)/2}=±Q 恒真空转),改用等价
602 参数化 (P',Q')=(1,1/5):V'_m = V_m/P^m 把 A* 的 (5,5) 等距
603 映射到 P=1 形(D' = 1-4Q' = 1/5,(D'|n) = (5|n) = -1 仍
604 合法),阶梯/stage2/末检全部公式零改动。q = 5^{-1} mod n
605 闭式:k*(n mod 5) = 4 (mod 5) 使 k*n+1 被 5 整除、真商 < n,
606 商经 mod 2^128 乘 5 的 2^128 幂逆恢复(2^64 ≡ 1 (mod 5)) */
607 static const uchar kt[5] = {0, 4, 2, 3, 1};
608 static const u128 inv5 =
609 (((u128)0xcccccccccccccccc) << 64) | 0xcccccccccccccccd; /* 5^{-1} mod 2^128 */
610 ulong r5 = (_u128low(n) % 5 + _u128high(n) % 5) % 5;
611 u128 q = (((u128)kt[r5]) * n + 1) * inv5;
612 Qm = mont2_to_mont2(q, R2, n, ninv);
613 } else {
614 Qm = mont2_to_mont1(Qabs, R2, n, ninv);
615 if (!Dneg) Qm = mont2_neg(Qm, n);
616 }
617
618 /* 阶梯初态 k=1:(V_1, V_2, Q^1, Q^2) = (1, 1-2Q, Q, Q^2) */
619 Vk = one;
620 Vk1 = mont2_sub(one, mont2_dbl(Qm, n), n);
621 Qk = Qm;
622 Qk1 = mont2_sqr(Qm, n, ninv);
623
624 for (i = bitlen_2(d) - 2; i >= 0; i--) {
625 if ((d >> i) & 1) {
626 u = mont2_mul_2(Vk, Vk1, n, ninv); /* V_{2k+1} 主项 */
627 w = mont2_sqr(Vk1, n, ninv); /* V_{2k+2} 主项 */
628 r = mont2_dbl(Qk1, n);
629 Vk = mont2_sub(u, Qk, n);
630 Vk1 = mont2_sub(w, r, n);
631 Qk = mont2_mul_2(Qk, Qk1, n, ninv); /* Q^{2k+1} */
632 Qk1 = mont2_sqr(Qk1, n, ninv); /* Q^{2k+2} */
633 } else {
634 u = mont2_sqr(Vk, n, ninv); /* V_{2k} 主项 */
635 w = mont2_mul_2(Vk, Vk1, n, ninv); /* V_{2k+1} 主项 */
636 r = mont2_dbl(Qk, n);
637 Vk = mont2_sub(u, r, n);
638 Vk1 = mont2_sub(w, Qk, n);
639 w = mont2_sqr(Qk, n, ninv); /* Q^{2k} */
640 Qk1 = mont2_mul_2(w, Qm, n, ninv); /* Q^{2k+1} */
641 Qk = w;
642 }
643 }
644
645 /* 判据:V_d = 0(r=0),或 U_d = 0,或 V_{d*2^r} = 0(0 < r < s)。
646 U_d = 0 经 D*U_d = 2V_{d+1} - V_d 检出(末态 Vk1 = V_{d+1})。
647 BFW 强化(Baillie-Fiori-Wagstaff 2021):命中不早退,链尾统一
648 追加 vpsp 与 Q-Euler 两检查——素数经 Frobenius(α^{n+1}=αβ=Q)
649 与 Euler 判据必然全过(vpsp@10^15 仅 5 个反例且与 spsp(2)/slpsp
650 全不相交,只拦假想的 BPSW 反例),正常完成路径零额外 REDC,
651 早退路径平均多 ~1-2 次链尾 sqr */
652 int hit = (Vk == 0) | (mont2_dbl(Vk1, n) == Vk);
653 u = mont2_sqr(Vk, n, ninv);
654 for (s--; s > 0; s--) {
655 r = mont2_dbl(Qk, n);
656 Vk = mont2_sub(u, r, n); /* V_{2d} = V_d^2 - 2Q^d(复用 u = V_d^2) */
657 Qk = mont2_sqr(Qk, n, ninv);
658 u = mont2_sqr(Vk, n, ninv);
659 if (Vk == 0) hit = 1;
660 }
661 if (!hit) return 0;
662 /* 末态 u = V_{(n+1)/2}^2,Qk = Q^{(n+1)/2}(s=1 时阶梯末态同型)。
663 vpsp:V_{n+1} = u - 2Qk ≡ 2Q;Q-Euler:Qk = Q*(Q|n) ∈ {Qm,-Qm} */
664 if (mont2_sub(u, mont2_dbl(Qk, n), n) != mont2_dbl(Qm, n)) return 0;
665 if (Qk != Qm && Qk != mont2_neg(Qm, n)) return 0;
666 return 1;
667}
668
669/* 蒙域参数预计算:ninv = -n^(-1) mod B^2,R2 = B^4 mod n
670 ([nn,5] = 2^256 除以 n 的余数) */
671static void mont2_preinv(u128 *ninv, u128 *R2, u128 n) {
672 ulong i2[2], q[4], nn[5] = {0, 0, 0, 0, 1};
673 ulong n2[2];
674
675 i2[0] = _u128low(n);
676 i2[1] = _u128high(n);
677 n2[0] = i2[0];
678 n2[1] = i2[1];
679 lmmp_binvert_2_(i2, i2);
680 i2[0] = -i2[0];
681 i2[1] = ~i2[1] + (i2[0] == 0);
682 lmmp_div_2_(q, nn, 5, n2);
683 *ninv = ((u128)i2[1] << 64) | i2[0];
684 *R2 = ((u128)n2[1] << 64) | n2[0];
685}
686
688 u128 n, nm1, d;
689 slong t;
690 int ebits;
691
692 n = ((u128)hi << 64) | lo;
693 nm1 = n - 1;
694 d = factor_2adic(nm1, &t);
695 ebits = bitlen_2(d);
696
697 /* SWbound = psi_13 (Sorenson-Webster):确定性基底档走 1.5-limb
698 sloppy 算术(返回 1 = 确定素数) */
699 if (n < ((((u128)0x2be69) << 64) | 0x51adc5b22410a5fd)) {
700 ulong minv1, minv0, nm1_1, nm1_0, y[2];
701 u128 minv;
702
703 ll_small_preinv(&minv, n);
704 minv0 = _u128low(minv);
705 minv1 = _u128high(minv);
706 _sub_ddmmss(nm1_1, nm1_0, hi, lo, 0, 1);
707
708 ll_small_2_powmod(y, d, ebits, hi, lo, minv1, minv0);
709 if (!ll_small_sprp_stage2(y[1], y[0], t, nm1_1, nm1_0, hi, lo, minv1, minv0)) return 0;
710
711 /* psi_12 台阶:n < psi_12 时 12 基底(2 + {3..37})已确定 */
712 {
713 int nb = n >= ((((u128)0x437a) << 64) | 0xe92817f9fc85b7e5) ? 12 : 11;
714 return ll_small_is_prime_mr(n, minv, d, ebits, t, nb) ? 1 : 0;
715 }
716 }
717
718 /* BPSW 档(n >= psi_13,蒙域:V·V 与 Q 链全宽乘无 1.5-limb 窗口) */
719 {
720 u128 ninv, R2, one, m_1, y;
721
722 mont2_preinv(&ninv, &R2, n);
723 one = mont2_to_mont1(1, R2, n, ninv);
724 m_1 = mont2_to_mont2(nm1, R2, n, ninv);
725
726 y = mont2_powmod_2_(d, ebits, R2, n, ninv);
727 if (!mont2_sprp_stage2(y, t, one, m_1, n, ninv)) return 0;
728
729 return mont2_lucas_strong_(n, ninv, R2) ? 2 : 0;
730 }
731}
732
734 lmmp_param_assert(hi > 0);
735 if ((lo & 1) == 0) return 0;
736 return is2_notrial_i_(lo, hi);
737}
738
740 lmmp_param_assert(hi > 0);
741 slong i;
742
743 if ((lo & 1) == 0) return 0;
744
745#define ainv0 ll_trial_primes[i][0]
746#define ainv1 ll_trial_primes[i][1]
747#define abound0 ll_trial_primes[i][2]
748#define abound1 ll_trial_primes[i][3]
749#define binv0 ll_trial_primes[i + 1][0]
750#define binv1 ll_trial_primes[i + 1][1]
751#define bbound0 ll_trial_primes[i + 1][2]
752#define bbound1 ll_trial_primes[i + 1][3]
753
754 if (hi < FAST_TRIAL_BOUND) {
755 for (i = 0; i < 32; i += 2) {
756 u128 a = _umul128to128_(hi, lo, ainv1, ainv0);
757 u128 b = _umul128to128_(hi, lo, binv1, binv0);
758 if ((_u128high(a) < abound1) | (_u128high(b) < bbound1)) return 0;
759 }
760 } else {
761 for (i = 0; i < 32; i += 2) {
762 u128 a = _umul128to128_(hi, lo, ainv1, ainv0);
763 u128 b = _umul128to128_(hi, lo, binv1, binv0);
764 if (ll_le(a, ((u128)abound1 << 64) | abound0) | ll_le(b, ((u128)bbound1 << 64) | bbound0))
765 return 0;
766 }
767 }
768#undef ainv0
769#undef ainv1
770#undef abound0
771#undef abound1
772#undef binv0
773#undef binv1
774#undef bbound0
775#undef bbound1
776
777 return is2_notrial_i_(lo, hi);
778}
#define k
#define A
#define lmmp_leading_zeros_
#define lmmp_tailing_zeros_
#define bbound1
#define FAST_TRIAL_BOUND
static const ulong ll_trial_primes[32][4]
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void ll_small_powmod_2ch_(ulong y1[2], ulong y2[2], ulong b1, ulong b2, u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static int mont2_sprp_stage2(u128 y, slong t, u128 one, u128 m_1, u128 n, u128 ninv)
static void mul_128(u128 a, u128 b, u128 *hi, u128 *lo)
static void ll_small_reduce2_precise(ulong *r1, ulong *r0, ulong x1, ulong x0, ulong n1, ulong n0, ulong minv1)
static void ll_small_sqrmod_sloppy(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong n1, ulong n0, ulong minv1, ulong minv0)
static u128 mont2_redc_mul_1(u128 a, ulong b, u128 n, u128 ninv)
static u128 mont2_powmod_2_(u128 d, int ebits, u128 R2, u128 n, u128 ninv)
static int jacobi_D(uint Dabs, int Dneg, u128 n)
#define binv1
static int ll_small_sprp_stage2(ulong y1, ulong y0, slong t, ulong nm1_1, ulong nm1_0, ulong n1, ulong n0, ulong minv1, ulong minv0)
static int is2_notrial_i_(mp_limb_t lo, mp_limb_t hi)
#define ainv0
static u128 mont2_dbl(u128 a, u128 n)
static int is_square_2(u128 n)
static void sqr_128(u128 a, u128 *hi, u128 *lo)
#define abound1
static int ll_le(u128 a, u128 b)
static void mont2_preinv(u128 *ninv, u128 *R2, u128 n)
static int mont2_lucas_strong_(u128 n, u128 ninv, u128 R2)
static u128 mont2_mul_2(u128 a, u128 b, u128 n, u128 ninv)
#define binv0
static int bitlen_2(u128 x)
static void ll_small_powmod_3_(ulong y1[2], ulong y2[2], ulong y3[2], ulong b1, ulong b2, ulong b3, u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static u128 mont2_redc(u128 thi, u128 tlo, u128 n, u128 ninv)
static u128 mont2_neg(u128 a, u128 n)
static void ll_small_mul1_(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong b)
static int jacobi_small(ulong b, ulong A)
static u128 mont2_to_mont2(u128 a, u128 R2, u128 n, u128 ninv)
static u128 mont2_sub(u128 a, u128 b, u128 n)
static u128 mont2_sqr(u128 a, u128 n, u128 ninv)
#define ainv1
static void ll_small_2_powmod(ulong y[2], u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
#define bbound0
static void ll_small_preinv(u128 *minv, u128 n)
static u128 mont2_to_mont1(ulong x, u128 R2, u128 n, u128 ninv)
#define abound0
static int ll_small_is_prime_mr(u128 n, u128 minv, u128 d, int ebits, slong t, int nb)
static u128 factor_2adic(u128 x, slong *t)
static void ll_small_sqrmod(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong n1, ulong n0, ulong minv1, ulong minv0)
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_NOINLINE
定义 lmmp.h:216
#define lmmp_param_assert(x)
定义 lmmp.h:509
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
static void _umulhi128_sloppy_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[2])
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static void _umullo128x64_(uint64_t a_high, uint64_t a_low, uint64_t b, uint64_t rr[2])
static void _usqr128to192_(uint64_t a_high, uint64_t a_low, uint64_t rr[3])
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)
#define _add_ssaaaa(sh, sl, ah, al, bh, bl)
static void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4])
#define b0
#define b1
#define a0
#define a1
#define r1
#define r0
#define b2
#define t
#define s
#define n
#define b3
#define r5
#define lo
#define c1
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
int lmmp_is_prime_2_notrial_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数(无试除法)
uint32_t uint
定义 numth.h:38
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
int64_t slong
定义 numth.h:41
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
uint64_t ulong
定义 numth.h:39