LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime_n.c 文件参考
#include "impl/tmp_alloc.h"
#include "impl/inlines.h"
#include "impl/longlong.h"
#include "numth/powmod.h"
#include "impl/rand_state.h"
#include "impl/trialdiv.h"
#include "lmmp/lmmpn.h"
#include "lmmp/mprand.h"
#include "lmmp/numth.h"
is_prime_n.c 的引用(Include)关系图:

浏览该文件的源代码.

结构体

struct  ipn_sdiv_t

宏定义

#define IPN_PROTH_WITNESS_MAX   65535u

函数

static mp_bitcnt_t ipn_ctz_ (mp_srcptr dp)
static int ipn_jacobi_D_ (uint Dabs, int Dneg, mp_srcptr np, mp_size_t nn)
static int ipn_jacobi_small_ (ulong b, ulong A)
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_add_ (mp_ptr dst, mp_srcptr a, mp_srcptr b, 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_mont_half_ (mp_ptr x, const lmmp_mont_t *restrict mc)
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 void ipn_mont_neg_ (mp_ptr dst, mp_srcptr x, const lmmp_mont_t *restrict mc)
static void ipn_mont_sub_ (mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t *restrict mc)
static mp_size_t ipn_norm_ (mp_srcptr dp, mp_size_t dn)
static int ipn_notrial_i_ (mp_srcptr np, mp_size_t nn, int strength)
static int ipn_proth_i_ (mp_srcptr np, mp_size_t nn, ulong kk, mp_bitcnt_t ne)
static void ipn_sdiv_init_ (ipn_sdiv_t *sd, mp_srcptr np, mp_size_t nn)
 短除上下文初始化:归一化除数顶 2 limb 与其 2/1 逆元
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 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 裸标量,梯子与探测全程蒙域
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)
int lmmp_is_prime_n_ (mp_srcptr np, mp_size_t nn, int strength)
 大整数素性检验(强度分档,大于 128 位)
int lmmp_is_prime_n_notrial_ (mp_srcptr np, mp_size_t nn, int strength)
 大整数素性检验(无试除法,强度分档,大于 128 位)
int lmmp_is_prothprime_ (uint k, mp_size_t n)
 Proth 数 k*2^n+1 的素性判定(普罗斯定理)
int lmmp_is_strong_lucas_ (mp_srcptr np, mp_size_t nn)
 强 Lucas-Selfridge 测试(大于 128 位)

变量

static const uchar ipn_r1_rounds [8] = {3, 4, 5, 6, 0, 2, 3, 4}
 Copyright (C) 2026 HJimmyK (Jericho Knox)
static const uchar ipn_rn_rounds [8] = {2, 3, 4, 5, 0, 0, 1, 2}
static const ushort ipn_trial_bound [8] = {100, 300, 1000, 3000, 1000, 3000, 5000, 10000}

结构体说明

◆ ipn_sdiv_t

struct ipn_sdiv_t

在文件 is_prime_n.c 第 179 行定义.

ipn_sdiv_t 的协作图:
成员变量
mp_limb_t d0
mp_limb_t d1
mp_limb_t dinv
mp_srcptr n
mp_size_t nn
mp_bitcnt_t sh

宏定义说明

◆ IPN_PROTH_WITNESS_MAX

#define IPN_PROTH_WITNESS_MAX   65535u

在文件 is_prime_n.c 第 703 行定义.

被这些函数引用 ipn_proth_i_().

函数说明

◆ ipn_ctz_()

mp_bitcnt_t ipn_ctz_ ( mp_srcptr dp)
inlinestatic

在文件 is_prime_n.c 第 115 行定义.

115 {
116 mp_size_t z = 0;
117 while (dp[z] == 0) z++;
118 return (mp_bitcnt_t)z * LIMB_BITS + lmmp_tailing_zeros_(dp[z]);
119}
#define lmmp_tailing_zeros_
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
#define LIMB_BITS
定义 lmmp.h:102

引用了 ipn_ctz_(), LIMB_BITS , 以及 lmmp_tailing_zeros_.

被这些函数引用 ipn_ctz_(), ipn_lucas_i_() , 以及 ipn_notrial_i_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_jacobi_D_()

int ipn_jacobi_D_ ( uint Dabs,
int Dneg,
mp_srcptr np,
mp_size_t nn )
static

在文件 is_prime_n.c 第 358 行定义.

358 {
359 ulong A = Dabs;
360 ulong b = lmmp_mod_1_(np, nn, A);
361 int sign = 1;
362 if ((A & 3) == 3 && (np[0] & 3) == 3) sign = -sign;
363 sign *= ipn_jacobi_small_(b, A);
364 if (sign == 0) return 0;
365 if (Dneg && (np[0] & 3) == 3) sign = -sign;
366 return sign;
367}
#define A
static int ipn_jacobi_small_(ulong b, ulong A)
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
uint64_t ulong
定义 numth.h:39

引用了 A, ipn_jacobi_D_(), ipn_jacobi_small_(), lmmp_mod_1_() , 以及 LMMP_NOINLINE.

被这些函数引用 ipn_jacobi_D_(), ipn_lucas_i_() , 以及 ipn_proth_i_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_jacobi_small_()

int ipn_jacobi_small_ ( ulong b,
ulong A )
inlinestatic

在文件 is_prime_n.c 第 333 行定义.

333 {
334 int sign = 1;
335 if (b == 0) return 0;
336 for (;;) {
337 int tz = lmmp_tailing_zeros_(b);
338 b >>= tz;
339 if ((tz & 1) && ((A & 7) == 3 || (A & 7) == 5)) sign = -sign;
340 if (b == 1) return sign;
341 if (b < A) {
342 ulong s = b;
343 b = A;
344 A = s;
345 if ((b & 3) == 3 && (A & 3) == 3) sign = -sign;
346 }
347 b -= A;
348 if (b == 0) return 0;
349 }
350}
#define s

引用了 A, ipn_jacobi_small_(), lmmp_tailing_zeros_ , 以及 s.

被这些函数引用 ipn_jacobi_D_() , 以及 ipn_jacobi_small_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_lucas_i_()

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

在文件 is_prime_n.c 第 381 行定义.

