LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powmod.h 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "impl/longlong.h"
#include "mparam.h"
#include "impl/mul_cache.h"
powmod.h 的引用(Include)关系图:
此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

结构体

struct  lmmp_mont_sp_t
struct  lmmp_mont_t
 Copyright (C) 2026 HJimmyK (Jericho Knox) 更多...

函数

static void lmmp_mont_fold_hi_ (mp_ptr restrict hi, mp_ptr restrict V, mp_srcptr restrict L, mp_size_t n, mp_size_t msz)
 从梅森折叠积中提取高半积(低位已知变体的 mulhi)
static void lmmp_mont_free_ (lmmp_mont_t *mc)
static void lmmp_mont_init_ (lmmp_mont_t *mc, mp_srcptr mp, mp_size_t n, mp_ptr arena, int anchors, mp_ptr restrict prod)
 蒙域上下文初始化:切分 REDC 工作段并预计算 ninv 与探测基准
static mp_size_t lmmp_mont_need_ (mp_size_t n, int anchors)
 蒙域上下文的分段工作区长度
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
static mp_limb_t lmmp_mont_redc_bc_ (mp_ptr restrict dst, mp_ptr restrict up, mp_srcptr restrict m, mp_size_t n, mp_limb_t ninv1, mp_limb_t ninv2)
 basecase REDC:链式 Hensel 归约,addmul_2 双 limb 步进消零
static void lmmp_mont_redcify_ (mp_ptr dst, mp_srcptr xp, mp_size_t n, mp_ptr restrict prod, mp_srcptr restrict mp)
 进蒙域:[dst,n] = [xp,n]*B^n mod [mp,n]
static int lmmp_mont_sp_init_ (lmmp_mont_sp_t *mc, mp_srcptr mp, mp_size_t n)
 稀疏形状探测与上下文装配(O(n) 扫描,免分配)
static void lmmp_mont_sp_redc_ (mp_ptr restrict dst, mp_ptr restrict tp, const lmmp_mont_sp_t *restrict mc)
 稀疏模数 REDC 单步并规范化:[dst,n] = t*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)
 奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
static mp_size_t lmmp_powmod_odd_mont_need_ (mp_size_t n, mp_bitcnt_t eb)
 蒙域梯子(lmmp_powmod_odd_mont_)的调用者工作区长度
static unsigned lmmp_powmod_win_size_ (mp_bitcnt_t eb)
 模幂滑动窗口尺寸(按指数位长分档)

结构体说明

◆ lmmp_mont_sp_t

struct lmmp_mont_sp_t

在文件 powmod.h 第 333 行定义.

lmmp_mont_sp_t 的协作图:
成员变量
int form
mp_limb_t kv0
mp_limb_t kv1
mp_srcptr m
mp_size_t n
mp_size_t p

◆ lmmp_mont_t

struct lmmp_mont_t

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

在文件 powmod.h 第 73 行定义.

lmmp_mont_t 的协作图:
成员变量
int fold
mp_ptr hi
mp_ptr Lbuf
mp_srcptr m
mp_ptr m1
fft_gr_cache mcache
int mcache_on
mp_ptr mscratch
mp_size_t msz
mp_ptr mulhi
mp_size_t n
fft_mullo_cache ncache
int ncache_on
mp_ptr ninv
mp_limb_t ninv1
mp_limb_t ninv2
mp_ptr one
mp_ptr q
mp_ptr V

函数说明

◆ lmmp_mont_fold_hi_()

void lmmp_mont_fold_hi_ ( mp_ptr restrict hi,
mp_ptr restrict V,
mp_srcptr restrict L,
mp_size_t n,
mp_size_t msz )
inlinestatic

从梅森折叠积中提取高半积(低位已知变体的 mulhi)

参数
hi结果指针(n 个limb),接收 [q,n]*[mp,n] div B^n
V输入兼工作区(msz 个limb),入口为 q*m mod B^msz-1,出口被破坏
L已知低位(n 个limb),满足 q*m ≡ L (mod B^n),此处 L = -t_lo mod B^n
n操作数长度
msz折叠尺寸,admissible 且 n <= msz < 2n
警告
sep(hi,V), V 的 msz-n 个高位 limb 亦会被读写
注解
设 P = q*m = hi*B^n + L,则 W = (V-L) mod B^msz-1 = hi*B^n mod B^msz-1, 即 hi 的第 j limb 恰位于 W[(j+n) mod msz],旋转载出即得

