LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime_n.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/*
24 强度分档(strength ∈ [0,7],随机基底取自全局 RNG)。随机轮分两层:
25 先跑至多 x 轮 1 limb 基底(a ∈ [3,B) 均匀,单轮最廉,尽早拒判),再跑
26 至多 y 轮全域(n limb,[2,n-2] 均匀)基底:
27 档 | 基底2 MR | 1 limb 轮 | n limb 轮 | 强 Lucas | 试除上界
28 0 | √ | 3 | 2 | - | 100
29 1 | √ | 4 | 3 | - | 300
30 2 | √ | 5 | 4 | - | 1000
31 3 | √ | 6 | 5 | - | 3000
32 4 | √ | - | - | √ | 1000
33 5 | √ | 2 | 0 | √ | 3000
34 6 | √ | 3 | 1 | √ | 5000
35 7 | √ | 4 | 2 | √ | 10000
36 各档均先做基底 2 特化 MR;"至多 N 轮"指任一轮检出合数即提前终止,
37 实际执行轮数不超过 N。试除上界随强度递增:高强度下幸存者代价更大
38 (更多轮次/含 Lucas),更深的初筛以近零代价换更高的提前淘汰率。
39 各档独立基底轮总数(含基底 2)为 s0..s3 = 6/8/10/12、s4..s7 = 1/3/5/7;
40 1 limb 基底空间仅 2^64,由 AGP 定理(无穷多合数的最小 MR 见证
41 > (log n)^(1/3))知窄基底类的最坏/对抗情形弱于全宽随机轮,本"1+n"
42 搭配定位于随机候选(keygen)场景。
43
44 Proth 形状独立入口 lmmp_is_prothprime_(k, n)(判 k*2^n+1,k 奇 < 2^32,
45 契约 k>0 奇、n>0)
46*/
47
48#include "impl/tmp_alloc.h"
49#include "impl/inlines.h"
50#include "impl/longlong.h"
51#include "numth/powmod.h"
52#include "impl/rand_state.h"
53#include "impl/trialdiv.h"
54#include "lmmp/lmmpn.h"
55#include "lmmp/mprand.h"
56#include "lmmp/numth.h"
57
58
59/* 1 limb 基底随机 MR 轮数上限(检出合数提前终止) */
60static const uchar ipn_r1_rounds[8] = {3, 4, 5, 6, 0, 2, 3, 4};
61
62/* 全域(n limb,[2,n-2] 均匀)基底随机 MR 轮数上限(检出合数提前终止) */
63static const uchar ipn_rn_rounds[8] = {2, 3, 4, 5, 0, 0, 1, 2};
64
65/*
66FIXME: 不使用固定的试除上限,而是根据输入的长度来决定试除多少
67*/
68
69/* 小素数试除上界(N 传给 lmmp_trialdiv_,即试除 <= N 的全部素数) */
70static const ushort ipn_trial_bound[8] = {100, 300, 1000, 3000, 1000, 3000, 5000, 10000};
71
72/* 蒙域加倍 x+x-m。值 < 2m:进位回绕(2x >= B^n)时 B^n 与 m 的差额由
73 减法借位在 B^n 下恰巧抵消,回绕结果即 2x-m(见 is_prime_2.c mont2_dbl)*/
74static inline void ipn_mont_dbl_(mp_ptr dst, mp_srcptr x, const lmmp_mont_t* restrict mc) {
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}
81
82/* 蒙域模减 a-b(a,b < m):借位回绕由加 m 补偿,结果 < m */
83static inline void ipn_mont_sub_(mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t* restrict mc) {
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}
88
89/* 蒙域取负 m-x(x != 0,结果 < m) */
90static inline void ipn_mont_neg_(mp_ptr dst, mp_srcptr x, const lmmp_mont_t* restrict mc) {
91 (void)lmmp_sub_n_(dst, mc->m, x, mc->n);
92}
93
94/* 蒙域模加 a+b(a,b < m)。和 < 2m < B^n+m:进位回绕(和 >= B^n)时
95 回绕值 < m,随后减 m 的借位在 B^n 下恰好补回,回绕结果即 a+b-m */
96static inline void ipn_mont_add_(mp_ptr dst, mp_srcptr a, mp_srcptr b, const lmmp_mont_t* restrict mc) {
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}
103
104/* 蒙域值模 n 折半 x <- x/2 mod n(n 奇:x 偶直接移位;x 奇先加 n 再移,
105 加法进位跨 limb 并入移位高位,B^n 回绕无损:真值 < 2n < 2B^n 且折半
106 后 < B^n 可表示) */
107static inline void ipn_mont_half_(mp_ptr x, const lmmp_mont_t* restrict mc) {
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}
113
114/* d 低位起 0 的个数;调用前应保证 [dp,n] != 0 */
115static inline mp_bitcnt_t ipn_ctz_(mp_srcptr dp) {
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}
120
121static inline mp_size_t ipn_norm_(mp_srcptr dp, mp_size_t dn) {
122 while (dn > 0 && dp[dn - 1] == 0) dn--;
123 return dn;
124}
125
126/**
127 * @brief 单轮 Rabin-Miller 强伪素数测试(大于 128 位,基底硬编码为 2)
128 * @param mc 蒙域上下文(含 one/m1,已完成 lmmp_mont_init_)
129 * @param d (n-1)>>t(奇,探测梯子的指数窗口)
130 * @param dbits d 的位长
131 * @param t v2(n-1)
132 * @param u 梯子累加器兼探测载体(mc->n 个limb)
133 * @param prod 工作区(2*mc->n 个limb,平方全积,出口被破坏)
134 * @warning sep(u,prod), sep([u|prod], mc 内各缓冲区)
135 * @note 蒙域 L2R 梯子:u = 2^d(蒙域剩余)。基底 2 特化为"平方 + 倍加"
136 * (蒙域乘 2 即剩余加倍 2*R ≡ 倍加,O(n) 替代一次 M(n) 蒙乘,蒙域 2
137 * 由 one 倍加而来,免去基底入蒙域的 redcify 除法)。蒙域基准
138 * one = B^n mod n 与 m1 = n - one(即 -1 的蒙域剩余)二次探测:
139 * y ∈ {1,-1} 或 y^(2^j) = -1(0 < j < t,n-1 = d*2^t)
140 * @return 1 = 通过基 2 的 Miller-Rabin 测试;0 = 合数
141 */
144 mp_srcptr d,
145 mp_bitcnt_t dbits,
147 mp_ptr u,
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}
177
178/* 短除上下文:归一化除数顶 2 limb 及其 2/1 逆元(1 limb 基底路径专用) */
179typedef struct {
180 mp_srcptr n; /* 模数 [n,nn](奇,顶 limb 非零,nn>=3) */
181 mp_limb_t d1; /* [n,nn]<<sh 的顶 limb(MSB 置 1) */
182 mp_limb_t d0; /* [n,nn]<<sh 的次顶 limb */
183 mp_limb_t dinv; /* (B^3-1)/(d1*B+d0) - B(_udiv_qr_3by2 的 dinv) */
184 mp_size_t nn; /* 模数 limb 长度 */
185 mp_bitcnt_t sh; /* clz(n[nn-1]) */
186} ipn_sdiv_t;
187
188/**
189 * @brief 短除上下文初始化:归一化除数顶 2 limb 与其 2/1 逆元
190 * @param sd 上下文
191 * @param np 模数(nn 个limb)
192 * @param nn 模数 limb 长度
193 * @warning np!=NULL, nn>2, np[nn-1]>0, np[0]%2==1
194 */
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}
209
210/**
211 * @brief 蒙域内乘裸 1 limb 标量:x <- x*a mod n(结果仍是蒙域剩余)
212 * @param x 蒙域剩余(nn 个limb,原地读写)
213 * @param a 裸标量(a < B)
214 * @param sd 短除上下文
215 * @warning x < [sd->n,sd->nn], sep(x,sd->n)
216 * @note 估商与回补的界见本节顶部注;"乘减 q*n"大操作数 n 在前、标量 q 在后
217 */
218static inline void ipn_sdiv_mul1_(mp_ptr x, mp_limb_t a, const ipn_sdiv_t* sd) {
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}
251
253 mp_ptr restrict dst,
255 ulong qabs,
256 int qneg,
257 const lmmp_mont_t* mc,
258 const ipn_sdiv_t* sd
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}
273
274/**
275 * @brief 短基底 MR 单轮:基底为 1 limb 裸标量,梯子与探测全程蒙域
276 * @param mc 蒙域上下文(含 one/m1,已完成 lmmp_mont_init_)
277 * @param sd 短除上下文(ipn_sdiv_init_ 就绪,模数同 mc)
278 * @param a 基底(1 个limb,a < B)
279 * @param d (n-1)>>t(奇)
280 * @param dbits d 的位长
281 * @param t v2(n-1)
282 * @param u 梯子累加器兼探测载体(mc->n 个limb)
283 * @param prod 工作区(2*mc->n 个limb,平方全积,出口被破坏)
284 * @warning 2 <= a <= [mc->m,mc->n]-2(契约域 n > 2^128 > B 恒成立),
285 * sep(u,prod), sep([u|prod], mc 内各缓冲区)
286 * @return 1 = 通过该基底的 Miller-Rabin 测试;0 = 合数
287 * @note SPRP 判据与基底 2 轮一致:u ∈ {one,m1} 或 u^(2^j) 命中 m1
288 */
289static int ipn_sprp_1_(
291 const ipn_sdiv_t* sd,
292 mp_limb_t a,
293 mp_srcptr d,
294 mp_bitcnt_t dbits,
296 mp_ptr u,
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}
330
331/* (b|A) 二进制算法:A 奇,b < A(移位/比较/减法,几次迭代),
332 与 is_prime_2.c 的 jacobi_small 同源 */
333static inline int ipn_jacobi_small_(ulong b, ulong A) {
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}
351
352/*
353 (±Dabs|n):Dabs 奇(uint 范围),n 为 nn limb 奇数。[np,nn] 经
354 lmmp_mod_1_ 折叠到 mod |D|(预逆除法,O(nn)),再经二次互反律
355 (A|n) = (n|A)*(-1)^(((A-1)/2)((n-1)/2)) 归结到 (n mod A | A);
356 D 为负时乘 (-1|n) 因子。gcd(|D|,n)>1 返回 0
357*/
358LMMP_NOINLINE static int ipn_jacobi_D_(uint Dabs, int Dneg, mp_srcptr np, mp_size_t nn) {
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}
368
369/*
370 强 Lucas-Selfridge 测试(U 阶梯,Hackman 平方型公式,P=1 特化)。
371 阶梯递推(蒙域,Q 仅以小标量出现,Q^k 链整体取消,Q^d 于末尾一次性恢复):
372 U_{2k} = U_{k+1}^2 - (U_{k+1}-U_k)^2
373 U_{2k+1} = U_{k+1}^2 - Q*U_k^2
374 U_{2k+2} = U_{2k+1} - Q*U_{2k}(bit=1 时经递推免去第三次平方)
375 每 bit 3 次平方 + 3 次 REDC + O(n) 标量运算(V/Q 双阶梯旧结构为
376 4 次乘族 + 4 次 REDC)。D 搜索:非完全平方的 n 其 Jacobi 特征
377 非平凡,序列中必存在 (D|n) = -1,搜索必然终止;完全平方是唯一
378 不终止情形,经 Dabs==17 处的延迟检测排除(lmmp_perfsqr_,不进
379 常见路径;固定小上界不可行)
380*/
381static int ipn_lucas_i_(
382 mp_srcptr np,
383 mp_size_t nn,
385 const ipn_sdiv_t* sd,
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}
505
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}
523
524LMMP_NOINLINE static int ipn_notrial_i_(mp_srcptr np, mp_size_t nn, int strength) {
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}
645
646int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength) {
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}
658
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}
668
669/*
670 普罗斯定理:N = k*2^t+1(k 奇,k < 2^t)为素数 ⟺ 存在 a 使
671 a^((N-1)/2) ≡ -1 (mod N)。正向(≡ -1 ⟹ N 素)为 Pocklington 型
672 阶论证,无需分解 k:任一素因子 p 满足 ord_p(a) | N-1 且
673 ∤ (N-1)/2,故 v2(ord_p(a)) = t,2^t | p-1,p >= 2^t+1 > sqrt(N)
674 (k < 2^t ⟹ N < 2^(2t)+1),与合数必有不超 sqrt(N) 的素因子矛盾。
675 反向仅在 Jacobi(a,N) = -1 的见证上成立(N 素时 Euler 判据强制
676 a^((N-1)/2) ≡ (a|N) = -1):故 Jacobi = 0 即 gcd(a,N) > 1 判合数
677 (本域 a < N 恒成立),首个 Jacobi = -1 的奇数 a 上单条梯子出双
678 方向定论;Jacobi = +1 的基对判决无贡献(素数给 +1,平方数亦恒给
679 +1,(a|p^2) = (a|p)^2 且 a^((p^2-1)/2) = (±1)^(p+1) = +1,两侧
680 不可区分),直接跳过。
681
682 见证搜索沿奇数 a = 3,5,7,... 至防御上界 IPN_PROTH_WITNESS_MAX。
683 终止性:唯一无 -1 见证的情形是 N 为完全平方,而本域(N >= 2^64,
684 kk < 2^32,ne = t >= 64)内平方不可能——若 N = p^2 且
685 (p-1)(p+1) = kk*2^t,记 p-1 = 2^a*u、p+1 = 2^b*v(u,v 奇,{a,b} 含 1),
686 p >= 2^32 与 uv = kk < 2^32 联立迫使小 v2 侧奇部 >= 2^31、
687 另一侧奇部 = 1,只剩 p ∈ {2^32-1, 2^33-1, 2^32+1},均非素——
688 故 (·|N) 非平凡,必有奇素数见证 < N,搜索有限步终止(实际首见证个位数到几十)。
689
690 梯子结构:指数 (N-1)/2 = k*2^(t-1) 低 t-1 位全零——k 部分(<= 32
691 位)走 L2R 二进制梯(乘底至多 31 次全宽乘,占梯子份额可忽略,故
692 不做窗口/短乘特化),尾部 t-1 步为纯平方链。全程蒙域,终点与 m1
693 (蒙域 -1)比较,免出蒙域归约;指数无需物化为 limb 数组,两段
694 循环由 kk 与 ne 直接驱动。
695
696 蒙域上下文走稀疏模数旁路(lmmp_mont_sp_t):驱动域内 N = 1 +
697 (kk<<s)·B^p 恒命中 +1 形(kk < 2^32 ⟹ 簇 <= 2 limb),REDC 每步
698 O(n)(伸缩恒等式坍缩,见 impl/powmod.h 稀疏节注释),梯子整体
699 平方主导;m1(蒙域 -1)经一次 redcify 除法装配 one 后取 N − one,
700 不经 lmmp_mont_t 的通用三层分派。
701*/
702
703#define IPN_PROTH_WITNESS_MAX 65535u
704
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}
767
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
#define prod
#define A
#define bn
#define lmmp_limb_bits_
#define lmmp_leading_zeros_
#define lmmp_mul_n_
#define lmmp_sqr_
#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)
mp_bitcnt_t sh
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)
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LIMB_MAX
定义 lmmp.h:105
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_NOINLINE
定义 lmmp.h:216
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#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
定义 shr.c:26
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
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
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
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_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27
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
#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 均匀分布)
#define r1
#define r0
#define b2
#define t
#define s
#define n
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
uint32_t uint
定义 numth.h:38
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 位)
uint16_t ushort
定义 numth.h:36
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
bool lmmp_is_prime_ulong_(ulong n)
判断素数
uint64_t ulong
定义 numth.h:39
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)
奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
mp_size_t n
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_randlimb_(void)
依据全局状态获取单个随机limb(0 - B 均匀分布)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)
bool lmmp_trialdiv_(mp_srcptr np, mp_size_t nn, ushort N)
Copyright (C) 2026 HJimmyK (Jericho Knox)