387 {
388 uint Dabs = 5;
389 int Dneg = 0;
390 for (;;) {
391 int j = ipn_jacobi_D_(Dabs, Dneg, np, nn);
392 if (j == 0) return 0; /* gcd(|D|,n)>1 且 0 < |D| < n → 合数 */
393 if (j == -1) break;
394 Dabs += 2;
395 Dneg ^= 1;
396 if (Dabs == 17 && lmmp_perfsqr_(np, nn)) return 0;
397 }
398
399 /* Q = (1-D)/4,可为负;d*2^s = n+1 */
400 uint Qabs = Dneg ? (Dabs + 1) / 4 : (Dabs - 1) / 4;
401
402 TEMP_DECL;
403
404 /*
405 [prod(2n)] 平方全积(REDC 被归约数,调用者段)
406 [np1(n+1)] n+1(防全 1 顶进位越顶)→ d 所在段
407 [Uk|Uk1(2n)] U 阶梯状态对 (U_k, U_{k+1})
408 [T1|T2|T3(3n)] 差值平方 / A / B 载体与标量乘输出
409 */
410 mp_ptr restrict arena = TALLOC_TYPE(6 * nn + 1, mp_limb_t);
411 mp_ptr restrict np1 = arena;
412 mp_ptr Uk = np1 + nn + 1, Uk1 = Uk + nn;
413 mp_ptr T1 = Uk1 + nn, T2 = T1 + nn, T3 = T2 + nn;
414
415 lmmp_copy(np1, np, nn);
416 np1[nn] = 0;
417 lmmp_inc(np1);
418 mp_bitcnt_t s = ipn_ctz_(np1);
419 mp_ptr d = np1 + s / LIMB_BITS;
420 mp_size_t dn = ipn_norm_(d, nn + 1 - s / LIMB_BITS);
421 lmmp_shr_(d, d, dn, s % LIMB_BITS);
422 dn = ipn_norm_(d, dn);
423
424 /* 阶梯初态 k=1:(U_1, U_2) = (1, 1)(P=1, U_0=0 → U_2 与 Q 无关) */
425 lmmp_copy(Uk, mc->one, nn);
426 lmmp_copy(Uk1, mc->one, nn);
427
428 mp_bitcnt_t dbits = (dn - 1) * LIMB_BITS + lmmp_limb_bits_(d[dn - 1]);
429 for (mp_bitcnt_t i = dbits - 1; i-- > 0;) {
430 ipn_mont_sub_(T1, Uk1, Uk, mc); /* (U_{k+1}-U_k)R */
431 lmmp_sqr_(prod, Uk1, nn);
432 lmmp_mont_redc_(T2, prod, mc); /* A = U_{k+1}^2 R */
433 lmmp_sqr_(prod, Uk, nn);
434 lmmp_mont_redc_(T3, prod, mc); /* B = U_k^2 R */
435 lmmp_sqr_(prod, T1, nn);
436 lmmp_mont_redc_(T1, prod, mc); /* D = (U_{k+1}-U_k)^2 R */
437 ipn_mont_mul_small_(Uk, T3, Qabs, !Dneg, mc, sd); /* Q*U_k^2 R */
438 ipn_mont_sub_(Uk1, T2, Uk, mc); /* U_{2k+1} = A - Q*B */
439 ipn_mont_sub_(Uk, T2, T1, mc); /* U_{2k} = A - D */
440 if ((d[i / LIMB_BITS] >> (i % LIMB_BITS)) & 1) {
441 ipn_mont_mul_small_(T3, Uk, Qabs, !Dneg, mc, sd); /* Q*U_{2k} R */
442 mp_ptr sw = Uk; Uk = Uk1; Uk1 = sw; /* (U_{2k+1}, _) */
443 ipn_mont_sub_(Uk1, Uk, T3, mc); /* U_{2k+2} = U_{2k+1} - Q*U_{2k} */
444 }
445 }
446
447 /*
448 BFW 强化(Baillie-Fiori-Wagstaff 2021,同 is_prime_2.c):判据
449 命中不早退,链尾统一追加 vpsp(V_{n+1} ≡ 2Q)与 Q-Euler
450 (Q^{(n+1)/2} ≡ ±Q)检查,素数必然全过、合数严格多拒。代价:
451 s>=2(n ≡ 3 mod 4)命中者本付 Q^d 重建,仅 +1 平方 REDC;s=1
452 (n ≡ 1 mod 4)素数必经入口命中,新付整套重建与检查(约
453 3.5 个 REDC + O(n) 标量,占 192n/每bit3REDC 的 U 阶梯 <0.5%)
454 */
455 int hit = lmmp_zero_q_(Uk, nn);
456 ipn_mont_dbl_(T1, Uk1, mc);
457 ipn_mont_sub_(T1, T1, Uk, mc); /* V_d = 2U_{d+1} - U_d */
458 hit |= lmmp_zero_q_(T1, nn);
459 if (hit || s > 1) {
460 /* Q^d R = (V_d^2 - D*U_d^2)R/4:两平方 REDC,D 以小标量合成,
461 再模 n 两次折半(GMP 在普通域有精确整除 /4 便车,蒙域以
462 折半替代,O(n)) */
463 lmmp_sqr_(prod, T1, nn);
464 lmmp_mont_redc_(T2, prod, mc); /* V_d^2 R */
465 lmmp_sqr_(prod, Uk, nn);
466 lmmp_mont_redc_(Uk, prod, mc); /* U_d^2 R(U_d 槽至此耗尽) */
467 ipn_mont_mul_small_(T3, Uk, Dabs, 0, mc, sd);
468 if (!Dneg)
469 ipn_mont_sub_(T2, T2, T3, mc); /* D>0:V_d^2 - D*U_d^2 */
470 else
471 ipn_mont_add_(T2, T2, T3, mc); /* D<0:V_d^2 + |D|*U_d^2 */
472 ipn_mont_half_(T2, mc); /* (V^2 - D U^2) = 4Q^d → 2Q^d */
473 ipn_mont_half_(T2, mc); /* → Q^d(阶为蒙域剩余) */
474 for (; s > 1; s--) {
475 ipn_mont_dbl_(T3, T2, mc); /* 2Q^m R */
476 lmmp_sqr_(prod, T1, nn);
477 lmmp_mont_redc_(Uk, prod, mc); /* V_m^2 R */
478 lmmp_sqr_(prod, T2, nn);
479 lmmp_mont_redc_(T2, prod, mc); /* Q^{2m} R(旧值已被消费) */
480 ipn_mont_sub_(T1, Uk, T3, mc); /* V_{2m} = V_m^2 - 2Q^m */
481 hit |= lmmp_zero_q_(T1, nn);
482 }
483 if (hit) {
484 /* 末态 T1 = V_{(n+1)/2},T2 = Q^{(n+1)/2}(s=1 时为 V_d/Q^d
485 同型)。vpsp 补一次平方 REDC 得 V_{n+1};Q-Euler 以蒙域
486 Qm = Q*one 做双值比较 */
487 lmmp_sqr_(prod, T1, nn);
488 lmmp_mont_redc_(Uk, prod, mc); /* V_{(n+1)/2}^2 R */
489 ipn_mont_dbl_(T3, T2, mc); /* 2Q^{(n+1)/2} R */
490 ipn_mont_sub_(T1, Uk, T3, mc); /* V_{n+1} R */
491 ipn_mont_mul_small_(Uk, mc->one, Qabs, !Dneg, mc, sd); /* Q R */
492 ipn_mont_dbl_(T3, Uk, mc); /* 2Q R */
493 if (lmmp_cmp_(T1, T3, nn) != 0)
494 hit = 0;
495 else if (lmmp_cmp_(T2, Uk, nn) != 0) {
496 ipn_mont_neg_(T3, Uk, mc);
497 if (lmmp_cmp_(T2, T3, nn) != 0) hit = 0;
498 }
499 }
500 }
501
502 TEMP_FREE;
503 return hit;
504}
#define prod
#define lmmp_limb_bits_
#define lmmp_sqr_
static void ipn_mont_neg_(mp_ptr dst, mp_srcptr x, const lmmp_mont_t *restrict mc)
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_mont_add_(mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t *restrict mc)
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 mp_size_t ipn_norm_(mp_srcptr dp, mp_size_t dn)
static void ipn_mont_sub_(mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t *restrict mc)
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_limb_t
定义 lmmp.h:92
#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
定义 shr.c:26
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
uint32_t uint
定义 numth.h:38
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
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
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 ipn_ctz_(), ipn_jacobi_D_(), ipn_lucas_i_(), ipn_mont_add_(), ipn_mont_dbl_(), ipn_mont_half_(), ipn_mont_mul_small_(), ipn_mont_neg_(), ipn_mont_sub_(), ipn_norm_(), LIMB_BITS, lmmp_cmp_(), lmmp_copy, lmmp_inc, lmmp_limb_bits_, lmmp_mont_redc_(), lmmp_perfsqr_(), lmmp_shr_(), lmmp_sqr_, lmmp_zero_q_(), prod, restrict, s, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 ipn_lucas_i_(), ipn_notrial_i_() , 以及 lmmp_is_strong_lucas_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_mont_add_()