在文件 powmod.h 第 124 行定义.

130 {
131 mp_size_t fn = msz - n; /* hi 中线性对位部分长度(取自 V+n) */
132 mp_size_t sn = n - fn; /* hi 中环绕部分长度(取自 V 头部) */
133 lmmp_debug_assert(msz >= n && 2 * n > msz);
134
135 mp_limb_t bor = lmmp_sub_n_(V, V, L, n);
136 if (bor) {
137 /* 数组当前值 = V - L + B^n(借位等价于吸收在第 n 个 limb 上) */
138 if (msz > n)
139 bor = lmmp_sub_1_(V + n, V + n, msz - n, 1);
140 /* 若高位段借位(此时 V < L,高位段必为全零,减 1 后变全 1),
141 或 msz==n(借位即 V<L),整体再减 1 补回 B^msz-1 */
142 if (msz == n || bor)
143 lmmp_dec(V);
144 }
145 lmmp_copy(hi, V + n, fn);
146 lmmp_copy(hi + fn, V, sn);
147}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_dec(p)
减1宏(预期无借位)
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_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 n

引用了 lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_sub_1_(), lmmp_sub_n_(), n , 以及 restrict.

函数调用图:

◆ lmmp_mont_free_()

void lmmp_mont_free_ ( lmmp_mont_t * mc)
inlinestatic

在文件 powmod.h 第 302 行定义.

302 {
303 if (mc->mcache_on)
305 if (mc->ncache_on)
307}
static void lmmp_mullo_cache_free_(fft_mullo_cache *ctx)
释放 mullo 缓存上下文
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
fft_gr_cache mcache
fft_mullo_cache ncache

引用了 lmmp_fft_gr_cache_free_(), lmmp_mullo_cache_free_(), lmmp_mont_t::mcache, lmmp_mont_t::mcache_on, lmmp_mont_t::ncache , 以及 lmmp_mont_t::ncache_on.

函数调用图:

◆ lmmp_mont_init_()

void lmmp_mont_init_ ( lmmp_mont_t * mc,
mp_srcptr mp,
mp_size_t n,
mp_ptr arena,
int anchors,
mp_ptr restrict prod )
inlinestatic

蒙域上下文初始化:切分 REDC 工作段并预计算 ninv 与探测基准

参数
mc上下文(出口就绪)
mp模数(n 个limb,奇,mc->m 引用之,生命周期须覆盖上下文全程)
n模数 limb 长度
arena工作区分段头(lmmp_mont_need_(n,anchors) 个limb)
anchors1 = 预计算 one/m1(蒙域 ±1 探测基准),0 = 免配
prod[2n] redcify 工作区(与 arena 分段分离,出口被破坏)
警告
n>0, mp[0]%2==1, mp[n-1]>0, sep([arena|prod],mp)
注解
分段布局见 lmmp_mont_t 注释;TEMP 工作区由调用者 TEMP_FREE 统一 回收,FFT 变换缓存另经 lmmp_mont_free_ 释放

在文件 powmod.h 第 228 行定义.

