|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "lmmpn/fft_ssa.h"结构体 | |
| struct | fft_cache |
| struct | fft_gr_cache |
| Copyright (C) 2026 HJimmyK (Jericho Knox) 更多... | |
| struct | fft_mullo_cache |
函数 | |
| static void | lmmp_fft_cache_free_ (fft_cache *ctx) |
| 释放FFT模乘法缓存上下文 | |
| static void | lmmp_fft_gr_cache_free_ (fft_gr_cache *ctx) |
| 释放费马或梅森数模乘法缓存上下文 | |
| 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_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] 第二个操作数将被缓存 | |
| 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 第二个操作数将被缓存 | |
| static void | lmmp_mullo_cache_free_ (fft_mullo_cache *ctx) |
| 释放 mullo 缓存上下文 | |
| 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 第二个操作数将被缓存 | |
| struct fft_cache |
在文件 mul_cache.h 第 44 行定义.
| 成员变量 | ||
|---|---|---|
| fft_gr_cache | fermat | |
| mp_size_t | hn | |
| fft_gr_cache | mersenne | |
| mp_size_t | na | |
| mp_size_t | nb | |
| mp_ptr | tp | |
| struct fft_gr_cache |
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
在文件 mul_cache.h 第 29 行定义.
| 成员变量 | ||
|---|---|---|
| mp_size_t | a_size | |
| fft_memstack | amsr | |
| fft_memstack | bmsr | |
| mp_size_t | K | |
| mp_size_t | k | |
| mp_size_t | M | |
| mp_size_t | N | |
| mp_size_t | n | |
| mp_size_t | na | |
| mp_size_t | nlen | |
| mp_size_t | rn | |
| mp_ptr | temp_coefb | |
| struct fft_mullo_cache |
|
inlinestatic |
释放FFT模乘法缓存上下文
| ctx | FFT模乘法缓存上下文 |
在文件 mul_cache.h 第 71 行定义.
引用了 fft_cache::fermat, lmmp_fft_cache_free_(), lmmp_fft_gr_cache_free_(), lmmp_free(), fft_cache::mersenne , 以及 fft_cache::tp.
被这些函数引用 lmmp_div_mulinv_(), lmmp_fft_cache_free_(), lmmp_mul_fft_unbalance_() , 以及 lmmp_mullo_cache_free_().
|
inlinestatic |
释放费马或梅森数模乘法缓存上下文
| ctx | 费马或梅森数模乘法缓存上下文 |
在文件 mul_cache.h 第 63 行定义.
引用了 fft_gr_cache::bmsr, lmmp_fft_gr_cache_free_() , 以及 lmmp_fft_memstack_().
被这些函数引用 lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_fft_cache_free_(), lmmp_fft_gr_cache_free_(), lmmp_hgcd_apply_mod_(), lmmp_mont_free_(), TEST_CASE() , 以及 TEST_CASE().
| 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().
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_().
| 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().
|
inlinestatic |
释放 mullo 缓存上下文
| ctx | mullo 缓存上下文 |
在文件 mul_cache.h 第 81 行定义.
引用了 lmmp_fft_cache_free_(), lmmp_mullo_cache_free_() , 以及 fft_mullo_cache::mul.
被这些函数引用 lmmp_binvert_unbalance_(), lmmp_divexact_mu_run_(), lmmp_mont_free_() , 以及 lmmp_mullo_cache_free_().
| 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
| dst | 输出结果缓冲区,长度至少为 n |
| numa | 第一个输入操作数,长度为 lmmp_mullo_fft_cache_init_() 中输入参数的 n |
| scratch | 临时空间(2*n 个 limb) |
| ctx | mullo 缓存上下文 |
引用了 fft_cache::fermat, fft_mullo_cache::hn, lmmp_mul_fermat_cache_(), lmmp_mul_mersenne_cache_(), lmmp_mullo_crt_(), lmmp_mullo_fft_cache_(), lmmp_param_assert, fft_cache::mersenne, fft_mullo_cache::mul, fft_mullo_cache::n, scratch , 以及 fft_cache::tp.
被这些函数引用 lmmp_binvert_unbalance_(), lmmp_divexact_mu_run_(), lmmp_mont_redc_() , 以及 lmmp_mullo_fft_cache_().
| 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 第二个操作数将被缓存
| dst | 输出结果缓冲区,长度至少为 n |
| numa | 第一个输入操作数,长度为 n |
| numb | 第二个输入操作数,长度为 n |
| n | 操作数的 limb 长度 |
| scratch | 临时空间(2*n 个 limb,两操作数分离) |
| ctx | mullo 缓存上下文 |
引用了 ALLOC_TYPE, fft_cache::fermat, fft_cache::hn, fft_mullo_cache::hn, lmmp_debug_assert, lmmp_fft_next_size_(), lmmp_mul_fermat_cache_init_(), lmmp_mul_mersenne_cache_init_(), lmmp_mullo_crt_(), lmmp_mullo_fft_cache_init_(), lmmp_param_assert, fft_cache::mersenne, fft_mullo_cache::mul, fft_mullo_cache::n, n, fft_cache::na, fft_cache::nb, numb, scratch , 以及 fft_cache::tp.
被这些函数引用 lmmp_binvert_unbalance_(), lmmp_divexact_mu_run_(), lmmp_mont_redc_() , 以及 lmmp_mullo_fft_cache_init_().