78 else if (
lmmp_cmp_(dst, mc->m, mc->n) >= 0)
100 else if (
lmmp_cmp_(dst, mc->m, mc->n) >= 0)
117 while (dp[z] == 0) z++;
122 while (dn > 0 && dp[dn - 1] == 0) dn--;
204 sd->
d1 = (np[nn - 1] << sh) | (np[nn - 2] >> (
LIMB_BITS - sh));
205 sd->
d0 = (np[nn - 2] << sh) | (np[nn - 3] >> (
LIMB_BITS - sh));
231 u1 = (x[nn - 1] << sd->
sh) | (x[nn - 2] >> (
LIMB_BITS - sd->
sh));
232 u0 = (x[nn - 2] << sd->
sh) | (x[nn - 3] >> (
LIMB_BITS - sd->
sh));
267 }
else if (qabs == 2) {
335 if (b == 0)
return 0;
339 if ((tz & 1) && ((
A & 7) == 3 || (
A & 7) == 5)) sign = -sign;
340 if (b == 1)
return sign;
345 if ((b & 3) == 3 && (
A & 3) == 3) sign = -sign;
348 if (b == 0)
return 0;
362 if ((
A & 3) == 3 && (np[0] & 3) == 3) sign = -sign;
364 if (sign == 0)
return 0;
365 if (Dneg && (np[0] & 3) == 3) sign = -sign;
392 if (j == 0)
return 0;
400 uint Qabs = Dneg ? (Dabs + 1) / 4 : (Dabs - 1) / 4;
412 mp_ptr Uk = np1 + nn + 1, Uk1 = Uk + nn;
413 mp_ptr T1 = Uk1 + nn, T2 = T1 + nn, T3 = T2 + nn;
442 mp_ptr sw = Uk; Uk = Uk1; Uk1 = sw;
516 lmmp_mont_init_(&mc, np, nn, arena, 1, arena + mn);
519 lmmp_mont_free_(&mc);
569 lmmp_mont_init_(&mc, np, nn, arena, 1,
prod);
600 for (
int r = rn; r > 0; r--) {
612 while (bw > 1 && bs[bw - 1] == 0) bw--;
631 if (!ok)
goto composite;
636 lmmp_mont_free_(&mc);
641 lmmp_mont_free_(&mc);
651 if ((np[0] & 1) == 0)
return 0;
664 if ((np[0] & 1) == 0)
return 0;
703#define IPN_PROTH_WITNESS_MAX 65535u
713 if (j == 0)
return 0;
721 int form = lmmp_mont_sp_init_(&mc, np, nn);
737 lmmp_mont_redcify_(abar, m1, nn,
prod, np);
743 lmmp_mont_redcify_(abar, abar, nn,
prod, np);
749 lmmp_mont_sp_redc_(u,
prod, &mc);
752 lmmp_mont_sp_redc_(u,
prod, &mc);
758 lmmp_mont_sp_redc_(u,
prod, &mc);
782 u128 N = ((u128)kk << ne) + 1;
801 if (hi) np[w + 1] = hi;
#define lmmp_leading_zeros_
#define lmmp_tailing_zeros_
static const uchar ipn_r1_rounds[8]
Copyright (C) 2026 HJimmyK (Jericho Knox)
static int ipn_sprp_1_(lmmp_mont_t *restrict mc, const ipn_sdiv_t *sd, mp_limb_t a, mp_srcptr d, mp_bitcnt_t dbits, mp_bitcnt_t t, mp_ptr u, mp_ptr restrict prod)
短基底 MR 单轮:基底为 1 limb 裸标量,梯子与探测全程蒙域
#define IPN_PROTH_WITNESS_MAX
static void ipn_mont_neg_(mp_ptr dst, mp_srcptr x, const lmmp_mont_t *restrict mc)
static const ushort ipn_trial_bound[8]
static int ipn_jacobi_small_(ulong b, ulong A)
static int ipn_jacobi_D_(uint Dabs, int Dneg, mp_srcptr np, mp_size_t nn)
static void ipn_mont_half_(mp_ptr x, const lmmp_mont_t *restrict mc)
static void ipn_mont_dbl_(mp_ptr dst, mp_srcptr x, const lmmp_mont_t *restrict mc)
static void ipn_sdiv_init_(ipn_sdiv_t *sd, mp_srcptr np, mp_size_t nn)
短除上下文初始化:归一化除数顶 2 limb 与其 2/1 逆元
static int ipn_notrial_i_(mp_srcptr np, mp_size_t nn, int strength)
static void ipn_mont_add_(mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t *restrict mc)
static int ipn_sprp_base2_(lmmp_mont_t *restrict mc, mp_srcptr d, mp_bitcnt_t dbits, mp_bitcnt_t t, mp_ptr u, mp_ptr restrict prod)
单轮 Rabin-Miller 强伪素数测试(大于 128 位,基底硬编码为 2)
static void ipn_mont_mul_small_(mp_ptr restrict dst, mp_srcptr restrict x, ulong qabs, int qneg, const lmmp_mont_t *mc, const ipn_sdiv_t *sd)
static mp_bitcnt_t ipn_ctz_(mp_srcptr dp)
static const uchar ipn_rn_rounds[8]
static void ipn_sdiv_mul1_(mp_ptr x, mp_limb_t a, const ipn_sdiv_t *sd)
蒙域内乘裸 1 limb 标量:x <- x*a mod n(结果仍是蒙域剩余)
static mp_size_t ipn_norm_(mp_srcptr dp, mp_size_t dn)
static int ipn_proth_i_(mp_srcptr np, mp_size_t nn, ulong kk, mp_bitcnt_t ne)
static int ipn_lucas_i_(mp_srcptr np, mp_size_t nn, lmmp_mont_t *restrict mc, const ipn_sdiv_t *sd, mp_ptr restrict prod)
static void ipn_mont_sub_(mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t *restrict mc)
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
#define lmmp_param_assert(x)
#define lmmp_dec(p)
减1宏(预期无借位)
#define lmmp_inc(p)
加1宏(预期无进位)
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
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
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
mp_size_t lmmp_random_(mp_ptr dst, mp_size_t n)
生成随机大整数(0 - B^n-1 均匀分布)
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
int lmmp_is_strong_lucas_(mp_srcptr np, mp_size_t nn)
强 Lucas-Selfridge 测试(大于 128 位)
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
int lmmp_is_prime_n_notrial_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(无试除法,强度分档,大于 128 位)
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
bool lmmp_is_prime_ulong_(ulong n)
判断素数
int lmmp_is_prothprime_(uint k, mp_size_t n)
Proth 数 k*2^n+1 的素性判定(普罗斯定理)
void lmmp_mont_redc_(mp_ptr restrict dst, mp_ptr restrict tp, lmmp_mont_t *restrict mc)
REDC 单步并规范化:[dst,n] = (t + q*m)/B^n mod m,结果 < m
void lmmp_powmod_odd_mont_(mp_ptr restrict u, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en, lmmp_mont_t *restrict mc, mp_ptr restrict b2, mp_ptr restrict prod, mp_ptr restrict pp)
奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_randlimb_(void)
依据全局状态获取单个随机limb(0 - B 均匀分布)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TALLOC_TYPE(n, type)
bool lmmp_trialdiv_(mp_srcptr np, mp_size_t nn, ushort N)
Copyright (C) 2026 HJimmyK (Jericho Knox)