void ipn_mont_add_ ( mp_ptr dst,
mp_srcptr a,
mp_srcptr b,
const lmmp_mont_t *restrict mc )
inlinestatic

在文件 is_prime_n.c 第 96 行定义.

96 {
97 mp_limb_t c = lmmp_add_n_(dst, a, b, mc->n);
98 if (c)
99 (void)lmmp_sub_n_(dst, dst, mc->m, mc->n);
100 else if (lmmp_cmp_(dst, mc->m, mc->n) >= 0)
101 lmmp_sub_n_(dst, dst, mc->m, mc->n);
102}
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]
定义 sub_n.c:84
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]
定义 add_n.c:76
mp_size_t n
mp_srcptr m

引用了 ipn_mont_add_(), lmmp_add_n_(), lmmp_cmp_(), lmmp_sub_n_() , 以及 restrict.

被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_add_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_mont_dbl_()

void ipn_mont_dbl_ ( mp_ptr dst,
mp_srcptr x,
const lmmp_mont_t *restrict mc )
inlinestatic

在文件 is_prime_n.c 第 74 行定义.

74 {
75 mp_limb_t c = lmmp_add_n_(dst, x, x, mc->n);
76 if (c)
77 (void)lmmp_sub_n_(dst, dst, mc->m, mc->n);
78 else if (lmmp_cmp_(dst, mc->m, mc->n) >= 0)
79 lmmp_sub_n_(dst, dst, mc->m, mc->n);
80}

引用了 ipn_mont_dbl_(), lmmp_add_n_(), lmmp_cmp_(), lmmp_sub_n_() , 以及 restrict.

被这些函数引用 ipn_lucas_i_(), ipn_mont_dbl_(), ipn_mont_mul_small_() , 以及 ipn_sprp_base2_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_mont_half_()

void ipn_mont_half_ ( mp_ptr x,
const lmmp_mont_t *restrict mc )
inlinestatic

在文件 is_prime_n.c 第 107 行定义.

107 {
108 mp_size_t n = mc->n;
109 mp_limb_t c = (x[0] & 1) ? lmmp_add_n_(x, x, mc->m, n) : 0;
110 lmmp_shr_(x, x, n, 1);
111 x[n - 1] |= c << (LIMB_BITS - 1);
112}
#define n

引用了 ipn_mont_half_(), LIMB_BITS, lmmp_add_n_(), lmmp_shr_(), n , 以及 restrict.

被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_half_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_mont_mul_small_()

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

在文件 is_prime_n.c 第 252 行定义.

259 {
260 if (qabs == 0) {
261 lmmp_zero(dst, mc->n);
262 return;
263 }
264 lmmp_copy(dst, x, mc->n);
265 if (qabs >= 3) {
266 ipn_sdiv_mul1_(dst, qabs, sd);
267 } else if (qabs == 2) {
268 ipn_mont_dbl_(dst, dst, mc);
269 }
270 if (qneg && !lmmp_zero_q_(dst, mc->n))
271 ipn_mont_neg_(dst, dst, mc);
272}
static void ipn_sdiv_mul1_(mp_ptr x, mp_limb_t a, const ipn_sdiv_t *sd)
蒙域内乘裸 1 limb 标量:x <- x*a mod n(结果仍是蒙域剩余)
#define lmmp_zero(dst, n)
定义 lmmp.h:476

引用了 ipn_mont_dbl_(), ipn_mont_mul_small_(), ipn_mont_neg_(), ipn_sdiv_mul1_(), lmmp_copy, lmmp_zero, lmmp_zero_q_(), lmmp_mont_t::n , 以及 restrict.

被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_mul_small_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_mont_neg_()

void ipn_mont_neg_ ( mp_ptr dst,
mp_srcptr x,
const lmmp_mont_t *restrict mc )
inlinestatic

在文件 is_prime_n.c 第 90 行定义.

90 {
91 (void)lmmp_sub_n_(dst, mc->m, x, mc->n);
92}

引用了 ipn_mont_neg_(), lmmp_sub_n_() , 以及 restrict.

被这些函数引用 ipn_lucas_i_(), ipn_mont_mul_small_() , 以及 ipn_mont_neg_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_mont_sub_()

void ipn_mont_sub_ ( mp_ptr dst,
mp_srcptr a,
mp_srcptr b,
const lmmp_mont_t *restrict mc )
inlinestatic

在文件 is_prime_n.c 第 83 行定义.

83 {
84 mp_limb_t bo = lmmp_sub_n_(dst, a, b, mc->n);
85 if (bo)
86 (void)lmmp_add_n_(dst, dst, mc->m, mc->n);
87}

引用了 ipn_mont_sub_(), lmmp_add_n_(), lmmp_sub_n_() , 以及 restrict.

被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_sub_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_norm_()

mp_size_t ipn_norm_ ( mp_srcptr dp,
mp_size_t dn )
inlinestatic

在文件 is_prime_n.c 第 121 行定义.

121 {
122 while (dn > 0 && dp[dn - 1] == 0) dn--;
123 return dn;
124}

引用了 ipn_norm_().

被这些函数引用 ipn_lucas_i_(), ipn_norm_() , 以及 ipn_notrial_i_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_notrial_i_()

int ipn_notrial_i_ ( mp_srcptr np,
mp_size_t nn,
int strength )
static