235 {
236 mc->n = n;
237 mc->m = mp;
238 /* basecase 档不进折叠路径,fold 置 0:避免 REDC_MERSENNE_THRESHOLD <
239 REDC_BASECASE_THRESHOLD 时(当前默认 40 < 41)basecase 分支残留
240 未配套的 fold=1 死状态;mont_redc_ 与此处的档位判定保持同一谓词 */
241 mc->fold = n < REDC_BASECASE_THRESHOLD ? 0
243 : (n >= REDC_MERSENNE_THRESHOLD ? 1 : 0);
244 mc->msz = mc->fold == 2 ? lmmp_fft_next_size_((2 * n + 1) >> 1)
245 : mc->fold == 1 ? lmmp_mersenne_next_size_((2 * n + 1) >> 1) : 0;
246 mc->mcache_on = 0;
247 mc->ncache_on = 0;
248 if (mc->fold)
249 lmmp_debug_assert(2 * n > mc->msz && mc->msz >= n);
250
251 if (anchors) {
252 mc->one = arena;
253 mc->m1 = arena + n;
254 } else {
255 mc->one = mc->m1 = NULL;
256 }
258 mc->ninv = NULL;
259 mc->ninv1 = 0 - lmmp_binvert_ulong_(mp[0]);
260 if (n > 1) {
261 /* ninv2 = -m^(-1) mod B^2 的高 limb:由 m*ninv1 ≡ -1 mod B 展开
262 (e = hi(mp[0]*ninv1)+1),n == 1 时 stride-2 用不到,不读 m[1] */
263 mp_limb_t e = _umul64to64hi_(mp[0], mc->ninv1) + 1;
264 mc->ninv2 = mc->ninv1 * e + mp[1] * mc->ninv1 * mc->ninv1;
265 } else {
266 mc->ninv2 = 0;
267 }
268 mc->q = mc->Lbuf = mc->hi = mc->mscratch = mc->mulhi = mc->V = NULL;
269 } else {
270 mp_size_t core = anchors ? 2 * n : 0;
271 mc->ninv1 = mc->ninv2 = 0;
272 mc->ninv = arena + core;
273 mc->q = arena + core + n;
274 mc->mscratch = arena + core + 2 * n;
275 if (mc->fold) {
276 mc->Lbuf = arena + core + 4 * n;
277 mc->hi = arena + core + 5 * n;
278 mc->V = arena + core + 6 * n;
279 mc->mulhi = NULL;
280 } else {
281 mc->mulhi = arena + core + 4 * n;
282 mc->Lbuf = mc->hi = mc->V = NULL;
283 }
284 /* ninv = -m^(-1) mod B^n:m 奇故其逆亦奇,取反加一不会越顶 */
285 lmmp_binvert_(mc->ninv, mp, n, n);
286 lmmp_not_(mc->ninv, mc->ninv, n);
287 lmmp_inc(mc->ninv);
288 }
289
290 if (anchors) {
291 /* one = B^n mod m:低位补 n 零 limb 实现 <<B^n,除法取余(m1 段先
292 兼作被除数的高半载体) */
293 lmmp_zero(mc->m1, n);
294 mc->m1[0] = 1;
295 lmmp_mont_redcify_(mc->one, mc->m1, n, prod, mp);
296 /* m1 = m - one(one != 0 恒成立,无借位) */
297 (void)lmmp_sub_n_(mc->m1, mp, mc->one, n);
298 }
299}
#define prod
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define lmmp_inc(p)
加1宏(预期无进位)
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
#define REDC_MERSENNE_THRESHOLD
#define REDC_BASECASE_THRESHOLD
#define REDC_MERSENNE_CACHE_THRESHOLD
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
mp_size_t n
static void lmmp_mont_redcify_(mp_ptr dst, mp_srcptr xp, mp_size_t n, mp_ptr restrict prod, mp_srcptr restrict mp)
进蒙域:[dst,n] = [xp,n]*B^n mod [mp,n]
mp_srcptr m
mp_limb_t ninv2
mp_size_t msz
mp_limb_t ninv1
mp_ptr mscratch

引用了 _umul64to64hi_(), lmmp_mont_t::fold, lmmp_mont_t::hi, lmmp_mont_t::Lbuf, lmmp_binvert_(), lmmp_binvert_ulong_(), lmmp_debug_assert, lmmp_fft_next_size_(), lmmp_inc, lmmp_mersenne_next_size_(), lmmp_mont_redcify_(), lmmp_not_(), lmmp_sub_n_(), lmmp_zero, lmmp_mont_t::m, lmmp_mont_t::m1, lmmp_mont_t::mcache_on, lmmp_mont_t::mscratch, lmmp_mont_t::msz, lmmp_mont_t::mulhi, lmmp_mont_t::n, n, lmmp_mont_t::ncache_on, lmmp_mont_t::ninv, lmmp_mont_t::ninv1, lmmp_mont_t::ninv2, lmmp_mont_t::one, prod, lmmp_mont_t::q, REDC_BASECASE_THRESHOLD, REDC_MERSENNE_CACHE_THRESHOLD, REDC_MERSENNE_THRESHOLD, restrict , 以及 lmmp_mont_t::V.

函数调用图:

◆ lmmp_mont_need_()

mp_size_t lmmp_mont_need_ ( mp_size_t n,
int anchors )
inlinestatic

蒙域上下文的分段工作区长度

