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

浏览该文件的源代码.

宏定义

#define getbit(p, bi)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static mp_bitcnt_t count_bits (mp_srcptr p, mp_size_t n)
static mp_limb_t getbits (const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
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_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en, mp_srcptr restrict mp, mp_size_t n)
void lmmp_powmod_odd_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en, mp_srcptr restrict mp, mp_size_t n)
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_limb_t lmmp_redc_ (mp_ptr restrict dst, mp_srcptr restrict tp, mp_srcptr restrict ninv, mp_srcptr restrict mp, mp_size_t n)

宏定义说明

◆ getbit

#define getbit ( p,
bi )
值:
((p[(bi - 1) / LIMB_BITS] >> (bi - 1) % LIMB_BITS) & 1)
#define LIMB_BITS
定义 lmmp.h:102

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.c 第 33 行定义.

函数说明

◆ count_bits()

mp_bitcnt_t count_bits ( mp_srcptr p,
mp_size_t n )
inlinestatic

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

54 {
55 return (n - 1) * LIMB_BITS + lmmp_limb_bits_(p[n - 1]);
56}
#define lmmp_limb_bits_
#define n

引用了 count_bits(), LIMB_BITS, lmmp_limb_bits_ , 以及 n.

函数调用图:

◆ getbits()

mp_limb_t getbits ( const mp_limb_t * p,
mp_bitcnt_t bi,
mp_bitcnt_t nbits )
inlinestatic

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

35 {
36 mp_bitcnt_t nbits_in_r;
37 mp_limb_t r;
38 mp_size_t i;
39
40 if (bi <= nbits) {
41 return p[0] & (((mp_limb_t)1 << bi) - 1);
42 } else {
43 bi -= nbits; /* bit index of low bit to extract */
44 i = bi / LIMB_BITS; /* word index of low bit to extract */
45 bi %= LIMB_BITS; /* bit index in low word */
46 r = p[i] >> bi; /* extract (low) bits */
47 nbits_in_r = LIMB_BITS - bi; /* number of bits now in r */
48 if (nbits_in_r < nbits) /* did we get enough bits? */
49 r += p[i + 1] << nbits_in_r; /* prepend bits from higher word */
50 return r & (((mp_limb_t)1 << nbits) - 1);
51 }
52}
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92

引用了 getbits() , 以及 LIMB_BITS.

函数调用图:

◆ 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 lmmp_zero(dst, n)
定义 lmmp.h:476
#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
#define lmmp_inc(p)
加1宏(预期无进位)
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_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
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 REDC_BASECASE_THRESHOLD
fft_gr_cache mcache
mp_size_t n
fft_mullo_cache ncache
mp_srcptr m
mp_limb_t ninv2
mp_size_t msz
mp_limb_t ninv1
mp_ptr mscratch
#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_powmod_()

void lmmp_powmod_ ( mp_ptr restrict dst,
mp_srcptr restrict bp,
mp_srcptr restrict ep,
mp_size_t en,
mp_srcptr restrict mp,
mp_size_t n )

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