在文件 is_prime_n.c 第 524 行定义.

524 {
525 /* n-1 = d*2^t(d 奇)的形状参数:t 与 d 位长先于单块工作区求出
526 (全域轮奇次幂表 ppn 依 d 位长取窗口尺寸) */
527 mp_bitcnt_t t, dbits;
528 {
529 TEMP_DECL;
530 mp_ptr nm1 = TALLOC_TYPE(nn, mp_limb_t);
531 lmmp_copy(nm1, np, nn);
532 lmmp_dec(nm1);
533 t = ipn_ctz_(nm1);
534 mp_size_t bn = ipn_norm_(nm1, nn);
535 dbits = (mp_bitcnt_t)(bn - 1) * LIMB_BITS + lmmp_limb_bits_(nm1[bn - 1]) - t;
536 TEMP_FREE;
537 }
538
539 int rn = ipn_rn_rounds[strength];
540 mp_size_t ppn = rn > 0 ? (mp_size_t)nn << (lmmp_powmod_win_size_(dbits) - 1) : 0;
541
542 TEMP_DECL;
543 lmmp_mont_t mc;
544 ipn_sdiv_t sd;
545 /*
546 全程共享单块工作区(蒙域上下文 init 一次,贯穿基底 2 / 随机基底
547 各轮 / 强 Lucas,各轮免 binvert、one/m1 的 redcify 与 FFT 变换
548 缓存重建):
549 [蒙域段] basecase 2n | 中层 8n | 折叠 8n+msz(lmmp_mont_need_)
550 [prod(2n)] 平方全积兼 redcify 工作区(各轮共用)
551 [nm1(n)] n-1(d 分解来源与全域轮采样上界)
552 [d(n)] (n-1)>>t(各随机轮固定不变)
553 [u(n)] 蒙域梯子累加器/探测载体(基底2、短基底、全域轮接力)
554 [bs(n)] 全域轮采样基底
555 [b2(n)] 全域轮表生成暂存(b²·R mod n,出口死)
556 [pp(ppn)] 全域轮奇次幂表(rn==0 档免配)
557 强 Lucas 的 U/T 阶梯段经嵌套 TEMP 分配,蒙域段与 prod 复用外层
558 */
559 mp_size_t mn = lmmp_mont_need_(nn, 1);
560 mp_ptr restrict arena = TALLOC_TYPE(mn + 8 * nn + ppn, mp_limb_t);
561 mp_ptr restrict prod = arena + mn;
562 mp_ptr restrict nm1 = prod + 2 * nn;
563 mp_ptr restrict d = nm1 + nn;
564 mp_ptr restrict u = d + nn;
565 mp_ptr restrict bs = u + nn;
566 mp_ptr b2 = bs + nn;
567 mp_ptr pp = b2 + nn;
568
569 lmmp_mont_init_(&mc, np, nn, arena, 1, prod);
570 ipn_sdiv_init_(&sd, np, nn);
571
572 /* n-1 = d*2^t:低零 limb 折叠为指针偏移,余位单次移位 */
573 lmmp_copy(nm1, np, nn);
574 lmmp_dec(nm1);
575 mp_size_t dn = ipn_norm_(nm1 + t / LIMB_BITS, nn - t / LIMB_BITS);
576 lmmp_shr_(d, nm1 + t / LIMB_BITS, dn, t % LIMB_BITS);
577 dn = ipn_norm_(d, dn);
578
579 /* 各档公共首步:基底 2 特化 MR(BPSW 的 MR 半部,倍加梯子) */
580 if (!ipn_sprp_base2_(&mc, d, dbits, t, u, prod)) goto composite;
581
582 /* 1 limb 基底 MR:a ∈ [3,B-1] 均匀(全局 RNG 单 limb 直取,免去
583 lmmp_random_ 的整块播种开销)。契约域 n > 2^128 > B 保证任意 a 满足
584 3 <= a <= n-2,无需拒绝采样 */
585 for (int r = ipn_r1_rounds[strength]; r > 0; r--) {
586 mp_limb_t a;
587 do {
588 a = lmmp_randlimb_();
589 } while (a < 3);
590 if (!ipn_sprp_1_(&mc, &sd, a, d, dbits, t, u, prod)) goto composite;
591 }
592
593 /* 全域(n limb)基底 MR(至多 N 轮,检出即止):b ∈ [2,n-2] 均匀。
594 顶 limb 掩码到 n 的位长内再整体拒绝采样:位长内均匀故 P(>=n) <= 1/2,
595 期望 <= 2 次填充,免去每轮一次 nn/nn 全除归约(旧路径 lmmp_div_)。
596 1 limb 短基底轮与全域轮的梯子均留在蒙域,y 的 ±1 探测以 one/m1
597 为基准,尾部探测平方走 sqr_+REDC(与基底 2 轮同构) */
598 uint tb = lmmp_limb_bits_(np[nn - 1]);
599 mp_limb_t tmask = (tb == LIMB_BITS) ? ~(mp_limb_t)0 : (((mp_limb_t)1 << tb) - 1);
600 for (int r = rn; r > 0; r--) {
601 for (;;) {
602 lmmp_random_(bs, nn);
603 bs[nn - 1] &= tmask;
604 if (lmmp_cmp_(bs, nm1, nn) < 0 && (bs[0] >= 2 || !lmmp_zero_q_(bs + 1, nn - 1)))
605 break;
606 }
607 /* 基底有效 limb 宽:nn=3 且 n 接近 2^128 时 <=1 limb 的基底占比可达
608 可观比例(均匀采样下约 2^128/n),窄基底走短乘可省下全宽乘。
609 宽度 2 不特化:其唯一可能出现的尺寸 nn=3 上短除内核慢于通用路径
610 (见本节顶部实测注),而 nn>=4 采样退化为 <=2 limb 的概率 ~2^-64 */
611 mp_size_t bw = nn;
612 while (bw > 1 && bs[bw - 1] == 0) bw--;
613 if (bw == 1) {
614 if (!ipn_sprp_1_(&mc, &sd, bs[0], d, dbits, t, u, prod)) goto composite;
615 continue;
616 }
617 lmmp_powmod_odd_mont_(u, bs, d, dn, &mc, b2, prod, pp);
618 int ok = 0;
619 if (lmmp_cmp_(u, mc.one, nn) == 0 || lmmp_cmp_(u, mc.m1, nn) == 0) {
620 ok = 1;
621 } else {
622 for (mp_bitcnt_t j = t - 1; j > 0; j--) {
623 lmmp_sqr_(prod, u, nn);
624 lmmp_mont_redc_(u, prod, &mc);
625 if (lmmp_cmp_(u, mc.m1, nn) == 0) {
626 ok = 1;
627 break;
628 }
629 }
630 }
631 if (!ok) goto composite;
632 }
633
634 /* 4 档及以上:BPSW 的 Lucas 半部(嵌套 TEMP 分配阶梯段,蒙域段复用) */
635 if (strength >= 4 && !ipn_lucas_i_(np, nn, &mc, &sd, prod)) goto composite;
636 lmmp_mont_free_(&mc);
637 TEMP_FREE;
638 return 2;
639
640composite:
641 lmmp_mont_free_(&mc);
642 TEMP_FREE;
643 return 0;
644}
#define bn
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 裸标量,梯子与探测全程蒙域
static void ipn_sdiv_init_(ipn_sdiv_t *sd, mp_srcptr np, mp_size_t nn)
短除上下文初始化:归一化除数顶 2 limb 与其 2/1 逆元
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 const uchar ipn_rn_rounds[8]
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)
#define lmmp_dec(p)
减1宏(预期无借位)
mp_size_t lmmp_random_(mp_ptr dst, mp_size_t n)
生成随机大整数(0 - B^n-1 均匀分布)
#define b2
#define t
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 均匀分布)

