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

浏览该文件的源代码.

宏定义

#define a0   ap
#define a0   ap
#define a1   (ap + n)
#define a1   (ap + n)
#define b0   bp
#define b1   (bp + n)
#define sp1   (tp + 2 * n + 2)
#define sp1   (tp + 2 * n + 2)
#define xp   tp
#define xp   tp

函数

mp_size_t lmmp_mersenne_next_size_ (mp_size_t n)
 计算满足 >=n 的最小分治梅森乘法可行尺寸
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
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_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
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 int mrs_fermat_usable_ (mp_size_t n)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
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 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)
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_sqr_core_ (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_ptr tp)
 分治梅森平方核心(半归一化内部约定:零类 = B^n-1)

宏定义说明

◆ a0 [1/2]

#define a0   ap

◆ a0 [2/2]

◆ a1 [1/2]

#define a1   (ap + n)

◆ a1 [2/2]

◆ b0

◆ b1

◆ sp1 [1/2]

#define sp1   (tp + 2 * n + 2)

◆ sp1 [2/2]

#define sp1   (tp + 2 * n + 2)

被这些函数引用 mrs_mul_core_() , 以及 mrs_sqr_core_().

◆ xp [1/2]

#define xp   tp

◆ xp [2/2]

函数说明

◆ lmmp_mersenne_next_size_()

mp_size_t lmmp_mersenne_next_size_ ( mp_size_t n)

计算满足 >=n 的最小分治梅森乘法可行尺寸

参数
n输入的目标尺寸
返回
满足条件的分治梅森乘法最小尺寸
注解
梅森缓存和fft算法应该改用 lmmp_fft_next_size_

在文件 mul_mersenne.c 第 408 行定义.

408 {
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}
uint64_t mp_size_t
定义 lmmp.h:93
#define MUL_MERSENNE_DC_THRESHOLD
#define MUL_FFT_MODF_THRESHOLD
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
#define n

引用了 lmmp_fft_next_size_(), lmmp_mersenne_next_size_(), MUL_FFT_MODF_THRESHOLD, MUL_MERSENNE_DC_THRESHOLD , 以及 n.