363 {
364 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL && mp != NULL);
365 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
366 lmmp_param_assert(n > 0 && mp[n - 1] > 0);
367
368 if (mp[0] % 2 == 1) {
369 lmmp_powmod_odd_(dst, bp, ep, en, mp, n);
370 return;
371 }
372
373 /* b = 0:正指数幂为 0;e = 1:契约 [bp,n] < [mp,n],拷贝即已取模 */
374 if (lmmp_zero_q_(bp, n)) {
375 lmmp_zero(dst, n);
376 return;
377 }
378 if (en == 1 && ep[0] == 1) {
379 lmmp_copy(dst, bp, n);
380 return;
381 }
382
383 /* 2-adic 赋值 k = v2(m):z 个低零 limb,ctz 为首个非零 limb 的消零数
384 (该 limb 为奇时 ctz == 0,k 恰为 limb 对齐值,无需掩码) */
385 mp_size_t z = 0;
386 while (mp[z] == 0) z++;
387 mp_bitcnt_t ctz = lmmp_tailing_zeros_(mp[z]);
388 mp_size_t nb2 = z + (ctz != 0); /* 2^k 部分的 limb 数 = ceil(k/64) */
389 mp_bitcnt_t k = (mp_bitcnt_t)z * LIMB_BITS + ctz;
390 mp_size_t nodd = n - z;
391
392 /* 偶底数短路:v2(b)*e >= k 时 b^e mod 2^k == 0,跳过整个 powlo 梯子 */
393 int r2_zero = 0;
394 if ((bp[0] & 1) == 0) {
395 mp_size_t zb = 0;
396 while (bp[zb] == 0) zb++; /* b != 0 已在上方保证 */
397 u128 v2b = (u128)(zb * LIMB_BITS + lmmp_tailing_zeros_(bp[zb]));
398 r2_zero = en > 1 || v2b * ep[0] >= (u128)k;
399 }
400
401 /* 纯 2 幂(m == 2^k ⟺ nodd==1 且首个非零 limb 消零后恰为 1):r 即
402 powlo 低 k 位,掩码 + 高位补零即成,全程无临时分配 */
403 if (nodd == 1 && (ctz != 0 ? mp[z] >> ctz == 1 : mp[z] == 1)) {
404 if (r2_zero) {
405 lmmp_zero(dst, n);
406 } else {
407 lmmp_powlo_(dst, bp, nb2, ep, en);
408 if (ctz != 0)
409 dst[nb2 - 1] &= ((mp_limb_t)1 << ctz) - 1;
410 lmmp_zero(dst + nb2, n - nb2);
411 }
412 return;
413 }
414
415 TEMP_DECL;
416
417 /*
418 [modd | sbn ] m_odd 移位缓冲(ctz==0 时免配,直接用 mp+z 视图;
419 移位归一化只缩短 nodd,不影响后续段的偏移)
420 [wrk | wn ] 归约底数 bmod → 2^k 部结果 r2 接力(powmod_odd_
421 返回后 bmod 已死)→ 合成积前段(mul 时 r2 已死)
422 [inv | nb2 ] 模逆 → 合成积后段接力(mullo 之后已死;因合成积
423 经 wrk 跨写本段,inv 不加 restrict)
424 [t | nb2 ] 截断乘输出(mullo 写、mul 读,与 inv/r2 并发,独占)
425 合成积落在 [wrk, wn+nb2)(跨 wrk+inv 两段,mul 时均已死),且
426 wn + nb2 >= nodd + nb2 恰好容纳
427 */
428 mp_size_t sbn = ctz != 0 ? nodd : 0;
429 mp_size_t wn = LMMP_MAX(nodd, nb2);
430 mp_ptr restrict wrkbase = TALLOC_TYPE(sbn + wn + 2 * nb2, mp_limb_t);
431 mp_srcptr modd;
432 if (ctz != 0) {
433 lmmp_shr_(wrkbase, mp + z, nodd, (mp_size_t)ctz);
434 nodd -= wrkbase[nodd - 1] == 0;
435 modd = wrkbase;
436 } else {
437 modd = mp + z;
438 }
439 mp_ptr restrict wrk = wrkbase + sbn;
440 mp_ptr inv = wrk + wn;
441 mp_ptr restrict t = inv + nb2;
442
443 /* 奇部 r1 = b^e mod m_odd 直接写入 dst 低 nodd limb(此后作为 r1 载体
444 直至最终加法,省一块 nodd 缓冲与一次拷贝);底数归约借用 wrk 段 */
445 lmmp_div_(NULL, wrk, bp, n, modd, nodd);
446 lmmp_powmod_odd_(dst, wrk, ep, en, modd, nodd);
447
448 /* 2 部 r2 = b^e mod B^nb2(复用已死的归约底数段) */
449 if (r2_zero)
450 lmmp_zero(wrk, nb2);
451 else
452 lmmp_powlo_(wrk, bp, nb2, ep, en);
453
454 /* t = (r2 - r1) * m_odd^(-1) mod B^nb2,再截到 k 位 */
455 lmmp_binvert_(inv, modd, LMMP_MIN(nodd, nb2), nb2);
456
457 mp_size_t mn = LMMP_MIN(nb2, nodd);
458 mp_limb_t bo = lmmp_sub_n_(wrk, wrk, dst, mn); /* r1 载于 dst */
459 if (mn < nb2)
460 (void)lmmp_sub_1_(wrk + mn, wrk + mn, nb2 - mn, bo); /* 借位在 B^nb2 窗内传播 */
461
462 lmmp_mullo_(t, inv, wrk, nb2);
463 if (ctz != 0)
464 t[nb2 - 1] &= ((mp_limb_t)1 << ctz) - 1;
465
466 /* r = r1 + m_odd * t < m:积写入 [wrk, wn+nb2)(wrk/inv 段此刻均死),
467 积 < m < B^n(nodd+nb2 <= n+1 时顶 limb 必为 0),dst 高位补零后
468 整体相加,进位必为 0。lmmp_mul_ 大操作数在前 */
469 if (nb2 > nodd)
470 lmmp_mul_(wrk, t, nb2, modd, nodd);
471 else
472 lmmp_mul_(wrk, modd, nodd, t, nb2);
473 lmmp_zero(dst + nodd, n - nodd);
474 (void)lmmp_add_n_(dst, dst, wrk, n);
475 TEMP_FREE;
476}
#define k
#define lmmp_tailing_zeros_
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
#define LMMP_MAX(h, i)
返回两个数中的较大值
定义 lmmp.h:454
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define lmmp_param_assert(x)
定义 lmmp.h:509
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
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]
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_mullo_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^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 t
void lmmp_powlo_(mp_ptr dst, mp_srcptr bp, mp_size_t n, mp_srcptr ep, mp_size_t en)
计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
void lmmp_powmod_odd_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n)
计算奇模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)