引用了 b2, bn, ipn_ctz_(), ipn_lucas_i_(), ipn_norm_(), ipn_notrial_i_(), ipn_r1_rounds, ipn_rn_rounds, ipn_sdiv_init_(), ipn_sprp_1_(), ipn_sprp_base2_(), LIMB_BITS, lmmp_cmp_(), lmmp_copy, lmmp_dec, lmmp_limb_bits_, lmmp_mont_redc_(), LMMP_NOINLINE, lmmp_powmod_odd_mont_(), lmmp_randlimb_(), lmmp_random_(), lmmp_shr_(), lmmp_sqr_, lmmp_zero_q_(), lmmp_mont_t::m1, lmmp_mont_t::one, prod, restrict, t, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 ipn_notrial_i_(), lmmp_is_prime_n_() , 以及 lmmp_is_prime_n_notrial_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_proth_i_()

int ipn_proth_i_ ( mp_srcptr np,
mp_size_t nn,
ulong kk,
mp_bitcnt_t ne )
static

在文件 is_prime_n.c 第 705 行定义.

705 {
706 /* 见证搜索(纯 Jacobi,无分配):首个 Jacobi != +1 者即决 */
707 ulong a;
708 int j = 1;
709 for (a = 3; a <= IPN_PROTH_WITNESS_MAX; a += 2) {
710 j = ipn_jacobi_D_((uint)a, 0, np, nn);
711 if (j != 1) break;
712 }
713 if (j == 0) return 0; /* gcd(a,N) > 1 且 a < N(N > 2^64 > a)*/
714 if (j == 1) {
715 if (nn == 2) return lmmp_is_prime_2_(np[0], np[1]);
716 return lmmp_is_prime_n_(np, nn, 4);
717 }
718
719 TEMP_DECL;
721 int form = lmmp_mont_sp_init_(&mc, np, nn);
722 lmmp_debug_assert(form == 1);
723 /*
724 [m1(n)] 蒙域 -1(one 装配载体转 m1)
725 [prod(2n)] redcify/平方/乘底全积(sp REDC 被归约数)
726 [u(n)] 梯子累加器
727 [abar(n)] 蒙域基底 ā(先作普通域基底载体,eqsep 原地 redcify)
728 */
729 mp_ptr restrict m1 = TALLOC_TYPE(5 * nn, mp_limb_t);
730 mp_ptr restrict prod = m1 + nn;
731 mp_ptr restrict u = prod + 2 * nn;
732 mp_ptr restrict abar = u + nn;
733
734 /* m1 = N − one(蒙域 -1):one = B^nn mod N 经一次 redcify 除法 */
735 lmmp_zero(m1, nn);
736 m1[0] = 1;
737 lmmp_mont_redcify_(abar, m1, nn, prod, np);
738 (void)lmmp_sub_n_(m1, np, abar, nn);
739
740 /* ā = a*B^nn mod N */
741 lmmp_zero(abar, nn);
742 abar[0] = a;
743 lmmp_mont_redcify_(abar, abar, nn, prod, np);
744
745 /* k 部分:u = ā^kk(L2R;kk <= 2^32-1) */
746 lmmp_copy(u, abar, nn);
747 for (mp_bitcnt_t i = lmmp_limb_bits_(kk) - 1; i-- > 0;) {
748 lmmp_sqr_(prod, u, nn);
749 lmmp_mont_sp_redc_(u, prod, &mc);
750 if ((kk >> i) & 1) {
751 lmmp_mul_n_(prod, u, abar, nn);
752 lmmp_mont_sp_redc_(u, prod, &mc);
753 }
754 }
755
756 for (mp_bitcnt_t i = ne - 1; i-- > 0;) {
757 lmmp_sqr_(prod, u, nn);
758 lmmp_mont_sp_redc_(u, prod, &mc);
759 }
760
761 /* a^((N-1)/2) ≡ -1 ⟺ 蒙域终值 = m1:素数(定理正向);否则该
762 Jacobi = -1 见证下必为合数(Euler 反证) */
763 int ret = lmmp_cmp_(u, m1, nn) == 0;
764 TEMP_FREE;
765 return ret;
766}
#define lmmp_mul_n_
#define IPN_PROTH_WITNESS_MAX
#define lmmp_debug_assert(x)
定义 lmmp.h:498
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)

引用了 ipn_jacobi_D_(), ipn_proth_i_(), IPN_PROTH_WITNESS_MAX, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_is_prime_2_(), lmmp_is_prime_n_(), lmmp_limb_bits_, lmmp_mul_n_, lmmp_sqr_, lmmp_sub_n_(), lmmp_zero, prod, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 ipn_proth_i_() , 以及 lmmp_is_prothprime_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_sdiv_init_()

void ipn_sdiv_init_ ( ipn_sdiv_t * sd,
mp_srcptr np,
mp_size_t nn )
static

短除上下文初始化:归一化除数顶 2 limb 与其 2/1 逆元

参数
sd上下文
np模数(nn 个limb)
nn模数 limb 长度
警告
np!=NULL, nn>2, np[nn-1]>0, np[0]%2==1

在文件 is_prime_n.c 第 195 行定义.

195 {
196 mp_bitcnt_t sh = lmmp_leading_zeros_(np[nn - 1]);
197 sd->n = np;
198 sd->nn = nn;
199 sd->sh = sh;
200 if (sh == 0) {
201 sd->d1 = np[nn - 1];
202 sd->d0 = np[nn - 2];
203 } else {
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));
206 }
207 sd->dinv = lmmp_inv_2_1_(sd->d1, sd->d0);
208}
#define lmmp_leading_zeros_
mp_bitcnt_t sh
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27

引用了 ipn_sdiv_t::d0, ipn_sdiv_t::d1, ipn_sdiv_t::dinv, ipn_sdiv_init_(), LIMB_BITS, lmmp_inv_2_1_(), lmmp_leading_zeros_, ipn_sdiv_t::n, ipn_sdiv_t::nn , 以及 ipn_sdiv_t::sh.