被这些函数引用 bench_mul_mersenne_dc(), binvert_mulhi_(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mersenne_next_size_(), lmmp_mont_init_(), lmmp_mont_need_(), lmmp_mul_toom62_unbalance_(), lmmp_redc_() , 以及 TEST_CASE().

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

◆ lmmp_mul_mersenne_()

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

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为进入 fft 档的推荐最小值
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
sep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, dst!=NULL, numa!=NULL, numb!=NULL
注解
na/nb 大小序不限(内部按交换律规范化为 nb<=na);rn 对齐粒度不限 (未达 fft 可行尺寸时即使超过阈值也回落 dc); 如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_函数;
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 417 行定义.

417 {
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}
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define MUL_MERSENNE_FFT_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_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
#define numb
#define tp

引用了 lmmp_fft_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_mersenne_fft_(), MUL_MERSENNE_FFT_THRESHOLD, numb , 以及 tp.

被这些函数引用 binvert_mulhi_(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mont_redc_(), lmmp_mul_mersenne_(), lmmp_mul_toom62_unbalance_(), lmmp_redc_() , 以及 TEST_CASE().

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

◆ lmmp_mul_mersenne_dc_()

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

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数
numa第一个输入操作数,长度为 na
na第一个操作数的 limb 长度
numb第二个输入操作数,长度为 nb
nb第二个操作数的 limb 长度
警告
sep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, na+nb>rn/2, dst!=NULL, numa!=NULL, numb!=NULL
注解
如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_dc_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_dc_函数
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 385 行定义.

385 {
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}
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_debug_assert(x)
定义 lmmp.h:498
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
static void mrs_norm_zero_(mp_ptr p, mp_size_t n)
零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示)
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 ALLOC_TYPE(n, type)

引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_free(), lmmp_mul_mersenne_dc_(), lmmp_param_assert, mrs_mul_core_(), mrs_norm_zero_(), numb , 以及 tp.

被这些函数引用 bench_mul_mersenne_dc(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_toom62_unbalance_() , 以及 TEST_CASE().

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

◆ lmmp_sqr_mersenne_()

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

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc); rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为进入 fft 档的推荐最小值
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
sep(dst,numa), 0<=[numa,na]<B^rn, dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 434 行定义.

434 {
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 SQR_MERSENNE_FFT_THRESHOLD
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_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

引用了 lmmp_fft_next_size_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_(), lmmp_sqr_mersenne_fft_() , 以及 SQR_MERSENNE_FFT_THRESHOLD.

被这些函数引用 lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_toom62_unbalance_(), lmmp_sqr_mersenne_() , 以及 TEST_CASE().

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

◆ lmmp_sqr_mersenne_dc_()

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

参数
dst输出结果缓冲区,长度至少为 rn
rn模运算的阶数参数
numa输入操作数,长度为 na
na输入操作数的 limb 长度
警告
sep(dst,numa), 0<=[numa,na]<B^rn, 4*na>rn, dst!=NULL, numa!=NULL
返回
无返回值,结果存储在dst中

在文件 mul_mersenne.c 第 397 行定义.

397 {
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}
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)

引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_free(), lmmp_param_assert, lmmp_sqr_mersenne_dc_(), mrs_norm_zero_(), mrs_sqr_core_() , 以及 tp.

被这些函数引用 lmmp_mul_toom62_unbalance_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_() , 以及 TEST_CASE().

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

◆ mrs_fermat_usable_()

int mrs_fermat_usable_ ( mp_size_t n)
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

判断 n 是否为费马变换可行尺寸(64n 能被 2^best_k 整除)

参数
n输入的 limb 长度
返回
1 可行 / 0 不可行

在文件 mul_mersenne.c 第 35 行定义.

35 {
37 return (n & (((mp_size_t)1 << k) - 1)) == 0;
38}
#define k
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
#define LOG2_LIMB_BITS
定义 lmmp.h:104

引用了 k, lmmp_fft_best_k_(), LOG2_LIMB_BITS, mrs_fermat_usable_() , 以及 n.

被这些函数引用 mrs_fermat_usable_(), mrs_mul_core_() , 以及 mrs_sqr_core_().

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

◆ mrs_mul_bnp1_()

void mrs_mul_bnp1_ ( mp_ptr rp,
mp_srcptr ap,
mp_srcptr bp,
mp_size_t n,
mp_ptr tp )
static

mod B^n+1 基例乘法 [rp,n+1] = [ap,n+1]*[bp,n+1] mod B^n+1(规范形 [0,B^n])

参数
rp输出缓冲区,长度至少为 n+1
ap第一个操作数(高半域形,值 < B^n+1),长度为 n+1
bp第二个操作数,长度为 n+1
n模运算的阶数
tp工作区,长度至少为 2n(允许 tp==rp)
警告
n>0, sep(tp,[ap|bp]) 或 tp==rp
注解
顶位特例:ap/bp 顶 limb 为 1(值 = B^n ≡ -1)时以取反代乘

在文件 mul_mersenne.c 第 68 行定义.

68 {
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}
#define rp
#define lmmp_mul_n_
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)
加指定值宏(预期无进位)
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)

引用了 lmmp_inc_1, lmmp_mul_n_, lmmp_sub_n_(), mrs_mul_bnp1_(), mrs_neg_(), n, rp , 以及 tp.

被这些函数引用 mrs_mul_bnp1_() , 以及 mrs_mul_core_().

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

◆ mrs_mul_core_()

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

分治梅森乘法核心(半归一化内部约定:零类 = B^n-1)

参数
rp输出 [rp,rn] = [ap,an]*[bp,bn] mod B^rn-1(半归一化,写入完整 rn limb)
rn模运算的阶数
ap第一个操作数
an第一个操作数的 limb 长度
bp第二个操作数
bn第二个操作数的 limb 长度
tp工作区,长度至少为 2rn+4
警告
0<bn<=an<=rn, an+bn>rn/2, sep(rp,[ap|bp]), sep(tp,[rp|ap|bp])

在文件 mul_mersenne.c 第 117 行定义.

117 {
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}
#define an
#define bn
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define LIMB_BITS
定义 lmmp.h:102
#define MUL_MERSENNE_FERMAT_THRESHOLD
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
#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_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
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
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_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])
#define b1
#define xp
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

