LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mul_mersenne.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 "mparam.h"
25#include "impl/tmp_alloc.h"
26#include "lmmpn/fft_ssa.h"
27#include "lmmp/lmmpn.h"
28
29
30/**
31 * @brief 判断 n 是否为费马变换可行尺寸(64n 能被 2^best_k 整除)
32 * @param n 输入的 limb 长度
33 * @return 1 可行 / 0 不可行
34 */
37 return (n & (((mp_size_t)1 << k) - 1)) == 0;
38}
39
40/**
41 * @brief 取负 [dst,n] = B^n - [numa,n],返回进位(= [numa,n] != 0)
42 * @param dst 输出缓冲区,长度至少为 n
43 * @param numa 输入操作数,长度为 n
44 * @param n 操作数的 limb 长度
45 * @warning n>0, sep/eqsep(dst,numa)
46 */
48 if (lmmp_zero_q_(numa, n)) {
49 lmmp_zero(dst, n);
50 return 0;
51 }
52 // B^n - x = ~x + 1;x!=0 保证 ~x+1 不越过 n limb
53 lmmp_not_(dst, numa, n);
54 lmmp_inc(dst);
55 return 1;
56}
57
58/**
59 * @brief mod B^n+1 基例乘法 [rp,n+1] = [ap,n+1]*[bp,n+1] mod B^n+1(规范形 [0,B^n])
60 * @param rp 输出缓冲区,长度至少为 n+1
61 * @param ap 第一个操作数(高半域形,值 < B^n+1),长度为 n+1
62 * @param bp 第二个操作数,长度为 n+1
63 * @param n 模运算的阶数
64 * @param tp 工作区,长度至少为 2n(允许 tp==rp)
65 * @warning n>0, sep(tp,[ap|bp]) 或 tp==rp
66 * @note 顶位特例:ap/bp 顶 limb 为 1(值 = B^n ≡ -1)时以取反代乘
67 */
69 mp_limb_t cy;
70 if (ap[n] | bp[n]) {
71 if (ap[n])
72 cy = bp[n] + mrs_neg_(rp, bp, n);
73 else // ap[n]==0
74 cy = mrs_neg_(rp, ap, n);
75 } else {
76 lmmp_mul_n_(tp, ap, bp, n);
77 cy = lmmp_sub_n_(rp, tp, tp + n, n);
78 }
79 rp[n] = 0;
80 // cy==1 时 rp = lo-hi+B^n <= B^n-1,再 +1 不会越过 rp[n]
81 lmmp_inc_1(rp, cy);
82}
83
84/**
85 * @brief mod B^n+1 基例平方 [rp,n+1] = [ap,n+1]^2 mod B^n+1(规范形 [0,B^n])
86 * @param rp 输出缓冲区,长度至少为 n+1
87 * @param ap 操作数(高半域形,值 < B^n+1),长度为 n+1
88 * @param n 模运算的阶数
89 * @param tp 工作区,长度至少为 2n(允许 tp==rp)
90 * @warning n>0, sep(tp,ap) 或 tp==rp
91 * @note 顶位特例:ap 顶 limb 为 1(值 ≡ -1)时结果为 1
92 */
94 mp_limb_t cy;
95 if (ap[n]) { // (-1)^2 = 1
96 rp[0] = 1;
97 lmmp_zero(rp + 1, n);
98 return;
99 }
100 lmmp_sqr_(tp, ap, n);
101 cy = lmmp_sub_n_(rp, tp, tp + n, n);
102 rp[n] = 0;
103 lmmp_inc_1(rp, cy);
104}
105
106/**
107 * @brief 分治梅森乘法核心(半归一化内部约定:零类 = B^n-1)
108 * @param rp 输出 [rp,rn] = [ap,an]*[bp,bn] mod B^rn-1(半归一化,写入完整 rn limb)
109 * @param rn 模运算的阶数
110 * @param ap 第一个操作数
111 * @param an 第一个操作数的 limb 长度
112 * @param bp 第二个操作数
113 * @param bn 第二个操作数的 limb 长度
114 * @param tp 工作区,长度至少为 2rn+4
115 * @warning 0<bn<=an<=rn, an+bn>rn/2, sep(rp,[ap|bp]), sep(tp,[rp|ap|bp])
116 */
118 if ((rn & 1) != 0 || rn < MUL_MERSENNE_DC_THRESHOLD) {
119 if (bn < rn) {
120 if (an + bn <= rn) {
121 // an+bn<=rn 蕴含 (B^an-1)(B^bn-1) < B^rn-1,积即精确残差
122 lmmp_mul_(rp, ap, an, bp, bn);
123 lmmp_zero(rp + an + bn, rn - (an + bn));
124 } else {
125 lmmp_mul_(tp, ap, an, bp, bn);
126 mp_limb_t cy = lmmp_add_(rp, tp, rn, tp + rn, an + bn - rn);
127 lmmp_inc_1(rp, cy);
128 }
129 } else {
130 lmmp_mul_n_(tp, ap, bp, rn);
131 mp_limb_t cy = lmmp_add_n_(rp, tp, tp + rn, rn);
132 // cy==1 时 rp <= B^rn-2,+1 不会溢出
133 lmmp_inc_1(rp, cy);
134 }
135 return;
136 }
137
138 mp_size_t n = rn >> 1;
139 mp_limb_t cy;
141
142 /*
143 x = -xp * B^n + (B^n + 1) * [ (xp + xm)/2 mod (B^n-1)]
144 */
145#define a0 ap
146#define a1 (ap + n)
147#define b0 bp
148#define b1 (bp + n)
149#define xp tp /* 2n+2 */
150 /* am1 maybe in {xp, n} */
151 /* bm1 maybe in {xp + n, n} */
152#define sp1 (tp + 2 * n + 2)
153 /* ap1 maybe in {sp1, n + 1} */
154 /* bp1 maybe in {sp1 + n + 1, n + 1} */
155
156 {
157 // xm = a*b mod (B^n-1)
159 mp_size_t anm, bnm;
160 mp_ptr so;
161
162 bm1 = b0;
163 bnm = bn;
164 if (an > n) {
165 am1 = xp;
166 cy = lmmp_add_(xp, a0, n, a1, an - n);
167 lmmp_inc_1(xp, cy);
168 anm = n;
169 so = xp + n;
170 if (bn > n) {
171 bm1 = so;
172 cy = lmmp_add_(so, b0, n, b1, bn - n);
173 lmmp_inc_1(so, cy);
174 bnm = n;
175 so += n;
176 }
177 } else {
178 so = xp;
179 am1 = a0;
180 anm = an;
181 }
182
183 mrs_mul_core_(rp, n, am1, anm, bm1, bnm, so);
184 }
185
186 {
187 // xp = a*b mod (B^n+1),规范形 [xp,n+1] in [0,B^n]
189 mp_size_t anp, bnp;
190
191 bp1 = b0;
192 bnp = bn;
193 if (an > n) {
194 ap1 = sp1;
195 cy = lmmp_sub_(sp1, a0, n, a1, an - n);
196 sp1[n] = 0;
197 lmmp_inc_1(sp1, cy);
198 anp = n + sp1[n];
199 if (bn > n) {
200 bp1 = sp1 + n + 1;
201 cy = lmmp_sub_(sp1 + n + 1, b0, n, b1, bn - n);
202 sp1[2 * n + 1] = 0;
203 lmmp_inc_1(sp1 + n + 1, cy);
204 bnp = n + bp1[n];
205 }
206 } else {
207 ap1 = a0;
208 anp = an;
209 }
210
212 lmmp_mul_fermat_(xp, n, ap1, anp, bp1, bnp);
213 } else if (bp1 == b0) {
214 // bn<=n:直乘 + 反向折叠
215 lmmp_mul_(xp, ap1, anp, bp1, bnp);
216 anp = anp + bnp - n;
217 lmmp_debug_assert(anp <= n || xp[2 * n] == 0);
218 anp -= anp > n;
219 cy = lmmp_sub_(xp, xp, n, xp + n, anp);
220 xp[n] = 0;
221 lmmp_inc_1(xp, cy);
222 } else {
223 mrs_mul_bnp1_(xp, ap1, bp1, n, xp);
224 }
225 }
226
227 // xm <- (xp + xm)/2 = (xp + xm)*B^n/2 mod (B^n-1),除2即循环右移(B^n=1)
228 // [xp,n+1] 已规范形,[rp,n] 半归一化;零类(B^n-1)在半域表示下依旧成立
229 cy = lmmp_shr1add_nc_(rp, rp, xp, n, xp[n]);
230 cy <<= LIMB_BITS - 1;
231 rp[n - 1] += cy;
232 if (rp[n - 1] < cy) // 仅当 rp[n-1] 溢出时进位,此时 [rp,n) 不可能全 B-1
233 lmmp_inc(rp);
234
235 // 高半段 = ([(xp+xm)/2 mod B^n-1] - xp) * B^n
236 if (an + bn < rn) {
237 // 此情形下结果为零当且仅当某操作数为零,且两路递归与 CRT 输出均为 0 而非 B^rn-1
238 // 值只占 [rp,an+bn);GMP 同构实现仅保证写 MIN(rn,an+bn) limb,此处补零至 rn
239 cy = lmmp_sub_n_(rp + n, rp, xp, an + bn - n);
240 // 高段相减只为取得借位链,值本身无意义
241 cy = xp[n] + lmmp_sub_nc_(xp + an + bn - n, rp + an + bn - n, xp + an + bn - n, rn - (an + bn), cy);
242 cy = lmmp_sub_1_(rp, rp, an + bn, cy);
243 lmmp_zero(rp + an + bn, rn - (an + bn));
244 } else {
245 cy = xp[n] + lmmp_sub_n_(rp + n, rp, xp, n);
246 // cy==2 不可能:xp[n]==1 蕴含 [xp,n]==0,即 [rp,n]!=0 时减法必不借位
247 // cy==1 时 DECR 至多波及最低 n limb
248 lmmp_dec_1(rp, cy);
249 }
250
251#undef a0
252#undef a1
253#undef b0
254#undef b1
255#undef xp
256#undef sp1
257}
258
259/**
260 * @brief 分治梅森平方核心(半归一化内部约定:零类 = B^n-1)
261 * @param rp 输出 [rp,rn] = [ap,an]^2 mod B^rn-1(半归一化,写入完整 rn limb)
262 * @param rn 模运算的阶数
263 * @param ap 操作数
264 * @param an 操作数的 limb 长度
265 * @param tp 工作区,长度至少为 2rn+4
266 * @warning 0<an<=rn, 4*an>rn, sep(rp,ap), sep(tp,[rp|ap])
267 */
269 if ((rn & 1) != 0 || rn < SQR_MERSENNE_DC_THRESHOLD) {
270 if (an < rn) {
271 if (2 * an <= rn) {
272 // (B^an-1)^2 < B^rn-1,平方即精确残差
273 lmmp_sqr_(rp, ap, an);
274 lmmp_zero(rp + 2 * an, rn - 2 * an);
275 } else {
276 lmmp_sqr_(tp, ap, an);
277 mp_limb_t cy = lmmp_add_(rp, tp, rn, tp + rn, 2 * an - rn);
278 lmmp_inc_1(rp, cy);
279 }
280 } else {
281 lmmp_sqr_(tp, ap, rn);
282 mp_limb_t cy = lmmp_add_n_(rp, tp, tp + rn, rn);
283 lmmp_inc_1(rp, cy);
284 }
285 return;
286 }
287
288 mp_size_t n = rn >> 1;
289 mp_limb_t cy;
290 lmmp_debug_assert(2 * an > n);
291
292#define a0 ap
293#define a1 (ap + n)
294#define xp tp /* 2n+2 */
295 /* am1 maybe in {xp, n} */
296#define sp1 (tp + 2 * n + 2)
297 /* ap1 maybe in {sp1, n + 1} */
298
299 {
300 // xm = a^2 mod (B^n-1)
302 mp_size_t anm;
303 mp_ptr so;
304
305 if (an > n) {
306 so = xp + n;
307 am1 = xp;
308 cy = lmmp_add_(xp, a0, n, a1, an - n);
309 lmmp_inc_1(xp, cy);
310 anm = n;
311 } else {
312 so = xp;
313 am1 = a0;
314 anm = an;
315 }
316
317 mrs_sqr_core_(rp, n, am1, anm, so);
318 }
319
320 {
321 // xp = a^2 mod (B^n+1),规范形 [xp,n+1] in [0,B^n]
323 mp_size_t anp;
324
325 if (an > n) {
326 ap1 = sp1;
327 cy = lmmp_sub_(sp1, a0, n, a1, an - n);
328 sp1[n] = 0;
329 lmmp_inc_1(sp1, cy);
330 anp = n + sp1[n];
331 } else {
332 ap1 = a0;
333 anp = an;
334 }
335
337 lmmp_sqr_fermat_(xp, n, ap1, anp);
338 } else if (ap1 == a0) {
339 // an<=n:直乘平方 + 反向折叠
340 lmmp_sqr_(xp, a0, an);
341 anp = 2 * an - n;
342 cy = lmmp_sub_(xp, xp, n, xp + n, anp);
343 xp[n] = 0;
344 lmmp_inc_1(xp, cy);
345 } else {
346 mrs_sqr_bnp1_(xp, ap1, n, xp);
347 }
348 }
349
350 // xm <- (xp + xm)/2 mod (B^n-1),同乘法版 CRT
351 cy = lmmp_shr1add_nc_(rp, rp, xp, n, xp[n]);
352 cy <<= LIMB_BITS - 1;
353 rp[n - 1] += cy;
354 if (rp[n - 1] < cy)
355 lmmp_inc(rp);
356
357 if (2 * an < rn) {
358 // 值只占 [rp,2an),补零至 rn(同乘法版注释)
359 cy = lmmp_sub_n_(rp + n, rp, xp, 2 * an - n);
360 cy = xp[n] + lmmp_sub_nc_(xp + 2 * an - n, rp + 2 * an - n, xp + 2 * an - n, rn - 2 * an, cy);
361 cy = lmmp_sub_1_(rp, rp, 2 * an, cy);
362 lmmp_zero(rp + 2 * an, rn - 2 * an);
363 } else {
364 cy = xp[n] + lmmp_sub_n_(rp + n, rp, xp, n);
365 lmmp_dec_1(rp, cy);
366 }
367
368#undef a0
369#undef a1
370#undef xp
371#undef sp1
372}
373
374/**
375 * @brief 零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示)
376 * @param p 输入输出缓冲区,长度为 n
377 * @param n limb 长度
378 */
380 mp_size_t i = 0;
381 while (i < n && p[i] == ~(mp_limb_t)0) ++i;
382 if (i == n) lmmp_zero(p, n);
383}
384
386 lmmp_param_assert(na > 0 && nb > 0);
387 lmmp_param_assert(nb <= na && na <= rn);
388 lmmp_param_assert(dst != NULL && numa != NULL && numb != NULL);
389 lmmp_debug_assert(na + nb > rn / 2);
390
391 mp_ptr tp = ALLOC_TYPE(2 * rn + 4, mp_limb_t);
392 mrs_mul_core_(dst, rn, numa, na, numb, nb, tp);
393 mrs_norm_zero_(dst, rn);
394 lmmp_free(tp);
395}
396
398 lmmp_param_assert(na > 0 && na <= rn);
399 lmmp_param_assert(dst != NULL && numa != NULL);
400 lmmp_debug_assert(4 * na > rn);
401
402 mp_ptr tp = ALLOC_TYPE(2 * rn + 4, mp_limb_t);
403 mrs_sqr_core_(dst, rn, numa, na, tp);
404 mrs_norm_zero_(dst, rn);
405 lmmp_free(tp);
406}
407
409 if (n < MUL_MERSENNE_DC_THRESHOLD) return n;
410 if (n < 4 * (MUL_MERSENNE_DC_THRESHOLD - 1) + 1) return (n + 1) & ~(mp_size_t)1;
411 if (n < 8 * (MUL_MERSENNE_DC_THRESHOLD - 1) + 1) return (n + 3) & ~(mp_size_t)3;
412 mp_size_t nh = (n + 1) >> 1;
413 if (nh < MUL_FFT_MODF_THRESHOLD) return (n + 7) & ~(mp_size_t)7;
414 return 2 * lmmp_fft_next_size_(nh);
415}
416
418 if (na < nb) {
419 mp_srcptr tp = numa;
420 mp_size_t tn = na;
421 numa = numb;
422 na = nb;
423 numb = tp;
424 nb = tn;
425 }
426 /* fft 分支要求 rn 为 fft 可行尺寸(缓存结构与 mersenne_next_size 的粗粒度
427 输出均不保证),未对齐时回落 dc(任意 rn 合法) */
428 if (rn >= MUL_MERSENNE_FFT_THRESHOLD && lmmp_fft_next_size_(rn) == rn)
429 lmmp_mul_mersenne_fft_(dst, rn, numa, na, numb, nb);
430 else
431 lmmp_mul_mersenne_dc_(dst, rn, numa, na, numb, nb);
432}
433
435 if (rn >= SQR_MERSENNE_FFT_THRESHOLD && lmmp_fft_next_size_(rn) == rn)
436 lmmp_sqr_mersenne_fft_(dst, rn, numa, na);
437 else
438 lmmp_sqr_mersenne_dc_(dst, rn, numa, na);
439}
#define k
#define rp
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
#define an
#define bn
#define lmmp_mul_n_
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
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
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define LOG2_LIMB_BITS
定义 lmmp.h:104
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define SQR_MERSENNE_FERMAT_THRESHOLD
#define SQR_MERSENNE_FFT_THRESHOLD
#define SQR_MERSENNE_DC_THRESHOLD
#define MUL_MERSENNE_DC_THRESHOLD
#define MUL_MERSENNE_FFT_THRESHOLD
#define MUL_FFT_MODF_THRESHOLD
#define MUL_MERSENNE_FERMAT_THRESHOLD
void lmmp_mul_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
mp_limb_t lmmp_shr1add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1
定义 shr.c:53
void lmmp_mul_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_sqr_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
#define lmmp_inc(p)
加1宏(预期无进位)
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_mul_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_sqr_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
void lmmp_sqr_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
#define lmmp_dec_1(p, dec)
减指定值宏(预期无借位)
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
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
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
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 b0
static void mrs_mul_bnp1_(mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n, mp_ptr tp)
mod B^n+1 基例乘法 [rp,n+1] = [ap,n+1]*[bp,n+1] mod B^n+1(规范形 [0,B^n])
static mp_limb_t mrs_neg_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
取负 [dst,n] = B^n - [numa,n],返回进位(= [numa,n] != 0)
static void mrs_norm_zero_(mp_ptr p, mp_size_t n)
零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示)
static void mrs_sqr_bnp1_(mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_ptr tp)
mod B^n+1 基例平方 [rp,n+1] = [ap,n+1]^2 mod B^n+1(规范形 [0,B^n])
static void mrs_mul_core_(mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn, mp_ptr tp)
分治梅森乘法核心(半归一化内部约定:零类 = B^n-1)
#define b1
#define xp
static void mrs_sqr_core_(mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_ptr tp)
分治梅森平方核心(半归一化内部约定:零类 = B^n-1)
static int mrs_fermat_usable_(mp_size_t n)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define a0
#define a1
#define sp1
#define am1
#define ap1
#define bp1
#define bm1
#define numb
#define tp
#define n
#define ALLOC_TYPE(n, type)