被这些函数引用 ipn_notrial_i_(), ipn_sdiv_init_() , 以及 lmmp_is_strong_lucas_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_sdiv_mul1_()

void ipn_sdiv_mul1_ ( mp_ptr x,
mp_limb_t a,
const ipn_sdiv_t * sd )
inlinestatic

蒙域内乘裸 1 limb 标量:x <- x*a mod n(结果仍是蒙域剩余)

参数
x蒙域剩余(nn 个limb,原地读写)
a裸标量(a < B)
sd短除上下文
警告
x < [sd->n,sd->nn], sep(x,sd->n)
注解
估商与回补的界见本节顶部注;"乘减 q*n"大操作数 n 在前、标量 q 在后

在文件 is_prime_n.c 第 218 行定义.

218 {
219 mp_size_t nn = sd->nn;
220 /* t = x*a:低 nn limb 落回 x,第 nn+1 limb 为进位 */
221 mp_limb_t cy = lmmp_mul_1_(x, x, nn, a);
222
223 /* t<<sh 的顶 3 limb (u2,u1,u0);t<<sh < (n<<sh)*B ⟹ u2 <= d1 */
224 mp_limb_t u2, u1, u0;
225 if (sd->sh == 0) {
226 u2 = cy;
227 u1 = x[nn - 1];
228 u0 = x[nn - 2];
229 } else {
230 u2 = (cy << sd->sh) | (x[nn - 1] >> (LIMB_BITS - sd->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));
233 }
234
235 mp_limb_t q, r1, r0;
236 if (u2 >= sd->d1) {
237 /* u2 == d1:真商 ∈ {B-1,B-2},取 B-1 至多回补一次 */
238 q = LIMB_MAX;
239 } else {
240 /* u2 < d1 ⟹ (u2,u1,u0) < (d1,d0)*B,3/2 除法契约满足 */
241 _udiv_qr_3by2(q, r1, r0, u2, u1, u0, sd->d1, sd->d0, sd->dinv);
242 }
243 (void)r1;
244 (void)r0;
245
246 /* x <- t - q*n;估商偏高时差值为负(hi != 0 即 B^{nn+1} 补码),回补 n */
247 mp_limb_t hi = cy - lmmp_submul_1_(x, sd->n, nn, q);
248 while (hi != 0)
249 hi += lmmp_add_n_(x, x, sd->n, nn);
250}
#define LIMB_MAX
定义 lmmp.h:105
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
定义 mul_1.c:27
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
#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
#define r1
#define r0

引用了 _udiv_qr_3by2, ipn_sdiv_t::d0, ipn_sdiv_t::d1, ipn_sdiv_t::dinv, ipn_sdiv_mul1_(), LIMB_BITS, LIMB_MAX, lmmp_add_n_(), lmmp_mul_1_(), lmmp_submul_1_(), ipn_sdiv_t::n, ipn_sdiv_t::nn, r0, r1 , 以及 ipn_sdiv_t::sh.

被这些函数引用 ipn_mont_mul_small_(), ipn_sdiv_mul1_() , 以及 ipn_sprp_1_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_sprp_1_()

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 )
static

短基底 MR 单轮:基底为 1 limb 裸标量,梯子与探测全程蒙域

参数
mc蒙域上下文(含 one/m1,已完成 lmmp_mont_init_)
sd短除上下文(ipn_sdiv_init_ 就绪,模数同 mc)
a基底(1 个limb,a < B)
d(n-1)>>t(奇)
dbitsd 的位长
tv2(n-1)
u梯子累加器兼探测载体(mc->n 个limb)
prod工作区(2*mc->n 个limb,平方全积,出口被破坏)
警告
2 <= a <= [mc->m,mc->n]-2(契约域 n > 2^128 > B 恒成立), sep(u,prod), sep([u|prod], mc 内各缓冲区)
返回
1 = 通过该基底的 Miller-Rabin 测试;0 = 合数
注解
SPRP 判据与基底 2 轮一致:u ∈ {one,m1} 或 u^(2^j) 命中 m1

在文件 is_prime_n.c 第 289 行定义.

298 {
299 mp_size_t nn = mc->n;
300
301 /* 梯子初值 u = a*B^nn mod n = one*a:复用同一乘底内核,免去基底入蒙域的
302 全宽 redcify 除法 */
303 lmmp_copy(u, mc->one, nn);
304 ipn_sdiv_mul1_(u, a, sd);
305
306 for (mp_bitcnt_t i = dbits - 1; i-- > 0;) {
307 lmmp_sqr_(prod, u, nn);
308 lmmp_mont_redc_(u, prod, mc);
309 if ((d[i / LIMB_BITS] >> (i % LIMB_BITS)) & 1)
310 ipn_sdiv_mul1_(u, a, sd);
311 }
312
313 /* 蒙域二次探测:y ∈ {one,m1} 或 y^(2^j) 命中 m1(0 < j < t,共 t-1 次
314 sqr+REDC;免出蒙域 REDC 与旧路径的全宽除法尾部) */
315 int ret = 0;
316 if (lmmp_cmp_(u, mc->one, nn) == 0 || lmmp_cmp_(u, mc->m1, nn) == 0) {
317 ret = 1;
318 } else {
319 for (mp_bitcnt_t j = t - 1; j > 0; j--) {
320 lmmp_sqr_(prod, u, nn);
321 lmmp_mont_redc_(u, prod, mc);
322 if (lmmp_cmp_(u, mc->m1, nn) == 0) {
323 ret = 1;
324 break;
325 }
326 }
327 }
328 return ret;
329}

引用了 ipn_sdiv_mul1_(), ipn_sprp_1_(), LIMB_BITS, lmmp_cmp_(), lmmp_copy, lmmp_mont_redc_(), lmmp_sqr_, prod, restrict , 以及 t.

被这些函数引用 ipn_notrial_i_() , 以及 ipn_sprp_1_().

函数调用图:
这是这个函数的调用关系图:

◆ ipn_sprp_base2_()

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 )
static

单轮 Rabin-Miller 强伪素数测试(大于 128 位,基底硬编码为 2)

参数
mc蒙域上下文(含 one/m1,已完成 lmmp_mont_init_)
d(n-1)>>t(奇,探测梯子的指数窗口)
dbitsd 的位长
tv2(n-1)
u梯子累加器兼探测载体(mc->n 个limb)
prod工作区(2*mc->n 个limb,平方全积,出口被破坏)
警告
sep(u,prod), sep([u|prod], mc 内各缓冲区)
注解
蒙域 L2R 梯子:u = 2^d(蒙域剩余)。基底 2 特化为"平方 + 倍加" (蒙域乘 2 即剩余加倍 2*R ≡ 倍加,O(n) 替代一次 M(n) 蒙乘,蒙域 2 由 one 倍加而来,免去基底入蒙域的 redcify 除法)。蒙域基准 one = B^n mod n 与 m1 = n - one(即 -1 的蒙域剩余)二次探测: y ∈ {1,-1} 或 y^(2^j) = -1(0 < j < t,n-1 = d*2^t)
返回
1 = 通过基 2 的 Miller-Rabin 测试;0 = 合数