引用了 a0, a1, am1, an, ap1, b0, b1, bm1, bn, bp1, LIMB_BITS, lmmp_add_(), lmmp_add_n_(), lmmp_debug_assert, lmmp_dec_1, lmmp_inc, lmmp_inc_1, lmmp_mul_(), lmmp_mul_fermat_(), lmmp_mul_n_, lmmp_shr1add_nc_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_(), lmmp_zero, mrs_fermat_usable_(), mrs_mul_bnp1_(), mrs_mul_core_(), MUL_MERSENNE_DC_THRESHOLD, MUL_MERSENNE_FERMAT_THRESHOLD, n, rp, sp1, tp , 以及 xp.

被这些函数引用 lmmp_mul_mersenne_dc_() , 以及 mrs_mul_core_().

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

◆ mrs_neg_()

mp_limb_t mrs_neg_ ( mp_ptr dst,
mp_srcptr numa,
mp_size_t n )
static

取负 [dst,n] = B^n - [numa,n],返回进位(= [numa,n] != 0)

参数
dst输出缓冲区,长度至少为 n
numa输入操作数,长度为 n
n操作数的 limb 长度
警告
n>0, sep/eqsep(dst,numa)

在文件 mul_mersenne.c 第 47 行定义.

47 {
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}
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26

引用了 lmmp_inc, lmmp_not_(), lmmp_zero, lmmp_zero_q_(), mrs_neg_() , 以及 n.

被这些函数引用 mrs_mul_bnp1_() , 以及 mrs_neg_().

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

◆ mrs_norm_zero_()

void mrs_norm_zero_ ( mp_ptr p,
mp_size_t n )
static

零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示)

参数
p输入输出缓冲区,长度为 n
nlimb 长度

在文件 mul_mersenne.c 第 379 行定义.

379 {
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}

引用了 lmmp_zero, mrs_norm_zero_() , 以及 n.

被这些函数引用 lmmp_mul_mersenne_dc_(), lmmp_sqr_mersenne_dc_() , 以及 mrs_norm_zero_().

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

◆ mrs_sqr_bnp1_()

void mrs_sqr_bnp1_ ( mp_ptr rp,
mp_srcptr ap,
mp_size_t n,
mp_ptr tp )
static

mod B^n+1 基例平方 [rp,n+1] = [ap,n+1]^2 mod B^n+1(规范形 [0,B^n])

参数
rp输出缓冲区,长度至少为 n+1
ap操作数(高半域形,值 < B^n+1),长度为 n+1
n模运算的阶数
tp工作区,长度至少为 2n(允许 tp==rp)
警告
n>0, sep(tp,ap) 或 tp==rp
注解
顶位特例:ap 顶 limb 为 1(值 ≡ -1)时结果为 1

在文件 mul_mersenne.c 第 93 行定义.

93 {
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}
#define lmmp_sqr_

引用了 lmmp_inc_1, lmmp_sqr_, lmmp_sub_n_(), lmmp_zero, mrs_sqr_bnp1_(), n, rp , 以及 tp.

被这些函数引用 mrs_sqr_bnp1_() , 以及 mrs_sqr_core_().

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

◆ mrs_sqr_core_()

void mrs_sqr_core_ ( mp_ptr rp,
mp_size_t rn,
mp_srcptr ap,
mp_size_t an,
mp_ptr tp )
static

分治梅森平方核心(半归一化内部约定:零类 = B^n-1)

参数
rp输出 [rp,rn] = [ap,an]^2 mod B^rn-1(半归一化,写入完整 rn limb)
rn模运算的阶数
ap操作数
an操作数的 limb 长度
tp工作区,长度至少为 2rn+4
警告
0<an<=rn, 4*an>rn, sep(rp,ap), sep(tp,[rp|ap])

在文件 mul_mersenne.c 第 268 行定义.

268 {
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}
#define SQR_MERSENNE_FERMAT_THRESHOLD
#define SQR_MERSENNE_DC_THRESHOLD
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
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])

引用了 a0, a1, am1, an, ap1, LIMB_BITS, lmmp_add_(), lmmp_add_n_(), lmmp_debug_assert, lmmp_dec_1, lmmp_inc, lmmp_inc_1, lmmp_shr1add_nc_(), lmmp_sqr_, lmmp_sqr_fermat_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_(), lmmp_zero, mrs_fermat_usable_(), mrs_sqr_bnp1_(), mrs_sqr_core_(), n, rp, sp1, SQR_MERSENNE_DC_THRESHOLD, SQR_MERSENNE_FERMAT_THRESHOLD, tp , 以及 xp.

被这些函数引用 lmmp_sqr_mersenne_dc_() , 以及 mrs_sqr_core_().

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