参数
n模数 limb 长度
anchors1 = 含 one/m1 探测基准段,0 = 仅 REDC 工作段
返回
蒙域段所需的 limb 数

在文件 powmod.h 第 102 行定义.

102 {
103 if (n < REDC_BASECASE_THRESHOLD) return anchors ? 2 * n : 0;
104 if (n >= REDC_MERSENNE_THRESHOLD) {
106 ? lmmp_fft_next_size_((2 * n + 1) >> 1) /* 缓存档:仅 fft 尺寸可用 */
107 : lmmp_mersenne_next_size_((2 * n + 1) >> 1); /* 分发档:细粒度低 padding */
108 return 6 * n + msz + (anchors ? 2 * n : 0);
109 }
110 return 6 * n + (anchors ? 2 * n : 0);
111}

引用了 lmmp_fft_next_size_(), lmmp_mersenne_next_size_(), n, REDC_BASECASE_THRESHOLD, REDC_MERSENNE_CACHE_THRESHOLD , 以及 REDC_MERSENNE_THRESHOLD.

函数调用图:

◆ lmmp_mont_redc_()

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

参数
dst结果指针(n 个limb)
tp被归约数兼工作区(2n 个limb,t < B^n*[m,n],出口被破坏)
mc蒙域上下文(须已完成 lmmp_mont_init_)
警告
sep(dst,tp), dst 与 mc 内各缓冲区均分离

在文件 powmod.c 第 58 行定义.

58 {
59 mp_size_t n = mc->n;
61
63 mp_limb_t cy = lmmp_mont_redc_bc_(dst, tp, mc->m, n, mc->ninv1, mc->ninv2);
64 if (cy) {
65 /* 值 >= B^n > m,减 m 必然可行;借位恰好抵消进位 limb */
66 (void)lmmp_sub_n_(dst, dst, mc->m, n);
67 } else if (lmmp_cmp_(dst, mc->m, n) >= 0) {
68 lmmp_sub_n_(dst, dst, mc->m, n);
69 }
70 return;
71 }
72
73 mp_limb_t carry = !lmmp_zero_q_(tp, n);
74
75 if (n < MULLO_DC_THRESHOLD) {
76 lmmp_mullo_dc_(mc->q, tp, mc->ninv, mc->mscratch, n);
77 } else if (mc->ncache_on == 0) {
78 lmmp_mullo_fft_cache_init_(mc->q, tp, mc->ninv, n, mc->mscratch, &mc->ncache);
79 mc->ncache_on = 1;
80 } else {
81 lmmp_mullo_fft_cache_(mc->q, tp, mc->mscratch, &mc->ncache);
82 }
83
84 if (mc->fold == 0) {
85 lmmp_mul_n_(mc->mulhi, mc->q, mc->m, n);
86 hi = mc->mulhi + n;
87 } else {
88 if (mc->fold == 1) {
89 /* 中档:分发入口不缓存(小尺寸 dc 主导) */
90 lmmp_mul_mersenne_(mc->V, mc->msz, mc->q, n, mc->m, n);
91 } else if (mc->mcache_on == 0) {
92 lmmp_mul_mersenne_cache_init_(mc->V, mc->msz, mc->q, n, mc->m, n, &mc->mcache);
93 mc->mcache_on = 1;
94 } else {
95 lmmp_mul_mersenne_cache_(mc->V, mc->q, &mc->mcache);
96 }
97 if (carry) {
98 lmmp_not_(mc->Lbuf, tp, n);
99 lmmp_inc(mc->Lbuf);
100 } else {
101 lmmp_zero(mc->Lbuf, n);
102 }
103 lmmp_mont_fold_hi_(mc->hi, mc->V, mc->Lbuf, n, mc->msz);
104 hi = mc->hi;
105 }
106
107 /* u = t_hi + hi + carry,结果 carry_out:[dst,n] < 2m */
108 mp_limb_t cy = lmmp_add_nc_(dst, tp + n, hi, n, carry);
109 if (cy) {
110 /* 值 >= B^n > m,减 m 必然可行;n limb 减法的借位恰好抵消进位 limb */
111 (void)lmmp_sub_n_(dst, dst, mc->m, n);
112 } else if (lmmp_cmp_(dst, mc->m, n) >= 0) {
113 lmmp_sub_n_(dst, dst, mc->m, n);
114 }
115}
#define lmmp_mul_n_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define MULLO_DC_THRESHOLD
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_mullo_dc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
mp_limb_t lmmp_add_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
定义 add_n.c:58
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
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mullo_fft_cache_(mp_ptr dst, mp_srcptr numa, mp_ptr scratch, fft_mullo_cache *ctx)
低位乘法(缓存版) [dst,n] = [numa,n] * 缓存numb mod B^n
void lmmp_mullo_fft_cache_init_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch, fft_mullo_cache *ctx)
低位乘法(缓存版) [dst,n] = [numa,n] * [numb,n] mod B^n 第二个操作数将被缓存
定义 mullo.c:86
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存
#define tp
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 lmmp_add_nc_(), lmmp_cmp_(), lmmp_inc, lmmp_mont_redc_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_n_, lmmp_mullo_dc_(), lmmp_mullo_fft_cache_(), lmmp_mullo_fft_cache_init_(), lmmp_not_(), lmmp_sub_n_(), lmmp_zero, lmmp_zero_q_(), MULLO_DC_THRESHOLD, n, REDC_BASECASE_THRESHOLD, restrict , 以及 tp.

被这些函数引用 ipn_lucas_i_(), ipn_notrial_i_(), ipn_sprp_1_(), ipn_sprp_base2_(), lmmp_mont_redc_(), lmmp_powmod_odd_() , 以及 lmmp_powmod_odd_mont_().

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

◆ lmmp_mont_redc_bc_()

mp_limb_t lmmp_mont_redc_bc_ ( mp_ptr restrict dst,
mp_ptr restrict up,
mp_srcptr restrict m,
mp_size_t n,
mp_limb_t ninv1,
mp_limb_t ninv2 )
inlinestatic

basecase REDC:链式 Hensel 归约,addmul_2 双 limb 步进消零

参数
dst结果指针(n 个limb),接收 ([up,2n] + q*m)/B^n 的低 n limb
up输入兼工作区(2n 个limb,出口被破坏)
m模数(n 个limb)
n操作数长度
ninv1-m^(-1) mod B(单 limb)
ninv2-m^(-1) mod B^2 的高 limb(n == 1 时不会读到)
警告
sep(dst,up), n < REDC_BASECASE_THRESHOLD 时才是优选路径
返回
进位([0|1]),返回值:[dst,n] 即 REDC 结果 < 2m(t < B^n*m 时)

在文件 powmod.h 第 160 行定义.

167 {
168 mp_ptr restrict up0 = up;
169 if (n & 1) {
170 up[0] = lmmp_addmul_1_(up, m, n, up[0] * ninv1);
171 up++;
172 }
173 for (mp_size_t j = n & ~(mp_size_t)1; j >= 2; j -= 2) {
174 mp_limb_t q[2], qh;
175 _umul64to128_(up[0], ninv1, &q[0], &qh);
176 q[1] = qh + up[0] * ninv2 + up[1] * ninv1;
177 mp_limb_t upn = up[n]; /* addmul_2 覆写 up[n],先保存 */
178 up[1] = lmmp_addmul_2_(up, m, n, q);
179 up[0] = up[n]; /* 第 n limb 搬移停入清零槽(折叠消权重差) */
180 up[n] = upn;
181 up += 2;
182 }
183 return lmmp_add_n_(dst, up0 + n, up0, n);
184}
mp_limb_t lmmp_addmul_2_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
定义 mul_1.c:99
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
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
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)

引用了 _umul64to128_(), lmmp_add_n_(), lmmp_addmul_1_(), lmmp_addmul_2_(), n , 以及 restrict.

函数调用图:

◆ lmmp_mont_redcify_()

void lmmp_mont_redcify_ ( mp_ptr dst,
mp_srcptr xp,
mp_size_t n,
mp_ptr restrict prod,
mp_srcptr restrict mp )
inlinestatic

进蒙域:[dst,n] = [xp,n]*B^n mod [mp,n]

参数
dst结果指针(n 个limb)
xp普通域输入(n 个limb,eqsep(dst,xp))
n操作数长度
prod工作区(2n 个limb,出口被破坏,sep(dst,xp,mp))
mp模数(n 个limb)
警告
n>0, mp[0]%2==1, mp[n-1]>0, sep([prod|dst],mp)

在文件 powmod.h 第 204 行定义.

210 {
211 lmmp_zero(prod, n);
212 lmmp_copy(prod + n, xp, n);
213 lmmp_div_(NULL, dst, prod, 2 * n, mp, n);
214}
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
#define xp

引用了 lmmp_copy, lmmp_div_(), lmmp_zero, n, prod, restrict , 以及 xp.

被这些函数引用 lmmp_mont_init_().

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

◆ lmmp_mont_sp_init_()

int lmmp_mont_sp_init_ ( lmmp_mont_sp_t * mc,
mp_srcptr mp,
mp_size_t n )
inlinestatic

稀疏形状探测与上下文装配(O(n) 扫描,免分配)

参数
mc上下文(出口:形状命中时就绪,否则 form=0 其余字段为 0)
mp模数(n 个limb,奇,顶 limb 非零)
n模数 limb 长度
警告
n >= 2
返回
形状(+1/−1),非稀疏返回 0

在文件 powmod.h 第 350 行定义.

350 {
351 lmmp_debug_assert(n >= 2 && mp[0] % 2 == 1 && mp[n - 1] != 0);
352 mc->n = n;
353 mc->m = mp;
354 mc->p = mc->kv0 = mc->kv1 = 0;
355 if (mp[0] == 1) {
356 mp_size_t i = 1;
357 while (i < n && mp[i] == 0) i++;
358 if (n - i < 1 || n - i > 2) return mc->form = 0;
359 mc->form = 1;
360 mc->p = i;
361 mc->kv0 = mp[i];
362 mc->kv1 = (n - i == 2) ? mp[n - 1] : 0;
363 return 1;
364 }
365 if (mp[0] == LIMB_MAX) {
366 mp_size_t i = 1;
367 while (i < n && mp[i] == LIMB_MAX) i++;
368 if (i >= n || n - i > 2) return mc->form = 0;
369 mc->form = -1;
370 mc->p = i;
371 /* Kv = 簇读值 + 1;mp[i] != B-1(探测保证)⟹ kv0 不回绕、无进位 */
372 mc->kv0 = mp[i] + 1;
373 mc->kv1 = (n - i == 2) ? mp[n - 1] : 0;
374 return -1;
375 }
376 return mc->form = 0;
377}
#define LIMB_MAX
定义 lmmp.h:105

引用了 lmmp_mont_sp_t::form, lmmp_mont_sp_t::kv0, lmmp_mont_sp_t::kv1, LIMB_MAX, lmmp_debug_assert, lmmp_mont_sp_t::m, lmmp_mont_sp_t::n, n , 以及 lmmp_mont_sp_t::p.

◆ lmmp_mont_sp_redc_()

void lmmp_mont_sp_redc_ ( mp_ptr restrict dst,
mp_ptr restrict tp,
const lmmp_mont_sp_t *restrict mc )
inlinestatic

稀疏模数 REDC 单步并规范化:[dst,n] = t*B^(-n) mod m,结果 < m

参数
dst结果指针(n 个limb)
tp被归约数兼工作区(2n 个limb,t < m*B^n,出口被破坏)
mc稀疏蒙域上下文(须已完成 lmmp_mont_sp_init_ 且 form != 0)
警告
sep(dst,tp),dst 与 mc->m 分离

在文件 powmod.h 第 386 行定义.

