69 n = (((
n - 1) >>
k) + 1) <<
k;
76 for (
mp_size_t i = 0; i < K; ++i) pfca[i] = (
mp_ptr)(pfca + K) + i * nlen;
77 pfcb += (nlen + 1) <<
k;
78 for (
mp_size_t i = 0; i < K; ++i) pfcb[i] = (
mp_ptr)(pfcb + K) + i * nlen;
122 n = (((
n - 1) >>
k) + 1) <<
k;
138 pfca[i] = (
mp_ptr)(pfca + K) + i * nlen;
140 coeflen = M + (i == K - 1);
141 coeflen =
LMMP_MIN(narest, coeflen);
152 pfcb += (nlen + 1) <<
k;
155 pfcb[i] = (
mp_ptr)(pfcb + K) + i * nlen;
157 coeflen = M + (i == K - 1);
158 coeflen =
LMMP_MIN(nbrest, coeflen);
196 n = (((
n - 1) >> (
k - 1)) + 1) << (
k - 1);
212 pfca[i] = (
mp_ptr)(pfca + K) + i * nlen;
223 pfcb += (nlen + 1) <<
k;
226 pfcb[i] = (
mp_ptr)(pfcb + K) + i * nlen;
246 if (nums[nlen - 1]) {
263 }
else if (roffset + nlen <= rn) {
264 lmmp_add_(dst + roffset, nums, nlen, dst + roffset, rhead - roffset);
265 rhead = roffset + nlen;
267 maxc +=
lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
268 maxc +=
lmmp_add_(dst, dst, rn, nums + rn - roffset, nlen + roffset - rn);
297 ctx->
M = ctx->
N >> ctx->
k;
298 ctx->
n = 2 * ctx->
M + ctx->
k + 2;
300 ctx->
n = (((ctx->
n - 1) >> ctx->
k) + 1) << ctx->
k;
326 coeflen = ctx->
M + (i == ctx->
K - 1);
327 coeflen =
LMMP_MIN(narest, coeflen);
342 coeflen = ctx->
M + (i == ctx->
K - 1);
343 coeflen =
LMMP_MIN(nbrest, coeflen);
387 coeflen = ctx->
M + (i == ctx->
K - 1);
388 coeflen =
LMMP_MIN(narest, coeflen);
430 ctx->
M = ctx->
N >> ctx->
k;
431 ctx->
n = 2 * ctx->
M + ctx->
k;
433 ctx->
n = (((ctx->
n - 1) >> (ctx->
k - 1)) + 1) << (ctx->
k - 1);
459 coeflen = ctx->
M + (i == ctx->
K - 1);
491 if (nums[ctx->
nlen - 1]) {
494 nums[ctx->
nlen - 1] = 0;
507 }
else if (roffset + ctx->
nlen <= rn) {
508 lmmp_add_(dst + roffset, nums, ctx->
nlen, dst + roffset, rhead - roffset);
509 rhead = roffset + ctx->
nlen;
511 maxc +=
lmmp_add_(dst + roffset, nums, rn - roffset, dst + roffset, rhead - roffset);
512 maxc +=
lmmp_add_(dst, dst, rn, nums + rn - roffset, ctx->
nlen + roffset - rn);
544 coeflen = ctx->
M + (i == ctx->
K - 1);
563 if (nums[ctx->
nlen - 1]) {
566 nums[ctx->
nlen - 1] = 0;
579 }
else if (roffset + ctx->
nlen <= ctx->
rn) {
580 lmmp_add_(dst + roffset, nums, ctx->
nlen, dst + roffset, rhead - roffset);
581 rhead = roffset + ctx->
nlen;
583 maxc +=
lmmp_add_(dst + roffset, nums, ctx->
rn - roffset, dst + roffset, rhead - roffset);
584 maxc +=
lmmp_add_(dst, dst, ctx->
rn, nums + ctx->
rn - roffset, ctx->
nlen + roffset - ctx->
rn);
626 if (
lmmp_add_(dst, numa, hn, numa + hn, na - hn))
663 if (dst[hn - 1] < cy)
674 cy =
tp[hn] +
lmmp_sub_nc_(
tp + nab - hn, dst + nab - hn,
tp + nab - hn, 2 * hn - nab, cy);
715 if (
lmmp_add_(dst, numa, hn, numa + hn, na - hn))
726 if (
lmmp_sub_(ctx->
tp, numa, hn, numa + hn, na - hn))
740 if (ctx->
na > ctx->
hn) {
748 if (ctx->
na > ctx->
hn) {
749 ctx->
tp[ctx->
hn] = 0;
770 sna = (hn << 1) - 1 - nb;
mp_size_t lmmp_fft_best_k_(mp_size_t n)
查找对于 m>=n 的模 B^m+1 FFT运算的最优k值
void lmmp_fft_shr_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shr)
对模 2^n+1 的系数执行右移操作 右移shr位 = 左移(2n - shr)位(mod 2^n+1的循环特性)
void lmmp_fft_shl_coef_(fft_memstack *ms, mp_ptr *coef, mp_size_t shl)
对模 2^n+1 的系数执行左移操作
void lmmp_mul_fermat_recombine_(fft_memstack *ms, mp_ptr dst, mp_ptr *pfca, mp_size_t K, mp_size_t k, mp_size_t n, mp_size_t M, mp_size_t rn)
费马变换 模 B^n+1 乘法的结果合并
void * lmmp_fft_memstack_(fft_memstack *ms, mp_size_t size)
FFT内存栈的分配/释放接口
void lmmp_ifft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
void lmmp_fft_extract_coef_(mp_ptr dst, mp_srcptr numa, mp_size_t bitoffset, mp_size_t bits, mp_size_t lenw)
[dst,lenw+1] = [(bit*)numa+bitoffset, bits]
void lmmp_fft_(fft_memstack *ms, mp_ptr *coef, mp_size_t k, mp_size_t w)
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
#define lmmp_debug_assert(x)
const mp_limb_t * mp_srcptr
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define LMMP_VECT_CONSERVATIVE
#define LMMP_MIN(l, o)
返回两个数中的较小值
#define lmmp_param_assert(x)
#define MUL_FFT_MODF_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
#define lmmp_dec(p)
减1宏(预期无借位)
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
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 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
void lmmp_mul_fft_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
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
void lmmp_mul_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
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]
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
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
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]
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
static void lmmp_fft_cache_free_(fft_cache *ctx)
释放FFT模乘法缓存上下文
void lmmp_mul_fft_cache_init_(mp_ptr dst, mp_size_t hn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_cache *ctx)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] 第二个操作数将被缓存
void lmmp_mul_fft_cache_(mp_ptr dst, mp_srcptr numa, fft_cache *ctx)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_fermat_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_mul_fermat_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+1]=[numa,na]*[numb,nb] mod B^rn+1 第二个操作数将被缓存
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 第二个操作数将被缓存
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void lmmp_mul_fermat_recurse_(fft_memstack *ms, mp_ptr *pc1, mp_ptr *pc2, mp_size_t K0)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void lmmp_mul_fft_mods_(mp_ptr dst, mp_ptr tp, mp_size_t hn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 双域模乘计算:分别求梅森域与费马域残差(lmmp_mul_fft_crt_ 的前半)
static void lmmp_mul_fft_crt_(mp_ptr dst, mp_ptr tp, mp_size_t hn, mp_size_t nab)
FFT 双域 CRT 重构尾部(lmmp_mul_fft_mods_ 的后半):两域残差 → 精确积
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ALLOC_TYPE(n, type)