30#define LMMP_INLINE static inline
42 return (*(
char*)&num) != 0;
988 b = (nq - 1) / nb + 1;
989 ni = (nq - 1) / b + 1;
990 }
else if (3 * nq > nb) {
991 ni = (nq - 1) / 2 + 1;
993 ni = (nq - 1) / 1 + 1;
1106#define lmmp_inc(p) \
1109 while (++(*(_p_++)) == 0); \
1118#define lmmp_inc_1(p, inc) \
1121 mp_limb_t _inc_ = (inc), _x_; \
1122 _x_ = *_p_ + _inc_; \
1125 while (++(*(++_p_)) == 0); \
1133#define lmmp_dec(p) \
1136 while ((*(_p_++))-- == 0); \
1145#define lmmp_dec_1(p, dec) \
1148 mp_limb_t _dec_ = (dec), _x_; \
1150 *_p_ = _x_ - _dec_; \
1152 while ((*(++_p_))-- == 0); \
1176#if defined(__GNUC__) && !defined(__clang__) && __GNUC__ >= 15
1177 #define LMMP_NOVECTOR _Pragma("GCC novector")
1179 #define LMMP_NOVECTOR
1182#define LMMP_AORS_(FUNCTION, TEST) \
1184 if (FUNCTION(dst, numa, numb, nb)) { \
1192 if (dst != numa && na != nb) \
1193 lmmp_copy(dst + nb, numa + nb, na - nb); \
1227#define LMMP_AORS_1_(OP, CB) \
1228 mp_size_t _i_ = 1; \
1229 mp_limb_t _x_ = numa[0], _r_ = _x_ OP x; \
1231 if (CB(_r_, _x_, x)) { \
1239 } while (CB(_r_, _x_, 1)); \
1241 if (numa != dst && na != _i_) \
1242 lmmp_copy(dst + _i_, numa + _i_, na - _i_); \
1246#define LMMP_ADDCB_(r, x, y) ((r) < (y))
1248#define LMMP_SUBCB_(r, x, y) ((x) < (y))
#define lmmp_leading_zeros_
#define lmmp_limb_popcnt_
#define lmmp_tailing_zeros_
#define LMMP_API
Copyright (C) 2026 HJimmyK (Jericho Knox)
const mp_limb_t * mp_srcptr
mp_limb_t lmmp_shlnot_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1
#define LMMP_SUBCB_(r, x, y)
mp_limb_t lmmp_div_3_2_(mp_ptr numa, mp_srcptr numb, mp_limb_t inv21)
3/2位除法运算 [numa,2]=[numa,3] mod [numb,2]
void lmmp_b36_to_chars_(mp_byte_t *dst, mp_size_t n, bool upper)
36进制数字字节原地转字符 [dst,n]: [0,35] -> ['0'-'9','a'-'z']或['0'-'9','A'-'Z']
void lmmp_mul_toom22_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-22乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
void lmmp_invappr_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算 (invappr)
static mp_size_t lmmp_div_inv_size_(mp_size_t nq, mp_size_t nb)
计算预计算逆元的尺寸
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
void lmmp_mul_toom44_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-44乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
#define LMMP_AORS_(FUNCTION, TEST)
void lmmp_mul_toom6h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,...
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_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
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
mp_limb_t lmmp_shr_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr, mp_limb_t c)
带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位
mp_limb_t lmmp_shr1add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
mp_limb_t lmmp_addmul_2_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
mp_size_t lmmp_to_hex_len_(mp_srcptr numa, mp_size_t na)
计算转换为十六进制字符串需要的缓冲区长度
mp_size_t lmmp_from_hex_len_(const char *src, mp_size_t len)
计算十六进制字符串转limb数组所需的 limb 缓冲区长度
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
mp_size_t lmmp_to_decimal_(char *dst, mp_srcptr numa, mp_size_t na)
limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]
void lmmp_mul_toom42_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqrlo_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
基础低位平方 [dst,n] = [numa,n]^2 mod B^n
void lmmp_inv_prediv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
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_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
void lmmp_sqr_toom8_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-8平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)
void lmmp_sqr_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
基础平方运算 [dst,2*na] = [numa,na]^2
mp_limb_t lmmp_mod_preinv_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
void lmmp_mul_toom42_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
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_mullo_dc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_mullo_basecase_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
基础低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
mp_limb_t lmmp_subshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法结合左移1位操作 [dst,n] = [numa,n] - ([numb,n] << 1)
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
mp_bitcnt_t lmmp_extract_bits_(mp_srcptr num, mp_size_t n, mp_limb_t *ext, int bits)
提取高位指定位数,并返回低位bits位数
mp_size_t lmmp_from_decimal_(mp_ptr dst, const char *src, mp_size_t len)
十进制字符串转limb数组 [src,len,10] to [dst,return value,B]
void lmmp_mul_toom43_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-43乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
mp_size_t lmmp_to_str_(mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base)
limb数组转字节数组操作 [numa,na,B] to [dst,return value,base]
mp_size_t lmmp_to_hex_(char *dst, mp_srcptr numa, mp_size_t na, bool upper)
limb数组转十六进制字符串 [numa,na,B] to [dst,return value,16]
void lmmp_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
#define LMMP_AORS_1_(OP, CB)
void lmmp_dec_to_chars_(mp_byte_t *dst, mp_size_t n)
十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']
void lmmp_mul_basecase_(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_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
#define LMMP_INLINE
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_sqr_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
FFT平方运算 [dst,2*na] = [numa,na]^2
mp_size_t lmmp_from_str_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base)
字节数组转limb数组操作 [src,len,base] to [dst,return value,B]
void lmmp_sqr_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_mul_toom32_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-32乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_size_t lmmp_to_str_len_(mp_srcptr numa, mp_size_t na, int base)
计算转换为字节数组,字节数组需要的缓冲区长度
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_sqr_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
void lmmp_invappr_newton_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算(牛顿迭代法)
void lmmp_mul_toom52_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-52乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_shl_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl, mp_limb_t c)
带进位的左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充c的低shl位
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
void lmmp_mul_toom62_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom2_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-2平方运算 [dst,2*na] = [numa,na]^2
mp_limb_t lmmp_add_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
void lmmp_sqr_toom3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-3平方运算 [dst,2*na] = [numa,na]^2
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_limb_t lmmp_shr1sub_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
void lmmp_bninv_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_size_t ni)
近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_sqrlo_dc_(mp_ptr dst, mp_srcptr numa, mp_ptr tp, mp_size_t n)
低位平方 [dst,n] = [numa,n]^2 mod B^n
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
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
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
#define LMMP_ADDCB_(r, x, y)
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]
void lmmp_mul_toom8h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±8,...
void lmmp_mul_toom53_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mullo_fft_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
mp_size_t lmmp_to_decimal_len_(mp_srcptr numa, mp_size_t na)
计算转换为十进制字符串需要的缓冲区长度
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
void lmmp_inv_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算
mp_size_t lmmp_from_decimal_len_(const char *src, mp_size_t len)
计算十进制字符串转limb数组所需的 limb 缓冲区长度
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
static bool lmmp_endian(void)
运行时判断端序
mp_size_t lmmp_from_hex_(mp_ptr dst, const char *src, mp_size_t len)
十六进制字符串转limb数组 [src,len,16] to [dst,return value,B]
mp_limb_t lmmp_div_mulinv_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_srcptr invappr, mp_size_t ni)
乘法逆元除法
void lmmp_inv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t nf)
求逆操作 [dst,na+nf+1] = (B^(2*(na+nf)) - 1) / ([numa,na]*B^nf) + [0|-1]
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
mp_limb_t lmmp_div_2_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
双精度数除法(除数为2个limb)
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
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_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
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]
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
mp_limb_t lmmp_shr1sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
void lmmp_sqr_toom6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-6平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
mp_limb_t lmmp_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
void lmmp_mul_toom62_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mullo_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
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_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
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_toom33_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom4_(mp_ptr dst, mp_srcptr numa, mp_size_t an)
Toom-4平方运算 [dst,2*na] = [numa,na]^2
mp_size_t lmmp_from_str_len_(const mp_byte_t *src, mp_size_t len, int base)
计算字节数组转limb数组所需的 limb 缓冲区长度