386 {
387 mp_size_t n = mc->n, n2 = 2 * n;
388 mp_size_t p = mc->p;
389 mp_limb_t kv0 = mc->kv0, kv1 = mc->kv1;
390 mp_ptr up = tp;
391 mp_limb_t top = 0;
392
393 for (mp_size_t j = 0; j < n; j++, up++) {
394 mp_limb_t u0 = up[0];
395 if (u0 == 0) continue;
396 mp_limb_t q;
397 if (mc->form > 0) {
398 /* +1 形:q = B − u0,本位清零、进位 1 入 j+1(游程遇非 B−1 即停) */
399 q = LIMB_MAX - u0 + 1;
400 up[0] = 0;
401 top += lmmp_add_1_(up + 1, up + 1, n2 - j - 1, 1);
402 } else {
403 /* −1 形:q = u0,本位恰清零无借位 */
404 q = u0;
405 up[0] = 0;
406 }
407 /* 绝对位 j+p 处 += q·Kv(up 已前移 j,故相对偏移恰为 p;Kv <= 2 limb
408 ⟹ 积 <= 3 limb,绝对位 j+p+1 <= 2n-1 恒在界内) */
409 mp_size_t w = p;
410 u128 t = (u128)q * kv0;
411 u128 s = (u128)up[w] + (mp_limb_t)t;
412 up[w] = (mp_limb_t)s;
413 t = (u128)q * kv1 + (mp_limb_t)(t >> 64);
414 s = (u128)up[w + 1] + (mp_limb_t)t + (mp_limb_t)(s >> 64);
415 up[w + 1] = (mp_limb_t)s;
416 mp_limb_t cy = (mp_limb_t)(t >> 64) + (mp_limb_t)(s >> 64);
417 if (cy) {
418 /* 绝对位 j+p+2 = 2n(1 limb 簇顶格)时进位直达 top */
419 if (j + w + 2 < n2)
420 cy = lmmp_add_1_(up + w + 2, up + w + 2, n2 - j - w - 2, cy);
421 top += cy;
422 }
423 }
424 lmmp_debug_assert(top <= 1);
425
426 /* 低 n limb 恒零;结果 = 高半 + top(虚进位),< 2m,规范化一次 */
427 lmmp_copy(dst, tp + n, n);
428 if (top) {
429 /* 值 >= B^n > m,减 m 必然可行,借位恰好抵消虚进位 */
430 (void)lmmp_sub_n_(dst, dst, mc->m, n);
431 } else if (lmmp_cmp_(dst, mc->m, n) >= 0) {
432 lmmp_sub_n_(dst, dst, mc->m, n);
433 }
434}
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
#define t
#define s

引用了 LIMB_MAX, lmmp_add_1_(), lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_sub_n_(), n, restrict, s, t , 以及 tp.

函数调用图:

◆ lmmp_powmod_odd_mont_()

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 )

奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域

参数
u出口(n 个limb)= b^e·R mod m < m,亦为梯子累加器
bp普通域基底(n 个limb,0 < [bp,n] < [mc->m,n])
ep指数(en 个limb,顶 limb 非零)
en指数 limb 长度
mc蒙域上下文(须已完成 lmmp_mont_init_)
b2表生成暂存(n 个limb,b²R mod m,出口死)
prod工作区(2n 个limb,平方/乘法全积兼 redcify,出口被破坏)
pp奇次幂表(n << (lmmp_powmod_win_size_(eb)-1) 个limb,出口死)
警告
n>2 建议走 1/2 limb 特化(见 lmmp_powmod_odd_),sep 各段与 mc
注解
大尺寸比二进制梯子省约 30% 乘法;e=1 时即 redcify。同一 mc 跨多次 调用可复用 ninv 与 FFT 变换缓存(同模数批量模幂/素性检验轮)

在文件 powmod.c 第 176 行定义.

