|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "lmmp/lmmpn.h"#include "lmmp/numth.h"#include "impl/longlong.h"#include "mparam.h"#include "impl/mul_cache.h"结构体 | |
| struct | lmmp_mont_sp_t |
| struct | lmmp_mont_t |
| Copyright (C) 2026 HJimmyK (Jericho Knox) 更多... | |
函数 | |
| 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_free_ (lmmp_mont_t *mc) |
| 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 mp_size_t | lmmp_mont_need_ (mp_size_t n, int anchors) |
| 蒙域上下文的分段工作区长度 | |
| 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 | |
| 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 步进消零 | |
| 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 int | lmmp_mont_sp_init_ (lmmp_mont_sp_t *mc, mp_srcptr mp, mp_size_t n) |
| 稀疏形状探测与上下文装配(O(n) 扫描,免分配) | |
| 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 | |
| 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 mp_size_t | lmmp_powmod_odd_mont_need_ (mp_size_t n, mp_bitcnt_t eb) |
| 蒙域梯子(lmmp_powmod_odd_mont_)的调用者工作区长度 | |
| static unsigned | lmmp_powmod_win_size_ (mp_bitcnt_t eb) |
| 模幂滑动窗口尺寸(按指数位长分档) | |
| struct lmmp_mont_sp_t |
| struct lmmp_mont_t |
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
| 成员变量 | ||
|---|---|---|
| int | fold | |
| mp_ptr | hi | |
| mp_ptr | Lbuf | |
| mp_srcptr | m | |
| mp_ptr | m1 | |
| fft_gr_cache | mcache | |
| int | mcache_on | |
| mp_ptr | mscratch | |
| mp_size_t | msz | |
| mp_ptr | mulhi | |
| mp_size_t | n | |
| fft_mullo_cache | ncache | |
| int | ncache_on | |
| mp_ptr | ninv | |
| mp_limb_t | ninv1 | |
| mp_limb_t | ninv2 | |
| mp_ptr | one | |
| mp_ptr | q | |
| mp_ptr | V | |
|
inlinestatic |
从梅森折叠积中提取高半积(低位已知变体的 mulhi)
| hi | 结果指针(n 个limb),接收 [q,n]*[mp,n] div B^n |
| V | 输入兼工作区(msz 个limb),入口为 q*m mod B^msz-1,出口被破坏 |
| L | 已知低位(n 个limb),满足 q*m ≡ L (mod B^n),此处 L = -t_lo mod B^n |
| n | 操作数长度 |
| msz | 折叠尺寸,admissible 且 n <= msz < 2n |
引用了 lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_sub_1_(), lmmp_sub_n_(), n , 以及 restrict.
|
inlinestatic |
引用了 lmmp_fft_gr_cache_free_(), lmmp_mullo_cache_free_(), lmmp_mont_t::mcache, lmmp_mont_t::mcache_on, lmmp_mont_t::ncache , 以及 lmmp_mont_t::ncache_on.
|
inlinestatic |
蒙域上下文初始化:切分 REDC 工作段并预计算 ninv 与探测基准
| mc | 上下文(出口就绪) |
| mp | 模数(n 个limb,奇,mc->m 引用之,生命周期须覆盖上下文全程) |
| n | 模数 limb 长度 |
| arena | 工作区分段头(lmmp_mont_need_(n,anchors) 个limb) |
| anchors | 1 = 预计算 one/m1(蒙域 ±1 探测基准),0 = 免配 |
| prod | [2n] redcify 工作区(与 arena 分段分离,出口被破坏) |
引用了 _umul64to64hi_(), lmmp_mont_t::fold, lmmp_mont_t::hi, lmmp_mont_t::Lbuf, lmmp_binvert_(), lmmp_binvert_ulong_(), lmmp_debug_assert, lmmp_fft_next_size_(), lmmp_inc, lmmp_mersenne_next_size_(), lmmp_mont_redcify_(), lmmp_not_(), lmmp_sub_n_(), lmmp_zero, lmmp_mont_t::m, lmmp_mont_t::m1, lmmp_mont_t::mcache_on, lmmp_mont_t::mscratch, lmmp_mont_t::msz, lmmp_mont_t::mulhi, lmmp_mont_t::n, n, lmmp_mont_t::ncache_on, lmmp_mont_t::ninv, lmmp_mont_t::ninv1, lmmp_mont_t::ninv2, lmmp_mont_t::one, prod, lmmp_mont_t::q, REDC_BASECASE_THRESHOLD, REDC_MERSENNE_CACHE_THRESHOLD, REDC_MERSENNE_THRESHOLD, restrict , 以及 lmmp_mont_t::V.
蒙域上下文的分段工作区长度
| n | 模数 limb 长度 |
| anchors | 1 = 含 one/m1 探测基准段,0 = 仅 REDC 工作段 |
引用了 lmmp_fft_next_size_(), lmmp_mersenne_next_size_(), n, REDC_BASECASE_THRESHOLD, REDC_MERSENNE_CACHE_THRESHOLD , 以及 REDC_MERSENNE_THRESHOLD.
REDC 单步并规范化:[dst,n] = (t + q*m)/B^n mod m,结果 < m
| dst | 结果指针(n 个limb) |
| tp | 被归约数兼工作区(2n 个limb,t < B^n*[m,n],出口被破坏) |
| mc | 蒙域上下文(须已完成 lmmp_mont_init_) |
引用了 lmmp_add_nc_(), lmmp_cmp_(), lmmp_inc, lmmp_mont_redc_(), lmmp_mul_mersenne_(), lmmp_mul_mersenne_cache_(), lmmp_mul_mersenne_cache_init_(), lmmp_mul_n_, lmmp_mullo_dc_(), lmmp_mullo_fft_cache_(), lmmp_mullo_fft_cache_init_(), lmmp_not_(), lmmp_sub_n_(), lmmp_zero, lmmp_zero_q_(), MULLO_DC_THRESHOLD, n, REDC_BASECASE_THRESHOLD, restrict , 以及 tp.
被这些函数引用 ipn_lucas_i_(), ipn_notrial_i_(), ipn_sprp_1_(), ipn_sprp_base2_(), lmmp_mont_redc_(), lmmp_powmod_odd_() , 以及 lmmp_powmod_odd_mont_().
|
inlinestatic |
basecase REDC:链式 Hensel 归约,addmul_2 双 limb 步进消零
| dst | 结果指针(n 个limb),接收 ([up,2n] + q*m)/B^n 的低 n limb |
| up | 输入兼工作区(2n 个limb,出口被破坏) |
| m | 模数(n 个limb) |
| n | 操作数长度 |
| ninv1 | -m^(-1) mod B(单 limb) |
| ninv2 | -m^(-1) mod B^2 的高 limb(n == 1 时不会读到) |
引用了 _umul64to128_(), lmmp_add_n_(), lmmp_addmul_1_(), lmmp_addmul_2_(), n , 以及 restrict.
|
inlinestatic |
进蒙域:[dst,n] = [xp,n]*B^n mod [mp,n]
| dst | 结果指针(n 个limb) |
| xp | 普通域输入(n 个limb,eqsep(dst,xp)) |
| n | 操作数长度 |
| prod | 工作区(2n 个limb,出口被破坏,sep(dst,xp,mp)) |
| mp | 模数(n 个limb) |
引用了 lmmp_copy, lmmp_div_(), lmmp_zero, n, prod, restrict , 以及 xp.
被这些函数引用 lmmp_mont_init_().
|
inlinestatic |
稀疏形状探测与上下文装配(O(n) 扫描,免分配)
| mc | 上下文(出口:形状命中时就绪,否则 form=0 其余字段为 0) |
| mp | 模数(n 个limb,奇,顶 limb 非零) |
| n | 模数 limb 长度 |
引用了 lmmp_mont_sp_t::form, lmmp_mont_sp_t::kv0, lmmp_mont_sp_t::kv1, LIMB_MAX, lmmp_debug_assert, lmmp_mont_sp_t::m, lmmp_mont_sp_t::n, n , 以及 lmmp_mont_sp_t::p.
|
inlinestatic |
稀疏模数 REDC 单步并规范化:[dst,n] = t*B^(-n) mod m,结果 < m
| dst | 结果指针(n 个limb) |
| tp | 被归约数兼工作区(2n 个limb,t < m*B^n,出口被破坏) |
| mc | 稀疏蒙域上下文(须已完成 lmmp_mont_sp_init_ 且 form != 0) |
引用了 LIMB_MAX, lmmp_add_1_(), lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_sub_n_(), n, restrict, s, t , 以及 tp.
| 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 ) |
奇模数蒙域模幂梯子(滑动窗口),结果留在蒙域
| u | 出口(n 个limb)= b^e·R mod m < m,亦为梯子累加器 |
| bp | 普通域基底(n 个limb,0 < [bp,n] < [mc->m,n]) |
| ep | 指数(en 个limb,顶 limb 非零) |
| en | 指数 limb 长度 |
| mc | 蒙域上下文(须已完成 lmmp_mont_init_) |
| b2 | 表生成暂存(n 个limb,b²R mod m,出口死) |
| prod | 工作区(2n 个limb,平方/乘法全积兼 redcify,出口被破坏) |
| pp | 奇次幂表(n << (lmmp_powmod_win_size_(eb)-1) 个limb,出口死) |
引用了 b2, count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_copy, lmmp_debug_assert, LMMP_MIN, lmmp_mont_redc_(), lmmp_mul_(), lmmp_param_assert, lmmp_powmod_odd_mont_(), lmmp_sqr_, n, prod , 以及 restrict.
被这些函数引用 ipn_notrial_i_(), lmmp_powmod_odd_() , 以及 lmmp_powmod_odd_mont_().
|
inlinestatic |
蒙域梯子(lmmp_powmod_odd_mont_)的调用者工作区长度
| n | 模数 limb 长度 |
| eb | 指数位长(>0) |
引用了 lmmp_powmod_odd_mont_need_(), lmmp_powmod_win_size_() , 以及 n.
被这些函数引用 lmmp_powmod_odd_mont_need_().
|
inlinestatic |
模幂滑动窗口尺寸(按指数位长分档)
| eb | 指数位长(>0) |
引用了 k.
被这些函数引用 lmmp_powmod_odd_mont_need_().