在文件 is_prime_n.c 第 142 行定义.

149 {
150 mp_size_t nn = mc->n;
151
152 /* 蒙域初值 one+one = 蒙域 2,逐位平方 + bit=1 倍加 */
153 ipn_mont_dbl_(u, mc->one, mc);
154 for (mp_bitcnt_t i = dbits - 1; i-- > 0;) {
155 lmmp_sqr_(prod, u, nn);
156 lmmp_mont_redc_(u, prod, mc);
157 if ((d[i / LIMB_BITS] >> (i % LIMB_BITS)) & 1)
158 ipn_mont_dbl_(u, u, mc);
159 }
160
161 /* 二次探测:y ∈ {1,-1} 或 y^(2^j) = -1(0 < j < t,共 t-1 次平方) */
162 int ret = 0;
163 if (lmmp_cmp_(u, mc->one, nn) == 0 || lmmp_cmp_(u, mc->m1, nn) == 0) {
164 ret = 1;
165 } else {
166 for (; t > 1; t--) {
167 lmmp_sqr_(prod, u, nn);
168 lmmp_mont_redc_(u, prod, mc);
169 if (lmmp_cmp_(u, mc->m1, nn) == 0) {
170 ret = 1;
171 break;
172 }
173 }
174 }
175 return ret;
176}

引用了 ipn_mont_dbl_(), ipn_sprp_base2_(), LIMB_BITS, lmmp_cmp_(), lmmp_mont_redc_(), lmmp_sqr_, prod, restrict , 以及 t.

被这些函数引用 ipn_notrial_i_() , 以及 ipn_sprp_base2_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_is_prime_n_()

int lmmp_is_prime_n_ ( mp_srcptr np,
mp_size_t nn,
int strength )

大整数素性检验(强度分档,大于 128 位)

参数
np待测数指针(nn 个limb)
nn待测数的 limb 长度
strength检测强度 [0,7],语义同 lmmp_is_prime_n_notrial_,强度越高理论误判率越低。 强度>=4时,已是接受集为标准 BPSW 素性(学界目前无已知反例)接受集的子集。
警告
np!=NULL, nn>2, np[nn-1]>0, 0<=strength<=7
注解
在 lmmp_is_prime_n_notrial_ 前进行小素数试除,适合随机输入或者一般情况。 建议使用强度 5 档,能够很好的平衡伪素数和素数的平均耗时。素性强度可以参照 lmmp_is_prime_n_notrial_中的说明。
返回
0 = 合数;1 = 素数(确定性判据,本契约域不可达); 2 = 极大概率为素数

在文件 is_prime_n.c 第 646 行定义.

646 {
647 lmmp_param_assert(np != NULL);
648 lmmp_param_assert(nn > 2 && np[nn - 1] > 0);
649 lmmp_param_assert(strength >= 0 && strength <= 7);
650
651 if ((np[0] & 1) == 0) return 0;
652
653 /* 小素数试除初筛:契约域 n > 2^128 大于一切表内素数,命中即合数 */
654 if (lmmp_trialdiv_(np, nn, ipn_trial_bound[strength])) return 0;
655
656 return ipn_notrial_i_(np, nn, strength);
657}
static const ushort ipn_trial_bound[8]
static int ipn_notrial_i_(mp_srcptr np, mp_size_t nn, int strength)
#define lmmp_param_assert(x)
定义 lmmp.h:509
bool lmmp_trialdiv_(mp_srcptr np, mp_size_t nn, ushort N)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 ipn_notrial_i_(), ipn_trial_bound, lmmp_is_prime_n_(), lmmp_param_assert , 以及 lmmp_trialdiv_().

