23#ifndef __LMMP_POWMOD_H__
24#define __LMMP_POWMOD_H__
108 return 6 *
n + msz + (anchors ? 2 *
n : 0);
110 return 6 *
n + (anchors ? 2 *
n : 0);
176 q[1] = qh + up[0] * ninv2 + up[1] * ninv1;
255 mc->
one = mc->
m1 = NULL;
272 mc->
ninv = arena + core;
273 mc->
q = arena + core +
n;
276 mc->
Lbuf = arena + core + 4 *
n;
277 mc->
hi = arena + core + 5 *
n;
278 mc->
V = arena + core + 6 *
n;
281 mc->
mulhi = arena + core + 4 *
n;
282 mc->
Lbuf = mc->
hi = mc->
V = NULL;
357 while (i <
n && mp[i] == 0) i++;
358 if (
n - i < 1 || n - i > 2)
return mc->
form = 0;
362 mc->
kv1 = (
n - i == 2) ? mp[
n - 1] : 0;
368 if (i >=
n ||
n - i > 2)
return mc->
form = 0;
373 mc->
kv1 = (
n - i == 2) ? mp[
n - 1] : 0;
395 if (u0 == 0)
continue;
410 u128
t = (u128)q * kv0;
420 cy =
lmmp_add_1_(up + w + 2, up + w + 2, n2 - j - w - 2, cy);
444 for (
k = 0; eb > x[
k++];);
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
#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]
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)
比较函数
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
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)
除法和取模操作
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
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]
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]
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 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)
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)
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 unsigned lmmp_powmod_win_size_(mp_bitcnt_t eb)
模幂滑动窗口尺寸(按指数位长分档)
static mp_size_t lmmp_mont_need_(mp_size_t n, int anchors)
蒙域上下文的分段工作区长度
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)