|
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 "lmmp/lmmpn.h"宏定义 | |
| #define | a0 ap |
| #define | a0 ap |
| #define | a1 (ap + n) |
| #define | a1 (ap + n) |
| #define | b0 bp |
| #define | b1 (bp + n) |
| #define | sp1 (tp + 2 * n + 2) |
| #define | sp1 (tp + 2 * n + 2) |
| #define | xp tp |
| #define | xp tp |
函数 | |
| mp_size_t | lmmp_mersenne_next_size_ (mp_size_t n) |
| 计算满足 >=n 的最小分治梅森乘法可行尺寸 | |
| 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_mul_mersenne_dc_ (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_sqr_mersenne_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na) |
| 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1 | |
| void | lmmp_sqr_mersenne_dc_ (mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na) |
| 分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1 | |
| static int | mrs_fermat_usable_ (mp_size_t n) |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| static void | mrs_mul_bnp1_ (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n, mp_ptr tp) |
| mod B^n+1 基例乘法 [rp,n+1] = [ap,n+1]*[bp,n+1] mod B^n+1(规范形 [0,B^n]) | |
| static void | mrs_mul_core_ (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn, mp_ptr tp) |
| 分治梅森乘法核心(半归一化内部约定:零类 = B^n-1) | |
| static mp_limb_t | mrs_neg_ (mp_ptr dst, mp_srcptr numa, mp_size_t n) |
| 取负 [dst,n] = B^n - [numa,n],返回进位(= [numa,n] != 0) | |
| static void | mrs_norm_zero_ (mp_ptr p, mp_size_t n) |
| 零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示) | |
| static void | mrs_sqr_bnp1_ (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_ptr tp) |
| mod B^n+1 基例平方 [rp,n+1] = [ap,n+1]^2 mod B^n+1(规范形 [0,B^n]) | |
| static void | mrs_sqr_core_ (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_ptr tp) |
| 分治梅森平方核心(半归一化内部约定:零类 = B^n-1) | |
| #define a0 ap |
| #define a0 ap |
被这些函数引用 ll_small_mul1_(), ll_small_sqrmod(), ll_small_sqrmod_sloppy(), lmmp_add_n_sub_n_(), lmmp_addmul_1_(), lmmp_binvert_2_(), lmmp_cbrt_3_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_invsqrt_newton_(), lmmp_mod_2_(), lmmp_mod_2p48sub1_(), lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom44_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mullo_dc_(), lmmp_sqr_basecase_(), lmmp_sqr_toom2_(), lmmp_sqr_toom3_(), lmmp_sqr_toom4_(), lmmp_sqrlo_dc_(), lmmp_sqrt_3_(), mrs_mul_core_(), mrs_sqr_core_(), mul_128(), mul_128(), sqr_128(), sqr_128(), umul128_tohi128() , 以及 umul128_tohi128_r().
| #define a1 (ap + n) |
| #define a1 (ap + n) |
被这些函数引用 ll_small_mul1_(), ll_small_sqrmod(), ll_small_sqrmod_sloppy(), lmmp_add_n_sub_n_(), lmmp_addmul_1_(), lmmp_binvert_2_(), lmmp_cbrt_3_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_invsqrt_newton_(), lmmp_mod_2_(), lmmp_mod_2p48sub1_(), lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom44_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mullo_dc_(), lmmp_nthroot_(), lmmp_sqr_basecase_(), lmmp_sqr_toom2_(), lmmp_sqr_toom3_(), lmmp_sqr_toom4_(), lmmp_sqrlo_dc_(), mrs_mul_core_(), mrs_sqr_core_(), mul_128(), mul_128(), sqr_128(), sqr_128(), umul128_tohi128() , 以及 umul128_tohi128_r().
| #define b0 bp |
被这些函数引用 fill_pattern(), lmmp_add_n_sub_n_(), lmmp_addmul_2_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_mod_2_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mullo_basecase_(), lmmp_mullo_dc_(), mrs_mul_core_(), mul_128(), mul_128(), TEST_CASE(), TEST_CASE(), umul128_tohi128() , 以及 umul128_tohi128_r().
| #define b1 (bp + n) |
被这些函数引用 ll_small_powmod_2ch_(), ll_small_powmod_3_(), lmmp_add_n_sub_n_(), lmmp_addmul_2_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_mod_2_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mullo_dc_(), lmmp_pow_win2_(), lmmp_u32_pow_1_(), lmmp_u64_pow_1_(), mrs_mul_core_(), mul_128(), mul_128(), TEST_CASE(), TEST_CASE(), TEST_CASE(), umul128_tohi128() , 以及 umul128_tohi128_r().
被这些函数引用 mrs_mul_core_() , 以及 mrs_sqr_core_().
| #define xp tp |
| #define xp tp |
被这些函数引用 binvert_mulhi_(), lmmp_fibonacci_(), lmmp_gcdext_derive_(), lmmp_inv_basecase_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mont_redcify_(), lmmp_toom_eval_dgr3_pm1_(), lmmp_toom_eval_dgr3_pm2_(), lmmp_toom_eval_pm1_(), lmmp_toom_eval_pm2_(), lmmp_toom_eval_pm2exp_(), mrs_mul_core_() , 以及 mrs_sqr_core_().
计算满足 >=n 的最小分治梅森乘法可行尺寸
| n | 输入的目标尺寸 |
在文件 mul_mersenne.c 第 408 行定义.
引用了 lmmp_fft_next_size_(), lmmp_mersenne_next_size_(), MUL_FFT_MODF_THRESHOLD, MUL_MERSENNE_DC_THRESHOLD , 以及 n.
被这些函数引用 bench_mul_mersenne_dc(), binvert_mulhi_(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mersenne_next_size_(), lmmp_mont_init_(), lmmp_mont_need_(), lmmp_mul_toom62_unbalance_(), lmmp_redc_() , 以及 TEST_CASE().
| 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
| dst | 输出结果缓冲区,长度至少为 rn |
| rn | 模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc); rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为进入 fft 档的推荐最小值 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
在文件 mul_mersenne.c 第 417 行定义.
引用了 lmmp_fft_next_size_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_mersenne_fft_(), MUL_MERSENNE_FFT_THRESHOLD, numb , 以及 tp.
被这些函数引用 binvert_mulhi_(), lmmp_binvert_unbalance_(), lmmp_div_mulinv_(), lmmp_divexact_mu_run_(), lmmp_hgcd_apply_mod_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mont_redc_(), lmmp_mul_mersenne_(), lmmp_mul_toom62_unbalance_(), lmmp_redc_() , 以及 TEST_CASE().
| void lmmp_mul_mersenne_dc_ | ( | 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
| dst | 输出结果缓冲区,长度至少为 rn |
| rn | 模运算的阶数参数 |
| numa | 第一个输入操作数,长度为 na |
| na | 第一个操作数的 limb 长度 |
| numb | 第二个输入操作数,长度为 nb |
| nb | 第二个操作数的 limb 长度 |
在文件 mul_mersenne.c 第 385 行定义.
引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_free(), lmmp_mul_mersenne_dc_(), lmmp_param_assert, mrs_mul_core_(), mrs_norm_zero_(), numb , 以及 tp.
被这些函数引用 bench_mul_mersenne_dc(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_dc_(), lmmp_mul_toom62_unbalance_() , 以及 TEST_CASE().
梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
| dst | 输出结果缓冲区,长度至少为 rn |
| rn | 模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc); rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为进入 fft 档的推荐最小值 |
| numa | 输入操作数,长度为 na |
| na | 输入操作数的 limb 长度 |
在文件 mul_mersenne.c 第 434 行定义.
引用了 lmmp_fft_next_size_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_(), lmmp_sqr_mersenne_fft_() , 以及 SQR_MERSENNE_FFT_THRESHOLD.
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_mul_toom62_unbalance_(), lmmp_sqr_mersenne_() , 以及 TEST_CASE().
分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
| dst | 输出结果缓冲区,长度至少为 rn |
| rn | 模运算的阶数参数 |
| numa | 输入操作数,长度为 na |
| na | 输入操作数的 limb 长度 |
在文件 mul_mersenne.c 第 397 行定义.
引用了 ALLOC_TYPE, lmmp_debug_assert, lmmp_free(), lmmp_param_assert, lmmp_sqr_mersenne_dc_(), mrs_norm_zero_(), mrs_sqr_core_() , 以及 tp.
被这些函数引用 lmmp_mul_toom62_unbalance_(), lmmp_sqr_mersenne_(), lmmp_sqr_mersenne_dc_() , 以及 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
判断 n 是否为费马变换可行尺寸(64n 能被 2^best_k 整除)
| n | 输入的 limb 长度 |
在文件 mul_mersenne.c 第 35 行定义.
引用了 k, lmmp_fft_best_k_(), LOG2_LIMB_BITS, mrs_fermat_usable_() , 以及 n.
被这些函数引用 mrs_fermat_usable_(), mrs_mul_core_() , 以及 mrs_sqr_core_().
mod B^n+1 基例乘法 [rp,n+1] = [ap,n+1]*[bp,n+1] mod B^n+1(规范形 [0,B^n])
| rp | 输出缓冲区,长度至少为 n+1 |
| ap | 第一个操作数(高半域形,值 < B^n+1),长度为 n+1 |
| bp | 第二个操作数,长度为 n+1 |
| n | 模运算的阶数 |
| tp | 工作区,长度至少为 2n(允许 tp==rp) |
在文件 mul_mersenne.c 第 68 行定义.
引用了 lmmp_inc_1, lmmp_mul_n_, lmmp_sub_n_(), mrs_mul_bnp1_(), mrs_neg_(), n, rp , 以及 tp.
被这些函数引用 mrs_mul_bnp1_() , 以及 mrs_mul_core_().
|
static |
分治梅森乘法核心(半归一化内部约定:零类 = B^n-1)
| rp | 输出 [rp,rn] = [ap,an]*[bp,bn] mod B^rn-1(半归一化,写入完整 rn limb) |
| rn | 模运算的阶数 |
| ap | 第一个操作数 |
| an | 第一个操作数的 limb 长度 |
| bp | 第二个操作数 |
| bn | 第二个操作数的 limb 长度 |
| tp | 工作区,长度至少为 2rn+4 |
在文件 mul_mersenne.c 第 117 行定义.
引用了 a0, a1, am1, an, ap1, b0, b1, bm1, bn, bp1, LIMB_BITS, lmmp_add_(), lmmp_add_n_(), lmmp_debug_assert, lmmp_dec_1, lmmp_inc, lmmp_inc_1, lmmp_mul_(), lmmp_mul_fermat_(), lmmp_mul_n_, lmmp_shr1add_nc_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_(), lmmp_zero, mrs_fermat_usable_(), mrs_mul_bnp1_(), mrs_mul_core_(), MUL_MERSENNE_DC_THRESHOLD, MUL_MERSENNE_FERMAT_THRESHOLD, n, rp, sp1, tp , 以及 xp.
被这些函数引用 lmmp_mul_mersenne_dc_() , 以及 mrs_mul_core_().
取负 [dst,n] = B^n - [numa,n],返回进位(= [numa,n] != 0)
| dst | 输出缓冲区,长度至少为 n |
| numa | 输入操作数,长度为 n |
| n | 操作数的 limb 长度 |
在文件 mul_mersenne.c 第 47 行定义.
引用了 lmmp_inc, lmmp_not_(), lmmp_zero, lmmp_zero_q_(), mrs_neg_() , 以及 n.
被这些函数引用 mrs_mul_bnp1_() , 以及 mrs_neg_().
零类归一化:[p,n] == B^n-1 时清零(内部半归一化 → 库规范 0 表示)
| p | 输入输出缓冲区,长度为 n |
| n | limb 长度 |
在文件 mul_mersenne.c 第 379 行定义.
引用了 lmmp_zero, mrs_norm_zero_() , 以及 n.
被这些函数引用 lmmp_mul_mersenne_dc_(), lmmp_sqr_mersenne_dc_() , 以及 mrs_norm_zero_().
mod B^n+1 基例平方 [rp,n+1] = [ap,n+1]^2 mod B^n+1(规范形 [0,B^n])
| rp | 输出缓冲区,长度至少为 n+1 |
| ap | 操作数(高半域形,值 < B^n+1),长度为 n+1 |
| n | 模运算的阶数 |
| tp | 工作区,长度至少为 2n(允许 tp==rp) |
在文件 mul_mersenne.c 第 93 行定义.
引用了 lmmp_inc_1, lmmp_sqr_, lmmp_sub_n_(), lmmp_zero, mrs_sqr_bnp1_(), n, rp , 以及 tp.
被这些函数引用 mrs_sqr_bnp1_() , 以及 mrs_sqr_core_().
分治梅森平方核心(半归一化内部约定:零类 = B^n-1)
| rp | 输出 [rp,rn] = [ap,an]^2 mod B^rn-1(半归一化,写入完整 rn limb) |
| rn | 模运算的阶数 |
| ap | 操作数 |
| an | 操作数的 limb 长度 |
| tp | 工作区,长度至少为 2rn+4 |
在文件 mul_mersenne.c 第 268 行定义.
引用了 a0, a1, am1, an, ap1, LIMB_BITS, lmmp_add_(), lmmp_add_n_(), lmmp_debug_assert, lmmp_dec_1, lmmp_inc, lmmp_inc_1, lmmp_shr1add_nc_(), lmmp_sqr_, lmmp_sqr_fermat_(), lmmp_sub_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_sub_nc_(), lmmp_zero, mrs_fermat_usable_(), mrs_sqr_bnp1_(), mrs_sqr_core_(), n, rp, sp1, SQR_MERSENNE_DC_THRESHOLD, SQR_MERSENNE_FERMAT_THRESHOLD, tp , 以及 xp.
被这些函数引用 lmmp_sqr_mersenne_dc_() , 以及 mrs_sqr_core_().