被这些函数引用 bench_is_prime_n(), bench_is_prime_n_proth(), ipn_proth_i_(), lmmp_is_prime_n_(), lmmp_powmod_(), pool_n(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_is_prime_n_notrial_()

int lmmp_is_prime_n_notrial_ ( mp_srcptr np,
mp_size_t nn,
int strength )

大整数素性检验(无试除法,强度分档,大于 128 位)

参数
np待测数指针(nn 个limb)
nn待测数的 limb 长度
strength检测强度 [0,7]。随机基底 MR 分两层:"1+n" 搭配指先跑至多 x 轮 1 limb 随机基底(a in [3,B) 均匀,廉价,可尽早拒判)再跑至多 y 轮 全域(n limb 随机基底,[2,n-2] 均匀)基底。各层均为“至多”轮数,任一轮检出 合数即提前终止:
强度 基底2 MR 1 limb 基底 MR n limb 基底 MR 强 Lucas
0 √ 3 2 -
1 √ 4 3 -
2 √ 5 4 -
3 √ 6 5 -
4 √ 0 0 √
5 √ 2 0 √
6 √ 3 1 √
7 √ 4 2 √
警告
np!=NULL, nn>2, np[nn-1]>0, np[0]%2==1, 0<=strength<=7
注解
1. 不进行试除法,对于含有明显小因子的输入不会早退。建议输入不含小因子或强伪素数、半素数等。
  1. 建议实际使用强度 5 档,能够很好的平衡伪素数和素数的平均耗时,对于真素数不会耗费过长的时间, 且可以更快的过滤伪素数。该档为 BPSW 型判据(基底 2 MR 叠加强 Lucas)之上增加 2 轮 1 limb 随机基底 MR;其中 Lucas 半部含 BFW vpsp 与 Q-Euler 两项强化检查 (Baillie-Fiori-Wagstaff 2021,素数必然全过),故接受集为标准 BPSW 接受集的子集 (合数只可能多拒、不可能少拒)。
  2. 强卢卡斯判据本身和 MR 测量相当正交,因此强度档大于4时,增加更多轮次 MR 测试存在边际效应, 并不能无条件的降低 BPSW 条件下的实际误判率。更多的 MR 轮次,只承担早退的任务,对于部分 伪素数可以更早的返回,而不是进行卢卡斯检验。但对于可能通过的(伪)素数,总时间反而增加。
注意
1 limb 基底空间仅 2^64,可能存在精心构造的伪素数,使其可以通过 1 limb 基底空间的所有 MR 测试。此测试主要用于搭配全基底空间快速过滤,不承诺对抗性输入下的强度保证。
返回
0 = 合数;1 = 素数(确定性判据,本契约域不可达);2 = 极大概率为素数

在文件 is_prime_n.c 第 659 行定义.

659 {
660 lmmp_param_assert(np != NULL);
661 lmmp_param_assert(nn > 2 && np[nn - 1] > 0);
662 lmmp_param_assert(strength >= 0 && strength <= 7);
663
664 if ((np[0] & 1) == 0) return 0;
665
666 return ipn_notrial_i_(np, nn, strength);
667}

引用了 ipn_notrial_i_(), lmmp_is_prime_n_notrial_() , 以及 lmmp_param_assert.

被这些函数引用 bench_is_prime_n_notrial(), lmmp_is_prime_n_notrial_(), lmmp_powmod_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_is_prothprime_()

int lmmp_is_prothprime_ ( uint k,
mp_size_t n )

Proth 数 k*2^n+1 的素性判定(普罗斯定理)

参数
k系数(k < 2^32)
n指数(2 的幂次)
警告
k>0 且为奇数, n>0
返回
0 = 合数;1 = 素数(确定性判据,本契约域可达); 2 = 极大概率为素数(BPSW 型素数;回退路径,极少触发)

在文件 is_prime_n.c 第 768 行定义.

768 {
769 lmmp_param_assert(k > 0 && n > 0);
770 lmmp_param_assert((k & 1) == 1);
771 ulong kk = k;
773 uint bk = (uint)lmmp_limb_bits_(kk);
774
775 /* N < 2^64(ne + bitlen(kk) <= 64):确定性小数路径 */
776 if (ne + bk <= 64) return lmmp_is_prime_ulong_((kk << ne) + 1) ? 1 : 0;
777
778 /* ne < 64:kk 簇低位与 limb0 的 1 共享 limb(N < 2^32*2^63 < 2^96,恰
779 双 limb),非稀疏形状——走 lmmp_is_prime_2_ 三态路径值透传
780 (<SWbound 确定性返回 1,之上 BPSW 型返回 2) */
781 if (ne < 64) {
782 u128 N = ((u128)kk << ne) + 1;
783 return lmmp_is_prime_2_((mp_limb_t)N, (mp_limb_t)(N >> 64));
784 }
785
786 /* 普罗斯定理驱动域:ne >= 64 ⟹ N >= 2^64 且 limb0 恒为纯 1(kk 簇整
787 体位于 limb >= 1,稀疏形状必命中),nn >= 2,kk < 2^32 <= 2^ne(定
788 理条件 k 奇、k < 2^t 自动成立)。装配 N = kk*2^ne + 1 */
789 mp_size_t nn = (mp_size_t)((ne + bk - 1) / LIMB_BITS) + 1;
790 TEMP_DECL;
791 mp_ptr np = TALLOC_TYPE(nn, mp_limb_t);
792 lmmp_zero(np, nn);
793 np[0] = 1;
794 mp_size_t w = (mp_size_t)(ne / LIMB_BITS);
795 mp_bitcnt_t s = ne % LIMB_BITS;
796 if (s == 0) {
797 np[w] = (mp_limb_t)kk;
798 } else {
799 np[w] |= (mp_limb_t)(kk << s);
800 mp_limb_t hi = (mp_limb_t)(kk >> (LIMB_BITS - s));
801 if (hi) np[w + 1] = hi; /* hi != 0 ⟺ 顶位跨 limb ⟺ w+1 == nn-1 */
802 }
803 int ret = ipn_proth_i_(np, nn, kk, ne);
804 TEMP_FREE;
805 return ret;
806}
#define k
static int ipn_proth_i_(mp_srcptr np, mp_size_t nn, ulong kk, mp_bitcnt_t ne)
bool lmmp_is_prime_ulong_(ulong n)
判断素数

引用了 ipn_proth_i_(), k, LIMB_BITS, lmmp_is_prime_2_(), lmmp_is_prime_ulong_(), lmmp_is_prothprime_(), lmmp_limb_bits_, lmmp_param_assert, lmmp_zero, n, s, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 bench_is_prothprime(), lmmp_is_prothprime_(), lmmp_powmod_(), pool_proth(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_is_strong_lucas_()

int lmmp_is_strong_lucas_ ( mp_srcptr np,
mp_size_t nn )

强 Lucas-Selfridge 测试(大于 128 位)

参数
np待测奇数指针(nn 个limb)
nn待测数的 limb 长度
警告
np!=NULL, nn>2, np[nn-1]>0, np[0]%2==1
注解
Selfridge 方法 A:P=1,Q=(1-D)/4,D 取 5,-7,9,-11,... 中首个 (D|n)=-1 者;V-only 阶梯实现,判据与标准 U/V 强 Lucas 测试精确一致 (U_d=0 经 P=1 恒等式 D*U_d = 2V_{d+1} - V_d 以 2V_{d+1}=V_d 检出), 判据命中后叠加 BFW vpsp(V_{n+1}=2Q)与 Q-Euler(Q^{(n+1)/2}=+-Q) 两项强化检查(Baillie-Fiori-Wagstaff 2021,素数必然全过)。 判定合数的情形含 gcd(|D|,n)>1 与 n 为完全平方数。 单轮成本约为单轮 MR 的 1.6~2 倍
返回
1 = 通过强 Lucas 测试;0 = 合数

在文件 is_prime_n.c 第 506 行定义.

506 {
507 lmmp_param_assert(np != NULL);
508 lmmp_param_assert(nn > 2 && np[nn - 1] > 0);
509 lmmp_param_assert(np[0] % 2 == 1);
510
511 TEMP_DECL;
512 lmmp_mont_t mc;
513 ipn_sdiv_t sd;
514 mp_size_t mn = lmmp_mont_need_(nn, 1);
515 mp_ptr restrict arena = TALLOC_TYPE(mn + 2 * nn, mp_limb_t);
516 lmmp_mont_init_(&mc, np, nn, arena, 1, arena + mn);
517 ipn_sdiv_init_(&sd, np, nn);
518 int ret = ipn_lucas_i_(np, nn, &mc, &sd, arena + mn);
519 lmmp_mont_free_(&mc);
520 TEMP_FREE;
521 return ret;
522}

引用了 ipn_lucas_i_(), ipn_sdiv_init_(), lmmp_is_strong_lucas_(), lmmp_param_assert, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

被这些函数引用 bench_is_strong_lucas(), lmmp_is_strong_lucas_(), lmmp_powmod_() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

变量说明

◆ ipn_r1_rounds

const uchar ipn_r1_rounds[8] = {3, 4, 5, 6, 0, 2, 3, 4}
static

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 is_prime_n.c 第 60 行定义.

被这些函数引用 ipn_notrial_i_().

◆ ipn_rn_rounds

const uchar ipn_rn_rounds[8] = {2, 3, 4, 5, 0, 0, 1, 2}
static

在文件 is_prime_n.c 第 63 行定义.

被这些函数引用 ipn_notrial_i_().

◆ ipn_trial_bound

const ushort ipn_trial_bound[8] = {100, 300, 1000, 3000, 1000, 3000, 5000, 10000}
static

在文件 is_prime_n.c 第 70 行定义.

被这些函数引用 lmmp_is_prime_n_().