引用了 k, LIMB_BITS, lmmp_add_n_(), lmmp_binvert_(), lmmp_copy, lmmp_div_(), LMMP_MAX, LMMP_MIN, lmmp_mul_(), lmmp_mullo_(), lmmp_param_assert, lmmp_powlo_(), lmmp_powmod_(), lmmp_powmod_odd_(), lmmp_shr_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_tailing_zeros_, lmmp_zero, lmmp_zero_q_(), n, restrict, t, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ lmmp_powmod_odd_()

void lmmp_powmod_odd_ ( mp_ptr restrict dst,
mp_srcptr restrict bp,
mp_srcptr restrict ep,
mp_size_t en,
mp_srcptr restrict mp,
mp_size_t n )

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

277 {
278 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL && mp != NULL);
279 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
280 lmmp_param_assert(n > 0 && mp[n - 1] > 0);
281 lmmp_param_assert(mp[0] % 2 == 1);
282
283 /* 1/2 limb 特化:标量 Montgomery 梯子,免去通用路径的全部缓冲区与预处理 */
284 if (n == 1) {
285 lmmp_powmod_1_(dst, bp, ep, en, mp[0]);
286 return;
287 }
288 if (n == 2 && mp[1] != 0) {
289 lmmp_powmod_2_(dst, bp, ep, en, mp);
290 return;
291 }
292
293 if (lmmp_zero_q_(bp, n)) {
294 lmmp_zero(dst, n);
295 return;
296 }
297
298 mp_bitcnt_t ebi = count_bits(ep, en);
299
300 /* 指数为 1:契约 [bp,n] < [mp,n],直接拷贝即已取模,免去全部蒙域预处理 */
301 if (ebi == 1) {
302 lmmp_copy(dst, bp, n);
303 return;
304 }
305
306 TEMP_DECL;
307 lmmp_mont_t mc;
308
309 /*
310 单块工作区分段(蒙域段在前,梯子段续后,段布局见 impl/powmod.h):
311 [蒙域段] basecase 0 | 中层 6n | 折叠 6n+msz(lmmp_mont_need_)
312 [u(n)] 梯子累加器
313 [b2(n)] 表生成暂存
314 [prod(2n)] 全积兼 redcify 工作区
315 [pp(ppn)] 奇次幂表,ppn = n << (win-1)
316 */
317 unsigned win = lmmp_powmod_win_size_(ebi);
318 mp_size_t mn = lmmp_mont_need_(n, 0);
319 mp_ptr restrict arena = TALLOC_TYPE(mn + 4 * n + ((mp_size_t)n << (win - 1)), mp_limb_t);
320 mp_ptr restrict u = arena + mn;
321 mp_ptr restrict b2 = u + n;
322 mp_ptr restrict prod = b2 + n;
323 mp_ptr restrict pp = prod + 2 * n;
324
325 lmmp_mont_init_(&mc, mp, n, arena, 0, prod);
326 lmmp_powmod_odd_mont_(u, bp, ep, en, &mc, b2, prod, pp);
327
328 /* 离开 Montgomery 域:r = REDC(u * 1) = u*B^(-n) mod m < m */
329 lmmp_copy(prod, u, n);
330 lmmp_zero(prod + n, n);
331 lmmp_mont_redc_(u, prod, &mc);
332 lmmp_copy(dst, u, n);
333
334 lmmp_mont_free_(&mc);
335 TEMP_FREE;
336}
#define prod
#define b2
void lmmp_powmod_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_limb_t mod)
计算奇模数模幂 [dst,1] = [bp,1]^[ep,en] % mod
void lmmp_powmod_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mod)
计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2]
static mp_bitcnt_t count_bits(mp_srcptr p, mp_size_t n)
定义 powlo.c:86
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)
奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 b2, count_bits(), lmmp_copy, lmmp_mont_redc_(), lmmp_param_assert, lmmp_powmod_1_(), lmmp_powmod_2_(), lmmp_powmod_odd_(), lmmp_powmod_odd_mont_(), lmmp_zero, lmmp_zero_q_(), n, prod, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ 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_
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define getbit(p, bi)
定义 powlo.c:65
static mp_limb_t getbits(const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
定义 powlo.c:67

引用了 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_redc_()

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

123 {
124 lmmp_param_assert(dst != NULL && tp != NULL);
125 lmmp_param_assert(ninv != NULL && mp != NULL);
126 lmmp_param_assert(n > 0 && mp[n - 1] > 0);
127 lmmp_param_assert(mp[0] % 2 == 1);
128 TEMP_DECL;
129
130 /* basecase 层:链式归约 clobber 工作区,先复制以维持 tp 只读契约 */
133 lmmp_copy(up, tp, 2 * n);
134 mp_limb_t cy = lmmp_mont_redc_bc_(dst, up, mp, n, ninv[0], n > 1 ? ninv[1] : 0);
135 TEMP_FREE;
136 return cy;
137 }
138
141 mp_ptr restrict hi;
142 /* t_lo != 0 时低半 t_lo + L == B^n 恰产生 1 进位;t_lo == 0 时 L == 0 */
143 mp_limb_t carry = !lmmp_zero_q_(tp, n);
144
145 if (n < MULLO_DC_THRESHOLD) {
146 lmmp_mullo_dc_(q, tp, ninv, tpw, n);
147 } else {
148 lmmp_mullo_fft_(q, tp, ninv, n, tpw);
149 }
150
153 lmmp_mul_n_(prod, q, mp, n);
154 hi = prod + n;
155 } else {
156 mp_size_t msz = lmmp_mersenne_next_size_((2 * n + 1) >> 1);
157 lmmp_debug_assert(2 * n > msz && msz >= n);
160 hi = TALLOC_TYPE(n, mp_limb_t);
161 lmmp_mul_mersenne_(V, msz, q, n, mp, n);
162 if (carry) {
163 lmmp_not_(L, tp, n);
164 lmmp_inc(L); /* t_lo != 0,取反加一不会越界 */
165 } else {
166 lmmp_zero(L, n);
167 }
168 lmmp_mont_fold_hi_(hi, V, L, n, msz);
169 }
170
171 mp_limb_t cy = lmmp_add_nc_(dst, tp + n, hi, n, carry);
172 TEMP_FREE;
173 return cy;
174}
void lmmp_mullo_fft_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
定义 mullo.c:68
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
#define REDC_MERSENNE_THRESHOLD

引用了 lmmp_add_nc_(), lmmp_copy, lmmp_debug_assert, lmmp_inc, lmmp_mersenne_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_n_, lmmp_mullo_dc_(), lmmp_mullo_fft_(), lmmp_not_(), lmmp_param_assert, lmmp_redc_(), lmmp_zero, lmmp_zero_q_(), MULLO_DC_THRESHOLD, n, prod, REDC_BASECASE_THRESHOLD, REDC_MERSENNE_THRESHOLD, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.

函数调用图: