LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powmod.h
浏览该文件的文档.
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#ifndef __LMMP_POWMOD_H__
24#define __LMMP_POWMOD_H__
25
26#include "lmmp/lmmpn.h"
27#include "lmmp/numth.h"
28#include "impl/longlong.h"
29#include "mparam.h"
30#include "impl/mul_cache.h"
31
32/*
33 记 R = B^n,m 为奇模数(n limb),ninv = -m^(-1) mod B^n。
34 单步 REDC:给定 t = a*b < m*B^n([tp,2n]),令
35
36 q = t_lo * ninv mod B^n (q*m ≡ -t_lo (mod B^n))
37
38 则 (t + q*m)/B^n ≡ t*R^(-1) (mod m) 且 < 2m。低半部分 t_lo + (q*m)_lo
39 恰为 B^n*[t_lo!=0],无需逐 limb 相加,故
40
41 u = t_hi + mulhi(q, m) + [t_lo!=0]
42
43 高半积 mulhi(q,m) 的三种来源(按规模分层):
44 1. basecase(n < REDC_BASECASE_THRESHOLD):链式 Hensel 归约消零,
45 成本约一次 basecase 乘法(其 clobber 输入的特性见各调用点)。
46 addmul_2 双 limb 步进。
47 2. 全积取高半:lmmp_mul_n_ 后读高 n limb(中尺寸段);
48 3. 梅森折叠(n >= REDC_MERSENNE_CACHE_THRESHOLD):由于 (q*m) mod B^n
49 = -t_lo mod B^n 是已知量 L,与 binvert_mulhi_ 同构——先算 V = q*m
50 mod (B^msz-1)(msz 为 admissible 尺寸,模数 m 一侧的变换全程缓存
51 复用),从 V 中减去 L 后旋转载出高半。两操作数均 < B^n 保证
52 hi <= B^n-2,拼接表示不会落在 B^msz-1 的二义点上;而 L==0 强制
53 q==0、积为零,也不与零类的非规范表示冲突。
54
55 蒙域值 x̃ = x*R mod m;进蒙域(redcify)用一次 (x*B^n) mod m 除法(低位
56 补 n 零 limb 实现 <<B^n),比 RR=B^2n mod m 加乘加归约的旧路径省约两个
57 M(n) 的预处理;basecase 层连全长 binvert 也一并省去(仅需低 limb 逆元)。
58
59 映射 x -> x*R mod m 为 Z/m 上的环同构(m 奇故 gcd(R,m)=1):乘法(REDC)
60 与加减法均保持,且 1 与 -1 的蒙域剩余为 one = B^n mod m 与 m1 = m - one
61 (anchors 档预计算)。素性检验的 ±1 探测因此可全程留在蒙域进行,
62 免去出蒙域归约。
63*/
64
65/* REDC 梯子上下文:模数一侧的全部预计算(ninv/one/m1/折叠分派)与工作区。
66 arena 分段布局(lmmp_mont_need_,随规模与 anchors 裁剪):
67 anchors:one(n) | m1(n) —— 蒙域 ±1 探测基准(is_prime_n 用)
68 basecase(n < REDC_BASECASE_THRESHOLD):无 core 段
69 中层:ninv(n) | q(n) | mscratch(2n) | mulhi(2n) == 6n
70 折叠层(n >= REDC_MERSENNE_THRESHOLD):mulhi(2n) 换
71 Lbuf(n) | hi(n) | V(msz) == 6n + msz
72 one/m1 之后的段与调用者的梯子段续接(单块打包) */
73typedef struct {
75 mp_srcptr m; /* 模数 */
76 mp_ptr ninv; /* -m^(-1) mod B^n(basecase 层不使用,为 NULL) */
77 mp_limb_t ninv1; /* -m^(-1) mod B(basecase 层专用) */
78 mp_limb_t ninv2; /* -m^(-1) mod B^2 的高 limb(basecase 层专用) */
79 int fold; /* 折叠模式:2=梅森缓存(fft),1=梅森分发(不缓存),0=朴素全积 */
80
81 mp_size_t msz; /* 折叠尺寸(fold 时有效) */
82 mp_ptr one; /* [n] B^n mod m(蒙域 1,无 anchors 档为 NULL) */
83 mp_ptr m1; /* [n] m - one(蒙域 -1,无 anchors 档为 NULL) */
84 mp_ptr q; /* [n] q = t_lo * ninv mod B^n */
85 mp_ptr Lbuf; /* [n] -t_lo mod B^n */
86 mp_ptr hi; /* [n] q*m 的高 n limb(折叠路径输出) */
87 mp_ptr mulhi; /* [2n] 全积路径的 q*m(非折叠路径) */
88 mp_ptr V; /* [msz] 折叠积 q*m mod B^msz-1 */
89 mp_ptr mscratch; /* [2n] mullo scratch */
95
96/**
97 * @brief 蒙域上下文的分段工作区长度
98 * @param n 模数 limb 长度
99 * @param anchors 1 = 含 one/m1 探测基准段,0 = 仅 REDC 工作段
100 * @return 蒙域段所需的 limb 数
101 */
102static inline mp_size_t lmmp_mont_need_(mp_size_t n, int anchors) {
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}
112
113/**
114 * @brief 从梅森折叠积中提取高半积(低位已知变体的 mulhi)
115 * @param hi 结果指针(n 个limb),接收 [q,n]*[mp,n] div B^n
116 * @param V 输入兼工作区(msz 个limb),入口为 q*m mod B^msz-1,出口被破坏
117 * @param L 已知低位(n 个limb),满足 q*m ≡ L (mod B^n),此处 L = -t_lo mod B^n
118 * @param n 操作数长度
119 * @param msz 折叠尺寸,admissible 且 n <= msz < 2n
120 * @warning sep(hi,V), V 的 msz-n 个高位 limb 亦会被读写
121 * @note 设 P = q*m = hi*B^n + L,则 W = (V-L) mod B^msz-1 = hi*B^n mod B^msz-1,
122 * 即 hi 的第 j limb 恰位于 W[(j+n) mod msz],旋转载出即得
123 */
124static inline void lmmp_mont_fold_hi_(
125 mp_ptr restrict hi,
128 mp_size_t n,
129 mp_size_t msz
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}
148
149/**
150 * @brief basecase REDC:链式 Hensel 归约,addmul_2 双 limb 步进消零
151 * @param dst 结果指针(n 个limb),接收 ([up,2n] + q*m)/B^n 的低 n limb
152 * @param up 输入兼工作区(2n 个limb,出口被破坏)
153 * @param m 模数(n 个limb)
154 * @param n 操作数长度
155 * @param ninv1 -m^(-1) mod B(单 limb)
156 * @param ninv2 -m^(-1) mod B^2 的高 limb(n == 1 时不会读到)
157 * @warning sep(dst,up), n < REDC_BASECASE_THRESHOLD 时才是优选路径
158 * @return 进位([0|1]),返回值:[dst,n] 即 REDC 结果 < 2m(t < B^n*m 时)
159 */
161 mp_ptr restrict dst,
162 mp_ptr restrict up,
164 mp_size_t n,
165 mp_limb_t ninv1,
166 mp_limb_t ninv2
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}
185
186/**
187 * @brief REDC 单步并规范化:[dst,n] = (t + q*m)/B^n mod m,结果 < m
188 * @param dst 结果指针(n 个limb)
189 * @param tp 被归约数兼工作区(2n 个limb,t < B^n*[m,n],出口被破坏)
190 * @param mc 蒙域上下文(须已完成 lmmp_mont_init_)
191 * @warning sep(dst,tp), dst 与 mc 内各缓冲区均分离
192 */
194
195/**
196 * @brief 进蒙域:[dst,n] = [xp,n]*B^n mod [mp,n]
197 * @param dst 结果指针(n 个limb)
198 * @param xp 普通域输入(n 个limb,eqsep(dst,xp))
199 * @param n 操作数长度
200 * @param prod 工作区(2n 个limb,出口被破坏,sep(dst,xp,mp))
201 * @param mp 模数(n 个limb)
202 * @warning n>0, mp[0]%2==1, mp[n-1]>0, sep([prod|dst],mp)
203 */
204static inline void lmmp_mont_redcify_(
205 mp_ptr dst,
207 mp_size_t n,
210) {
211 lmmp_zero(prod, n);
212 lmmp_copy(prod + n, xp, n);
213 lmmp_div_(NULL, dst, prod, 2 * n, mp, n);
214}
215
216/**
217 * @brief 蒙域上下文初始化:切分 REDC 工作段并预计算 ninv 与探测基准
218 * @param mc 上下文(出口就绪)
219 * @param mp 模数(n 个limb,奇,mc->m 引用之,生命周期须覆盖上下文全程)
220 * @param n 模数 limb 长度
221 * @param arena 工作区分段头(lmmp_mont_need_(n,anchors) 个limb)
222 * @param anchors 1 = 预计算 one/m1(蒙域 ±1 探测基准),0 = 免配
223 * @param prod [2n] redcify 工作区(与 arena 分段分离,出口被破坏)
224 * @warning n>0, mp[0]%2==1, mp[n-1]>0, sep([arena|prod],mp)
225 * @note 分段布局见 lmmp_mont_t 注释;TEMP 工作区由调用者 TEMP_FREE 统一
226 * 回收,FFT 变换缓存另经 lmmp_mont_free_ 释放
227 */
228static inline void lmmp_mont_init_(
229 lmmp_mont_t* mc,
230 mp_srcptr mp,
231 mp_size_t n,
232 mp_ptr arena,
233 int anchors,
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}
300
301/* 释放蒙域上下文的 FFT 变换缓存(TEMP 工作区由调用者 TEMP_FREE 统一回收) */
302static inline void lmmp_mont_free_(lmmp_mont_t* mc) {
303 if (mc->mcache_on)
305 if (mc->ncache_on)
307}
308
309/*
310 形状 m = ε + Kv·B^p(ε ∈ {+1,−1},Kv ≤ 2 limb,p ≥ 1,n ≥ 2):
311 +1 形(Proth):limb0 = 1、limb 1..p−1 全零、顶部 ≤2 limb 簇 = Kv;
312 −1 形(Mersenne/Riesel):limb 0..p−1 全 B−1、顶部簇读值 Kv−1
313 (m = Kv·B^p − 1,簇全 B−1 已被探测排除,Kv 无越顶)。
314
315 单步 REDC 与 lmmp_mont_redc_bc_ 同为链式 Hensel 逐 limb 消零,但每轮
316 addmul_1 经伸缩恒等式坍缩为 O(1):
317
318 q·m·B^64j = q·Kv·B^(64(j+p)) + ε·q·B^64j
319
320 乘子由 m ≡ ε (mod B) 免费给出(ε=+1 ⟹ m^(-1)=1 ⟹ q = B − up[j],本位
321 u0+q = B 恰清零、进位 1 入 j+1;ε=−1 ⟹ q = up[j],本位 u0−q 恰清零无
322 借位),中间 limb 零贡献,唯一的实做是 j+p 处 q·Kv 的 ≤3 limb 乘加与
323 有界进位游程(add_1 遇非 B−1 即停,游程被后续 O(1) 次写入重建,充电
324 论证总游程 O(n))。p ≥ 1 保证各操作只触 ≥ j+1 位,低 j limb 恒零,
325 n 轮后高 n limb 即结果。整步 O(n),全尺寸优于 bc/中层/折叠三层
326 (后三者 ≈ 一次 M(n))——本旁路因此独立于 lmmp_mont_t 的尺寸分派,
327 形状命中即用,上下文无任何工作段与缓存(init 免配、无 free)。
328
329 值域核算:表示值 = 数组 + top·B^2n ≡ t + (Σq_j B^j)m < 2m·B^n ≤ 2B^2n,
330 数组非负 ⟹ top ∈ {0,1}(越顶进位逐次捕获累加);结果 = 高半 + top·B^n
331 ∈ [0,2m),规范化至多减 m 一次。
332*/
333typedef struct {
334 mp_size_t n; /* 模数 limb 长度 */
335 mp_srcptr m; /* 模数(引用调用者内存,生命周期须覆盖上下文全程) */
336 int form; /* 形状:+1 / −1(0 = 非稀疏,上下文未装配) */
337 mp_size_t p; /* 簇偏移(1 <= p <= n-1) */
338 mp_limb_t kv0; /* Kv 低 limb */
339 mp_limb_t kv1; /* Kv 高 limb(1 limb 簇时为 0;−1 形为簇读值+1 的产物) */
341
342/**
343 * @brief 稀疏形状探测与上下文装配(O(n) 扫描,免分配)
344 * @param mc 上下文(出口:形状命中时就绪,否则 form=0 其余字段为 0)
345 * @param mp 模数(n 个limb,奇,顶 limb 非零)
346 * @param n 模数 limb 长度
347 * @warning n >= 2
348 * @return 形状(+1/−1),非稀疏返回 0
349 */
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}
378
379/**
380 * @brief 稀疏模数 REDC 单步并规范化:[dst,n] = t*B^(-n) mod m,结果 < m
381 * @param dst 结果指针(n 个limb)
382 * @param tp 被归约数兼工作区(2n 个limb,t < m*B^n,出口被破坏)
383 * @param mc 稀疏蒙域上下文(须已完成 lmmp_mont_sp_init_ 且 form != 0)
384 * @warning sep(dst,tp),dst 与 mc->m 分离
385 */
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}
435
436/**
437 * @brief 模幂滑动窗口尺寸(按指数位长分档)
438 * @param eb 指数位长(>0)
439 * @return 窗口宽 k ∈ [1,10],奇次幂表长 2^(k-1)
440 */
441static inline unsigned lmmp_powmod_win_size_(mp_bitcnt_t eb) {
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}
447
448/**
449 * @brief 蒙域梯子(lmmp_powmod_odd_mont_)的调用者工作区长度
450 * @param n 模数 limb 长度
451 * @param eb 指数位长(>0)
452 * @return 所需 limb 数:b2(n) + prod(2n) + 奇次幂表(n << (win-1))
453 */
455 return 3 * n + (n << (lmmp_powmod_win_size_(eb) - 1));
456}
457
458/**
459 * @brief 奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
460 * @param u 出口(n 个limb)= b^e·R mod m < m,亦为梯子累加器
461 * @param bp 普通域基底(n 个limb,0 < [bp,n] < [mc->m,n])
462 * @param ep 指数(en 个limb,顶 limb 非零)
463 * @param en 指数 limb 长度
464 * @param mc 蒙域上下文(须已完成 lmmp_mont_init_)
465 * @param b2 表生成暂存(n 个limb,b²R mod m,出口死)
466 * @param prod 工作区(2n 个limb,平方/乘法全积兼 redcify,出口被破坏)
467 * @param pp 奇次幂表(n << (lmmp_powmod_win_size_(eb)-1) 个limb,出口死)
468 * @warning n>2 建议走 1/2 limb 特化(见 lmmp_powmod_odd_),sep 各段与 mc
469 * @note 大尺寸比二进制梯子省约 30% 乘法;e=1 时即 redcify。同一 mc 跨多次
470 * 调用可复用 ninv 与 FFT 变换缓存(同模数批量模幂/素性检验轮)
471 */
476 mp_size_t en,
481);
482
483#endif /* __LMMP_POWMOD_H__ */
#define k
#define prod
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_dec(p)
减1宏(预期无借位)
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
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 lmmp_inc(p)
加1宏(预期无进位)
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
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
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_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
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
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
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
static void lmmp_mullo_cache_free_(fft_mullo_cache *ctx)
释放 mullo 缓存上下文
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define xp
#define b2
#define t
#define tp
#define s
#define n
#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 下的逆元
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)
奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
static void lmmp_mont_free_(lmmp_mont_t *mc)
fft_gr_cache mcache
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
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 int lmmp_mont_sp_init_(lmmp_mont_sp_t *mc, mp_srcptr mp, mp_size_t n)
稀疏形状探测与上下文装配(O(n) 扫描,免分配)
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)
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]
fft_mullo_cache ncache
mp_srcptr m
mp_limb_t ninv2
mp_size_t msz
static unsigned lmmp_powmod_win_size_(mp_bitcnt_t eb)
模幂滑动窗口尺寸(按指数位长分档)
mp_limb_t ninv1
static mp_size_t lmmp_mont_need_(mp_size_t n, int anchors)
蒙域上下文的分段工作区长度
mp_ptr mscratch
static mp_size_t lmmp_powmod_odd_mont_need_(mp_size_t n, mp_bitcnt_t eb)
蒙域梯子(lmmp_powmod_odd_mont_)的调用者工作区长度
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 步进消零
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)