36 { 0xaaaaaaaaaaaaaaab, 0xaaaaaaaaaaaaaaaa, 0x5555555555555555, 0x5555555555555555 },
37 { 0xcccccccccccccccd, 0xcccccccccccccccc, 0x3333333333333333, 0x3333333333333333 },
38 { 0x6db6db6db6db6db7, 0xb6db6db6db6db6db, 0x4924924924924924, 0x2492492492492492 },
39 { 0x2e8ba2e8ba2e8ba3, 0xa2e8ba2e8ba2e8ba, 0x745d1745d1745d17, 0x1745d1745d1745d1 },
40 { 0x4ec4ec4ec4ec4ec5, 0xc4ec4ec4ec4ec4ec, 0x3b13b13b13b13b13, 0x13b13b13b13b13b1 },
41 { 0xf0f0f0f0f0f0f0f1, 0xf0f0f0f0f0f0f0f0, 0x0f0f0f0f0f0f0f0f, 0x0f0f0f0f0f0f0f0f },
42 { 0x86bca1af286bca1b, 0xbca1af286bca1af2, 0xe50d79435e50d794, 0x0d79435e50d79435 },
43 { 0xd37a6f4de9bd37a7, 0x4de9bd37a6f4de9b, 0x42c8590b21642c85, 0x0b21642c8590b216 },
44 { 0x34f72c234f72c235, 0xc234f72c234f72c2, 0xd3dcb08d3dcb08d3, 0x08d3dcb08d3dcb08 },
45 { 0xef7bdef7bdef7bdf, 0xdef7bdef7bdef7bd, 0x8421084210842108, 0x0842108421084210 },
46 { 0x14c1bacf914c1bad, 0xc1bacf914c1bacf9, 0x5306eb3e45306eb3, 0x06eb3e45306eb3e4 },
47 { 0x8f9c18f9c18f9c19, 0x18f9c18f9c18f9c1, 0x63e7063e7063e706, 0x063e7063e7063e70 },
48 { 0x82fa0be82fa0be83, 0xbe82fa0be82fa0be, 0xf417d05f417d05f4, 0x05f417d05f417d05 },
49 { 0x51b3bea3677d46cf, 0x3677d46cefa8d9df, 0x882b9310572620ae, 0x0572620ae4c415c9 },
50 { 0x21cfb2b78c13521d, 0x13521cfb2b78c135, 0x4873ecade304d487, 0x04d4873ecade304d },
51 { 0xcbeea4e1a08ad8f3, 0x8f2fba9386822b63, 0x15b1e5f75270d045, 0x0456c797dd49c341 },
52 { 0x4fbcda3ac10c9715, 0x14fbcda3ac10c971, 0x4325c53ef368eb04, 0x04325c53ef368eb0 },
53 { 0xf0b7672a07a44c6b, 0xc2dd9ca81e9131ab, 0x40f4898d5f85bb39, 0x03d226357e16ece5 },
54 { 0x193d4bb7e327a977, 0x4f52edf8c9ea5dbf, 0x240e6c2b4481cd85, 0x039b0ad12073615a },
55 { 0x7e3f1f8fc7e3f1f9, 0x3f1f8fc7e3f1f8fc, 0x070381c0e070381c, 0x0381c0e070381c0e },
56 { 0x9b8b577e613716af, 0xd5df984dc5abbf30, 0xa5440cf6474a8819, 0x033d91d2a2067b23 },
57 { 0xa3784a062b2e43db, 0x2818acb90f6bf3a9, 0x6f0940c565c87b5f, 0x03159721ed7e7534 },
58 { 0xf47e8fd1fa3f47e9, 0xd1fa3f47e8fd1fa3, 0xc0b81702e05c0b81, 0x02e05c0b81702e05 },
59 { 0xa3a0fd5c5f02a3a1, 0x5f02a3a0fd5c5f02, 0xa0fd5c5f02a3a0fd, 0x02a3a0fd5c5f02a3 },
60 { 0x3a4c0a237c32b16d, 0xc32b16cfd7720f35, 0xc83cd4e930288df0, 0x0288df0cac5b3f5d },
61 { 0xdab7ec1dd3431b57, 0xd0c6d5bf60ee9a18, 0x88b2f392a409f116, 0x027c45979c95204f },
62 { 0x77a04c8f8d28ac43, 0xa2b10bf66e0e5aea, 0xdc1cb5d4ef40991f, 0x02647c69456217ec },
63 { 0xa6c0964fda6c0965, 0xc0964fda6c0964fd, 0x9b02593f69b02593, 0x02593f69b02593f6 },
64 { 0x90fdbc090fdbc091, 0xc090fdbc090fdbc0, 0x43f6f0243f6f0243, 0x0243f6f0243f6f02 },
65 { 0x7efdfbf7efdfbf7f, 0xbf7efdfbf7efdfbf, 0x0408102040810204, 0x0204081020408102 },
66 { 0x03e88cb3c9484e2b, 0xf82ee6986d6f63aa, 0x7f05dcd30dadec75, 0x01f44659e4a42715 },
67 { 0xe21a291c077975b9, 0x21a291c077975b8f, 0x701de5d6e3f8868a, 0x01de5d6e3f8868a4 },
73#define FAST_TRIAL_BOUND (MP_ULONG_MAX - 137)
75static inline int ll_le(u128 a, u128 b) {
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;
89 u128 l = (mid << 64) + p00;
92 *hi = p11 + (mid >> 64) + cl + (cm << 64);
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];
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;
107 u128 p1 = (u128)
a1 *
a1;
110 u128 l = (ml << 64) + p0;
113 *hi = p1 + (ml >> 64) + cl + (mh << 64);
117 *
lo = ((u128)u[1] << 64) | u[0];
118 *hi = ((u128)u[3] << 64) | u[2];
124static inline u128
mont2_redc(u128 thi, u128 tlo, u128
n, u128 ninv) {
125#if defined(LMMP_ASM_ARM64)
129 ulong t0 = _u128low(tlo), t1 = _u128high(tlo);
130 ulong p0 = _u128low(ql), p1 = _u128high(ql);
131 ulong k0 = (t0 + p0) < t0;
136 ulong h0 = _u128low(thi) + _u128low(qh);
137 ulong j0 = h0 < _u128low(qh);
140 ulong h1 = _u128high(thi) + _u128high(qh);
141 ulong j1 = h1 < _u128high(qh);
144 ulong n0 = _u128low(
n), n1 = _u128high(
n);
145 if (j1 || (h1 > n1) || (h1 == n1 && h0 >= n0)) {
150 return ((u128)h1 << 64) | h0;
153 u128 qh, ql,
lo, hi, c,
c1, c2;
185 u128
lo = (u128)_u128low(a) * b;
186 u128 h = (u128)_u128high(a) * b;
187 u128 tlo =
lo + (h << 64);
218 return a == 0 ? a :
n - a;
229 if (_u128low(x) == 0) {
231 return (u128)_u128high(x) >> (*
t - 64);
240 if (b == 0)
return 0;
244 if ((tz & 1) && ((
A & 7) == 3 || (
A & 7) == 5)) sign = -sign;
245 if (b == 1)
return sign;
250 if ((b & 3) == 3 && (
A & 3) == 3) sign = -sign;
253 if (b == 0)
return 0;
268 if (Bm >=
A) Bm -=
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;
273 if (sign == 0)
return 0;
274 if (Dneg && (_u128low(
n) & 3) == 3) sign = -sign;
281 if (y == one || y == m_1)
return 1;
282 for (
t--;
t > 0;
t--) {
284 if (y == m_1)
return 1;
295 int k = ebits > 6 ? 6 : ebits;
298 for (bit = ebits -
k - 1; bit >= 0; bit--) {
325 ulong q[3], nn[4] = {0, 0, 0, 1}, d[2];
329 *minv = ((u128)q[1] << 64) | q[0];
353 while (*
r1 > n1 || (*
r1 == n1 && *
r0 >= n0))
365 while (x1 > n1 || (x1 == n1 && x0 >= n0))
381 int k = ebits > 6 ? 6 : ebits;
385 for (bit = ebits -
k - 1; bit >= 0; bit--) {
397 if ((y1 == 0 && y0 == 1) || (y1 == nm1_1 && y0 == nm1_0))
return 1;
398 for (
t--;
t > 0;
t--) {
400 if (y1 == nm1_1 && y0 == nm1_0)
return 1;
416 ulong xr1 = 0, xr0, yr1 = 0, yr0, zr1 = 0, zr0;
447 for (; bit >= 0; bit--) {
451 if ((d >> bit) & 1) {
468 ulong xr1 = 0, xr0, yr1 = 0, yr0;
494 for (; bit >= 0; bit--) {
497 if ((d >> bit) & 1) {
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];
517 for (j = 0; j + 3 <= nb; j += 3) {
519 n1, n0, minv1, minv0);
533 ulong hi = _u128high(
n),
lo = _u128low(
n);
534 ulong src[2], rr[2], r;
545 return (u128)r * r ==
n;
569 u128 one, Qm, Qk, Qk1, Vk, Vk1, d, u, w, r;
586 if (j == 0)
return 0;
594 Qabs = Dneg ? (Dabs + 1) / 4 : (Dabs - 1) / 4;
598 if (Dabs == 5 && !Dneg) {
607 static const uchar kt[5] = {0, 4, 2, 3, 1};
608 static const u128 inv5 =
609 (((u128)0xcccccccccccccccc) << 64) | 0xcccccccccccccccd;
610 ulong r5 = (_u128low(
n) % 5 + _u128high(
n) % 5) % 5;
611 u128 q = (((u128)kt[
r5]) *
n + 1) * inv5;
624 for (i =
bitlen_2(d) - 2; i >= 0; i--) {
652 int hit = (Vk == 0) | (
mont2_dbl(Vk1,
n) == Vk);
654 for (
s--;
s > 0;
s--) {
659 if (Vk == 0) hit = 1;
665 if (Qk != Qm && Qk !=
mont2_neg(Qm,
n))
return 0;
672 ulong i2[2], q[4], nn[5] = {0, 0, 0, 0, 1};
676 i2[1] = _u128high(
n);
681 i2[1] = ~i2[1] + (i2[0] == 0);
683 *ninv = ((u128)i2[1] << 64) | i2[0];
684 *R2 = ((u128)n2[1] << 64) | n2[0];
692 n = ((u128)hi << 64) |
lo;
699 if (
n < ((((u128)0x2be69) << 64) | 0x51adc5b22410a5fd)) {
700 ulong minv1, minv0, nm1_1, nm1_0, y[2];
704 minv0 = _u128low(minv);
705 minv1 = _u128high(minv);
713 int nb =
n >= ((((u128)0x437a) << 64) | 0xe92817f9fc85b7e5) ? 12 : 11;
720 u128 ninv, R2, one, m_1, y;
735 if ((
lo & 1) == 0)
return 0;
743 if ((
lo & 1) == 0)
return 0;
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]
755 for (i = 0; i < 32; i += 2) {
758 if ((_u128high(a) <
abound1) | (_u128high(b) <
bbound1))
return 0;
761 for (i = 0; i < 32; i += 2) {
#define lmmp_leading_zeros_
#define lmmp_tailing_zeros_
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)
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)
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)
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)
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)
static void ll_small_2_powmod(ulong y[2], u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_preinv(u128 *minv, u128 n)
static u128 mont2_to_mont1(ulong x, u128 R2, u128 n, u128 ninv)
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)
#define lmmp_param_assert(x)
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
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
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])
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
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 位素数
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]))