185 {
186 lmmp_param_assert(u != NULL && bp != NULL && ep != NULL && mc != NULL);
187 lmmp_param_assert(b2 != NULL && prod != NULL && pp != NULL);
188 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
189
190 mp_size_t n = mc->n;
191 mp_bitcnt_t ebi, cnt;
192 unsigned windowsize, this_windowsize;
193 mp_limb_t expbits;
194
195 ebi = count_bits(ep, en);
196
197 /* 进蒙域:pp[0] = b*B^n mod m,一次 2n/n 除法(低位补 n 零 limb 实现
198 <<B^n,比 RR=B^2n mod m 加乘加归约省约两个 M(n)) */
199 lmmp_mont_redcify_(pp, bp, n, prod, mc->m);
200
201 /* 指数为 1:梯子即入蒙域本体 */
202 if (ebi == 1) {
203 lmmp_copy(u, pp, n);
204 return;
205 }
206
207 windowsize = lmmp_powmod_win_size_(ebi);
208
209 if (windowsize > 1) {
210 lmmp_debug_assert(windowsize < ebi);
211
212 /* b2 = b^2*B^n mod m,用于生成奇次幂表 */
213 lmmp_sqr_(prod, pp, n);
214 lmmp_mont_redc_(b2, prod, mc);
215
216 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++) {
217 lmmp_mul_(prod, pp + (i - 1) * n, n, b2, n);
218 lmmp_mont_redc_(pp + i * n, prod, mc);
219 }
220
221 expbits = getbits(ep, ebi, windowsize);
222 ebi -= windowsize;
223
224 ctz_shr_u64(expbits, expbits, cnt);
225 ebi += cnt;
226
227 lmmp_copy(u, pp + n * (expbits >> 1), n);
228 } else {
229 lmmp_copy(u, pp, n);
230 --ebi;
231 }
232
233 while (ebi != 0) {
234 while (getbit(ep, ebi) == 0) {
235 lmmp_sqr_(prod, u, n);
236 lmmp_mont_redc_(u, prod, mc);
237 if (--ebi == 0)
238 return;
239 }
240
241 /* The next bit of the exponent is 1. Now extract the largest block of
242 bits <= windowsize, and such that the least significant bit is 1. */
243
244 expbits = getbits(ep, ebi, windowsize);
245 this_windowsize = LMMP_MIN(windowsize, ebi);
246
247 ctz_shr_u64(expbits, expbits, cnt);
248 this_windowsize -= cnt;
249 ebi -= this_windowsize;
250
251 while (this_windowsize > 1) {
252 lmmp_sqr_(prod, u, n);
253 lmmp_mont_redc_(u, prod, mc);
254 lmmp_sqr_(prod, u, n);
255 lmmp_mont_redc_(u, prod, mc);
256 this_windowsize -= 2;
257 }
258
259 if (this_windowsize != 0) {
260 lmmp_sqr_(prod, u, n);
261 lmmp_mont_redc_(u, prod, mc);
262 }
263 lmmp_mul_(prod, u, n, pp + n * (expbits >> 1), n);
264 lmmp_mont_redc_(u, prod, mc);
265 }
266 /* 不出蒙域:[u,n] = b^e*B^n mod m < m(含规范化),供调用者蒙域内继续
267 运算或 ±1 探测 */
268}
#define lmmp_sqr_
size_t mp_bitcnt_t
定义 lmmp.h:98
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define lmmp_param_assert(x)
定义 lmmp.h:509
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]
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define b2
#define getbit(p, bi)
定义 powlo.c:65
static mp_bitcnt_t count_bits(mp_srcptr p, mp_size_t n)
定义 powlo.c:86
static mp_limb_t getbits(const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
定义 powlo.c:67
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

引用了 b2, count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_copy, lmmp_debug_assert, LMMP_MIN, lmmp_mont_redc_(), lmmp_mul_(), lmmp_param_assert, lmmp_powmod_odd_mont_(), lmmp_sqr_, n, prod , 以及 restrict.

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

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

◆ lmmp_powmod_odd_mont_need_()

mp_size_t lmmp_powmod_odd_mont_need_ ( mp_size_t n,
mp_bitcnt_t eb )
inlinestatic

蒙域梯子(lmmp_powmod_odd_mont_)的调用者工作区长度

参数
n模数 limb 长度
eb指数位长(>0)
返回
所需 limb 数:b2(n) + prod(2n) + 奇次幂表(n << (win-1))

在文件 powmod.h 第 454 行定义.

454 {
455 return 3 * n + (n << (lmmp_powmod_win_size_(eb) - 1));
456}
static unsigned lmmp_powmod_win_size_(mp_bitcnt_t eb)
模幂滑动窗口尺寸(按指数位长分档)

引用了 lmmp_powmod_odd_mont_need_(), lmmp_powmod_win_size_() , 以及 n.

被这些函数引用 lmmp_powmod_odd_mont_need_().

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

◆ lmmp_powmod_win_size_()

unsigned lmmp_powmod_win_size_ ( mp_bitcnt_t eb)
inlinestatic

模幂滑动窗口尺寸(按指数位长分档)

参数
eb指数位长(>0)
返回
窗口宽 k ∈ [1,10],奇次幂表长 2^(k-1)

在文件 powmod.h 第 441 行定义.

441 {
442 unsigned k;
443 static mp_bitcnt_t x[] = {7, 25, 81, 241, 673, 1793, 4609, 11521, 28161, ~(mp_bitcnt_t)0};
444 for (k = 0; eb > x[k++];);
445 return k;
446}
#define k

引用了 k.

被这些函数引用 lmmp_powmod_odd_mont_need_().

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