|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "impl/inlines.h"#include "mparam.h"#include "impl/tmp_alloc.h"#include "lmmpn/fft_ssa.h"#include "impl/mul_cache.h"#include "lmmp/lmmpn.h"函数 | |
| 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_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 第二个操作数将被缓存 | |
| 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) | |
| 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] | |
| 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_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] 第二个操作数将被缓存 | |
| 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_ 的后半):两域残差 → 精确积 | |
| 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_ 的前半) | |
| void | lmmp_mul_fft_unbalance_ (mp_ptr restrict dst, mp_srcptr restrict numa, mp_size_t na, mp_srcptr restrict numb, mp_size_t nb) |
| 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_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 第二个操作数将被缓存 | |
| 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 | |
| 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
| dst | 输出结果缓冲区,长度至少为 rn+1 |
| rn | 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_zero, lmmp_zero_q_(), fft_memstack::maxdepth, n, numb, fft_memstack::temp_coef , 以及 fft_memstack::tempdepth.
被这些函数引用 lmmp_mul_fermat_(), lmmp_mul_fft_mods_(), lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_() , 以及 mrs_mul_core_().
| 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
| dst | 输出结果缓冲区,长度为 lmmp_mul_fermat_cache_init_()函数中输入参数的 rn+1 |
| numa | 第一个输入操作数,长度为 lmmp_mul_fermat_cache_init_()函数中输入参数的 na |
| ctx | 费马数模乘法缓存上下文 |
引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::k, fft_memstack::lenw, LIMB_BITS, lmmp_dec, lmmp_fft_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_cache_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_param_assert, lmmp_zero, lmmp_zero_q_(), fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.
被这些函数引用 lmmp_mul_fermat_cache_(), lmmp_mul_fft_cache_(), lmmp_mullo_fft_cache_() , 以及 TEST_CASE().
| 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 第二个操作数将被缓存
| dst | 输出结果缓冲区,长度至少为 rn+1 |
| rn | 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
| ctx | 费马数模乘法缓存上下文 |
引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_param_assert, lmmp_zero, lmmp_zero_q_(), fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::N, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, numb, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.
被这些函数引用 lmmp_mul_fermat_cache_init_(), lmmp_mul_fft_cache_init_(), lmmp_mullo_fft_cache_init_() , 以及 TEST_CASE().
|
static |
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
费马变换乘法递归函数(核心乘法逻辑)
| ms | - 内存栈结构体指针 |
| pc1 | - 第一个数的FFT系数数组指针数组 |
| pc2 | - 第二个数的FFT系数数组指针数组 |
| K0 | - FFT块数 |
引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_debug_assert, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shl_coef_(), lmmp_ifft_(), lmmp_inc_1, lmmp_mul_fermat_recombine_(), lmmp_mul_fermat_recurse_(), lmmp_mul_n_, lmmp_sub_n_(), MUL_FFT_MODF_THRESHOLD, n, numb , 以及 fft_memstack::temp_coef.
被这些函数引用 lmmp_mul_fermat_(), lmmp_mul_fermat_cache_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_() , 以及 lmmp_mul_mersenne_fft_().
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
| dst | 输出结果缓冲区,长度至少为 na+nb |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
引用了 ALLOC_TYPE, lmmp_assert, lmmp_fft_next_size_(), lmmp_free(), lmmp_mul_fft_(), lmmp_mul_fft_crt_(), lmmp_mul_fft_mods_(), lmmp_param_assert, numb , 以及 tp.
被这些函数引用 __lmmp_mul_n_(), bench_mul_fft(), lmmp_mul_(), lmmp_mul_fft_(), lmmp_mul_n_() , 以及 lmmp_mul_toom62_unbalance_().
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
| dst | 输出结果缓冲区,长度至少为 na+nb |
| numa | 第一个输入操作数,长度为 na |
| ctx | FFT乘法缓存上下文 |
引用了 fft_cache::fermat, fft_cache::hn, lmmp_add_(), lmmp_inc, lmmp_mul_fermat_cache_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_crt_(), lmmp_mul_mersenne_cache_(), lmmp_param_assert, lmmp_sub_(), fft_cache::mersenne, fft_cache::na, fft_cache::nb , 以及 fft_cache::tp.
被这些函数引用 lmmp_div_mulinv_(), lmmp_mul_fft_cache_() , 以及 lmmp_mul_fft_unbalance_().
| 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] 第二个操作数将被缓存
| dst | 输出结果缓冲区,长度至少为 na+nb |
| hn | 双域模运算的阶数。须满足 hn<na+nb<=2*hn,使 CRT 重组能容纳完整乘积。 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
| ctx | FFT乘法缓存上下文 |
引用了 ALLOC_TYPE, fft_cache::fermat, fft_cache::hn, lmmp_add_(), lmmp_inc, lmmp_mul_fermat_cache_init_(), lmmp_mul_fft_cache_init_(), lmmp_mul_fft_crt_(), lmmp_mul_mersenne_cache_init_(), lmmp_param_assert, lmmp_sub_(), fft_cache::mersenne, fft_cache::na, fft_cache::nb, numb , 以及 fft_cache::tp.
被这些函数引用 lmmp_div_mulinv_(), lmmp_mul_fft_cache_init_() , 以及 lmmp_mul_fft_unbalance_().
FFT 双域 CRT 重构尾部(lmmp_mul_fft_mods_ 的后半):两域残差 → 精确积
| dst | 输入输出:入口为梅森域残差 [dst,hn](P mod B^hn-1,规范形 [0,B^hn-1)),出口为精确积 [dst,nab] |
| tp | 输入输出:入口为费马域残差 [tp,hn+1](P mod B^hn+1,库规范形 [0,B^hn]),出口内容破坏 |
| hn | 变换阶数(与 mods_ 一致) |
| nab | 积长度界(P < B^nab),hn < nab <= 2*hn |
引用了 LIMB_BITS, lmmp_dec_1, lmmp_inc, lmmp_mul_fft_crt_(), lmmp_shr1add_nc_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_() , 以及 tp.
被这些函数引用 lmmp_mul_fft_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_() , 以及 lmmp_mul_fft_crt_().
|
static |
FFT 双域模乘计算:分别求梅森域与费马域残差(lmmp_mul_fft_crt_ 的前半)
| dst | 输出:梅森域结果 [dst,hn] = P mod (B^hn-1),P = [numa,na]*[numb,nb] |
| tp | 输出:费马域结果 [tp,hn+1] = P mod (B^hn+1)(库规范形 [0,B^hn]), na > hn 时兼作 numa 的费马折叠工作区(需 hn+1 limb) |
| hn | 变换阶数(两域共用) |
| numa | 第一操作数(超长时按域折叠:amodm = a mod (B^hn-1) 原位写入 dst, amodp = a mod (B^hn+1) 原位写入 tp,折叠取 [低hn)±[高位)) |
| na | numa 长度(任意 > 0;> hn 时触发折叠) |
| numb | 第二操作数(不折叠,要求 nb <= hn) |
| nb | numb 长度 |
引用了 lmmp_add_(), lmmp_inc, lmmp_mul_fermat_(), lmmp_mul_fft_mods_(), lmmp_mul_mersenne_fft_(), lmmp_sub_(), numb , 以及 tp.
被这些函数引用 lmmp_mul_fft_() , 以及 lmmp_mul_fft_mods_().
| void lmmp_mul_fft_unbalance_ | ( | mp_ptr restrict | dst, |
| mp_srcptr restrict | numa, | ||
| mp_size_t | na, | ||
| mp_srcptr restrict | numb, | ||
| mp_size_t | nb ) |
引用了 ALLOC_TYPE, lmmp_add_n_(), lmmp_copy, lmmp_fft_cache_free_(), lmmp_fft_next_size_(), lmmp_free(), lmmp_inc, lmmp_mul_(), lmmp_mul_fft_cache_(), lmmp_mul_fft_cache_init_(), lmmp_mul_fft_unbalance_(), lmmp_param_assert, lmmp_zero, numb , 以及 restrict.
| 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
| dst | 输出结果缓冲区,长度为 lmmp_mul_mersenne_cache_init_()函数中输入参数的 rn |
| numa | 第一个输入操作数,长度为 lmmp_mul_mersenne_cache_init_()函数中输入参数的 na |
| ctx | 梅森数模乘法缓存上下文 |
引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::k, fft_memstack::lenw, LIMB_BITS, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shr_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.
被这些函数引用 lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_mont_redc_(), lmmp_mul_fft_cache_(), lmmp_mul_mersenne_cache_(), lmmp_mullo_fft_cache_() , 以及 TEST_CASE().
| 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 第二个操作数将被缓存
| dst | 输出结果缓冲区,长度至少为 rn |
| rn | 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
| ctx | 梅森数模乘法缓存上下文 |
引用了 fft_gr_cache::a_size, fft_gr_cache::amsr, fft_gr_cache::bmsr, fft_gr_cache::K, fft_gr_cache::k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shr_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_cache_init_(), lmmp_param_assert, lmmp_shl_(), lmmp_zero, fft_gr_cache::M, fft_memstack::maxdepth, fft_gr_cache::N, fft_gr_cache::n, fft_gr_cache::na, fft_gr_cache::nlen, numb, fft_gr_cache::rn, fft_memstack::temp_coef, fft_gr_cache::temp_coefb , 以及 fft_memstack::tempdepth.
被这些函数引用 lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_mont_redc_(), lmmp_mul_fft_cache_init_(), lmmp_mul_mersenne_cache_init_(), lmmp_mullo_fft_cache_init_() , 以及 TEST_CASE().
| 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
| dst | 输出结果缓冲区,长度至少为 rn |
| rn | 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
引用了 k, fft_memstack::lenw, LIMB_BITS, LIMB_BYTES, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_fft_(), lmmp_fft_best_k_(), lmmp_fft_extract_coef_(), lmmp_fft_memstack_(), lmmp_fft_shr_coef_(), lmmp_ifft_(), LMMP_MIN, lmmp_mul_fermat_recurse_(), lmmp_mul_mersenne_fft_(), lmmp_shl_(), lmmp_zero, fft_memstack::maxdepth, n, numb, fft_memstack::temp_coef , 以及 fft_memstack::tempdepth.
被这些函数引用 bench_mul_mersenne_fft(), lmmp_mul_fft_mods_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_fft_(), lmmp_mul_toom62_unbalance_(), lmmp_mullo_fft_() , 以及 TEST_CASE().