|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
结构体 | |
| struct | lmmp_hgcd_matrix_t |
| hgcd 变换矩阵 更多... | |
类型定义 | |
| typedef int8_t | schar |
| typedef int8_t * | scharp |
| typedef int32_t | sint |
| typedef int32_t * | sintp |
| typedef int64_t | slong |
| typedef int64_t * | slongp |
| typedef int16_t | sshort |
| typedef int16_t * | sshortp |
| typedef uint8_t | uchar |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| typedef uint8_t * | ucharp |
| typedef uint32_t | uint |
| typedef uint32_t * | uintp |
| typedef uint64_t | ulong |
| typedef uint64_t * | ulongp |
| typedef uint16_t | ushort |
| typedef uint16_t * | ushortp |
函数 | |
| mp_size_t | lmmp_2factorial_ (mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n) |
| 计算 n! | |
| mp_size_t | lmmp_2factorial_size_ (uint n, mp_bitcnt_t *bits) |
| 计算 n! | |
| mp_size_t | lmmp_arith_seqprod_ (mp_ptr dst, mp_size_t rn, uint x, uint n, uint m) |
| 计算等差数列乘积 x(x+m)...(x+n*m) | |
| mp_size_t | lmmp_arith_seqprod_size_ (uint x, uint n, uint m) |
| 计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度 | |
| void | lmmp_binvert_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n) |
| 计算 [numa,na] 在 B^n 下的逆元 | |
| void | lmmp_binvert_2_ (mp_ptr dst, mp_srcptr numa) |
| 计算 [numa,2] 在 B^2 下的逆元 | |
| void | lmmp_binvert_3_ (mp_ptr dst, mp_srcptr numa) |
| 计算 [numa,3] 在 B^3 下的逆元 | |
| void | lmmp_binvert_4_ (mp_ptr dst, mp_srcptr numa) |
| 计算 [numa,4] 在 B^4 下的逆元 | |
| void | lmmp_binvert_n_dc_ (mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp) |
| 计算 [numa,n] 在 B^n 下的逆元 | |
| uint | lmmp_binvert_uint_ (uint a) |
| 计算 a 在2^32下的逆元 | |
| ulong | lmmp_binvert_ulong_ (ulong a) |
| 计算 a 在2^64下的逆元 | |
| void | lmmp_binvert_unbalance_ (mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n, mp_ptr tp) |
| 计算 [numa,na] 在 B^n 下的逆元 | |
| void | lmmp_binvert_unbalance_1_ (mp_ptr dst, mp_limb_t a, mp_size_t n) |
| 计算 a 在 B^n 下的逆元 | |
| void | lmmp_binvert_unbalance_2_ (mp_ptr dst, mp_srcptr numa, mp_size_t n) |
| 计算 [numa,2] 在 B^n 下的逆元 | |
| void | lmmp_cbrt_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf) |
| 计算 [numa,na] * B^(3*nf) 的立方根和余数 | |
| mp_limb_t | lmmp_cbrt_3_ (mp_limb_t a0, mp_limb_t a1, mp_limb_t a2) |
| 计算算数立方根 floor(cbrt(a0+a1*B+a2*B^2)) | |
| void | lmmp_cbrt_6_ (mp_ptr dst, mp_srcptr numa, mp_size_t na) |
| 计算算术立方根 floor(cbrt([numa,na])) | |
| void | lmmp_cbrt_6_fast_ (mp_ptr dst, mp_ptr numa, mp_ptr tp) |
| 计算算术立方根 [dst,2] = floor(cbrt([numa,6])) | |
| ulong | lmmp_cbrt_chebyshev_ (ulong n) |
| 计算算数立方根 floor(cbrt(n)) | |
| void | lmmp_cbrt_divide_ (mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr) |
| 计算算术立方根 floor(cbrt([numa,3*ns])) | |
| void | lmmp_cbrt_newton_ (mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf) |
| 计算近似立方根 [dsts,na/3+nf+1]=[floor|round](cbrt([numa,na]*B^(3*nf))), 输入须已归一化:na ≡ 0 (mod 3) 且顶 limb >= B/8 | |
| ulong | lmmp_cbrt_ulong_ (ulong n) |
| 计算算数立方根 floor(cbrt(n)) | |
| void | lmmp_divexact_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn) |
| 精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0) | |
| void | lmmp_divexact_1_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv) |
| 精确除法([dst,nn]=[np,nn]/d,且余数必须为0) | |
| void | lmmp_divexact_2_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv) |
| 精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0) | |
| void | lmmp_divexact_basecase_ (mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn) |
| 精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法 | |
| void | lmmp_divexact_divide_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn) |
| 精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法 | |
| void | lmmp_divexact_unbalance_ (mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv) |
| 精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0) | |
| mp_size_t | lmmp_factorial_ (mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n) |
| 计算 n! | |
| mp_size_t | lmmp_factorial_size_ (uint n, mp_bitcnt_t *bits) |
| 计算 n! | |
| mp_size_t | lmmp_fibonacci2_ (mp_ptr dst, mp_ptr dst2, mp_size_t rn, ulong n) |
| 计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1] | |
| mp_size_t | lmmp_fibonacci_ (mp_ptr dst, mp_size_t rn, ulong n) |
| 计算 Fibonacci 数 [dst,rn] = F[n] | |
| mp_size_t | lmmp_fibonacci_size_ (ulong n) |
| 计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度 | |
| mp_size_t | lmmp_gcd_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) |
| 计算两个无符号整数的最大公约数(通用分发入口) | |
| mp_limb_t | lmmp_gcd_11_ (mp_limb_t u, mp_limb_t v) |
| 计算两个无符号整数的最大公约数 | |
| mp_limb_t | lmmp_gcd_1_ (mp_srcptr up, mp_size_t un, mp_limb_t v) |
| 计算两个无符号整数的最大公约数 | |
| mp_size_t | lmmp_gcd_22_ (mp_ptr dst, mp_srcptr up, mp_srcptr vp) |
| 计算两个无符号整数的最大公约数 | |
| mp_size_t | lmmp_gcd_2_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp) |
| 计算两个无符号整数的最大公约数 | |
| mp_size_t | lmmp_gcd_hgcd_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) |
| 计算两个无符号整数的最大公约数(hgcd 分治,长输入优选) | |
| mp_size_t | lmmp_gcd_lehmer_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) |
| 计算两个无符号整数的最大公约数(Lehmer算法) | |
| mp_size_t | lmmp_gcdext_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) |
| 扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g | |
| ulong | lmmp_gcdext_11_ (ulong u, ulong v, slong *s, slong *t) |
| 扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g | |
| mp_size_t | lmmp_gcdext_1_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, ulong v) |
| 扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g | |
| mp_size_t | lmmp_gcdext_2_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp) |
| 扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g | |
| mp_size_t | lmmp_gcdext_hgcd_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) |
| 扩展欧几里得(hgcd 分治,长输入优选):g = gcd(u,v),s*u + t*v = g | |
| mp_size_t | lmmp_gcdext_lehmer_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) |
| 扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g | |
| mp_size_t | lmmp_hgcd_ (lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n) |
| 半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵 | |
| void | lmmp_hgcd_matrix_free_ (lmmp_hgcd_matrix_t *M) |
| 释放 hgcd 变换矩阵的元素缓冲 | |
| void | lmmp_hgcd_matrix_init_ (lmmp_hgcd_matrix_t *M, mp_size_t alloc) |
| 初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲) | |
| mp_size_t | lmmp_hyperfac_ (mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n) |
| 计算hyper阶乘(k^k累乘至n) | |
| mp_size_t | lmmp_hyperfac_size_ (ushort n, mp_bitcnt_t *bits) |
| 计算hyper阶乘的 limb 缓冲区长度 | |
| void | lmmp_invcbrt_newton_ (mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na) |
| 计算逆立方根的定点下近似:记 I=floor(cbrt(B^(3*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,ns+1] <= I,且 dstis[ns]>=1 | |
| void | lmmp_invsqrt_newton_ (mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na) |
| 计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,ns+1] <= I,且 dstis[ns]=1 | |
| int | lmmp_is_prime_2_ (mp_limb_t lo, mp_limb_t hi) |
| 判断 128 位素数 | |
| int | lmmp_is_prime_2_notrial_ (mp_limb_t lo, mp_limb_t hi) |
| 判断 128 位素数(无试除法) | |
| int | lmmp_is_prime_n_ (mp_srcptr np, mp_size_t nn, int strength) |
| 大整数素性检验(强度分档,大于 128 位) | |
| int | lmmp_is_prime_n_notrial_ (mp_srcptr np, mp_size_t nn, int strength) |
| 大整数素性检验(无试除法,强度分档,大于 128 位) | |
| bool | lmmp_is_prime_uint_ (uint n) |
| 判断素数 | |
| bool | lmmp_is_prime_ulong_ (ulong n) |
| 判断素数 | |
| bool | lmmp_is_prime_ulong_notrial_ (ulong n) |
| 判断素数(无试除法,单 limb 档) | |
| int | lmmp_is_prothprime_ (uint k, mp_size_t n) |
| Proth 数 k*2^n+1 的素性判定(普罗斯定理) | |
| int | lmmp_is_strong_lucas_ (mp_srcptr np, mp_size_t nn) |
| 强 Lucas-Selfridge 测试(大于 128 位) | |
| mp_limb_t | lmmp_mod_2p48sub1_ (mp_srcptr p, mp_size_t n) |
| 计算 [p,n] % 2^48-1 | |
| mp_size_t | lmmp_modinv_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t mn) |
| 模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn] | |
| ulong | lmmp_modinv_ulong_ (ulong u, ulong m) |
| 模逆元(单 limb):求 u^{-1} mod m | |
| ulong | lmmp_mulmod_ulong_ (ulong a, ulong b, ulong mod, ulongp q) |
| 计算两个无符号整数的乘积,对mod取模,商放入 q 中 | |
| mp_size_t | lmmp_multinomial_ (mp_ptr dst, mp_size_t rn, uint n, const uintp r, uint m) |
| 计算多项式系数 | |
| mp_size_t | lmmp_multinomial_size_ (const uintp r, uint m, ulong *n) |
| 计算多项式系数的 limb 缓冲区长度 | |
| mp_size_t | lmmp_nCr_ (mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n, uint r) |
| 计算 nCr 组合数 ( nCr = n! | |
| mp_size_t | lmmp_nCr_size_ (uint n, uint r, mp_bitcnt_t *bits) |
| 计算 nCr 组合数的 limb 缓冲区长度 | |
| ulong | lmmp_next_prime_ulong_ (ulong n) |
| 大于n的下一个素数 | |
| mp_size_t | lmmp_nPr_ (mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ulong n, ulong r) |
| 计算 nPr 排列数 ( nPr = n! | |
| mp_size_t | lmmp_nPr_size_ (ulong n, ulong r, mp_bitcnt_t *bits) |
| 计算 nPr 排列数的 limb 缓冲区长度 | |
| void | lmmp_nthroot_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp) |
| 计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb) | |
| mp_size_t | lmmp_nthroot_size_ (mp_size_t na, ulong root) |
| 计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口) | |
| ulong | lmmp_nthroot_ulong_ (ulong n, ulong root) |
| 计算 floor(n^(1/root)) | |
| mp_size_t | lmmp_odd_factorial_uint_ (mp_ptr dst, mp_size_t rn, uint n) |
| 计算 n! | |
| mp_size_t | lmmp_odd_nCr_uint_ (mp_ptr dst, mp_size_t rn, uint n, uint r) |
| 计算 nCr 组合数的奇数部分 | |
| mp_size_t | lmmp_odd_nCr_ushort_ (mp_ptr dst, mp_size_t rn, uint n, uint r) |
| 计算 nCr 组合数的奇数部分 | |
| mp_size_t | lmmp_odd_nPr_uint_ (mp_ptr dst, mp_size_t rn, ulong n, ulong r) |
| 计算 nPr 排列数的奇数部分 | |
| mp_size_t | lmmp_odd_nPr_ulong_ (mp_ptr dst, mp_size_t rn, ulong n, ulong r) |
| 计算 nPr 排列数的奇数部分 | |
| mp_size_t | lmmp_odd_nPr_ushort_ (mp_ptr dst, mp_size_t rn, ulong n, ulong r) |
| 计算 nPr 排列数的奇数部分 | |
| bool | lmmp_perfsqr_ (mp_srcptr p, mp_size_t n) |
| 判断[p,n]是否为完全平方数 | |
| bool | lmmp_perfsqr_filter_ (mp_srcptr p, mp_size_t n) |
| 非完全平方数过滤器 | |
| bool | lmmp_perfsqr_filter_1_ (mp_limb_t p) |
| 非完全平方数过滤器 | |
| mp_size_t | lmmp_pow_ (mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp) |
| 计算大整数幂 [dst,rn] = [base,n] ^ exp | |
| mp_size_t | lmmp_pow_1_ (mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp) |
| 计算幂次方 [dst,rn] = [base,1] ^ exp | |
| mp_size_t | lmmp_pow_1_size_ (mp_limb_t base, ulong exp) |
| 计算幂次方需要的limb缓冲区长度 base ^ exp | |
| mp_size_t | lmmp_pow_basecase_ (mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp) |
| 计算奇数次幂算法 [dst,rn] = [base,n] ^ exp | |
| mp_size_t | lmmp_pow_size_ (mp_srcptr base, mp_size_t n, ulong exp) |
| 计算幂次方需要的limb缓冲区长度 [base,n] ^ exp | |
| mp_size_t | lmmp_pow_win2_ (mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp) |
| 计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp | |
| void | lmmp_powlo_ (mp_ptr dst, mp_srcptr bp, mp_size_t n, mp_srcptr ep, mp_size_t en) |
| 计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n] | |
| void | lmmp_powlo_1_ (mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en) |
| 计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化) | |
| void | lmmp_powlo_2_ (mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en) |
| 计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化) | |
| void | lmmp_powmod_ (mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n) |
| 计算任意模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n] | |
| void | lmmp_powmod_1_ (mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_limb_t mod) |
| 计算奇模数模幂 [dst,1] = [bp,1]^[ep,en] % mod | |
| void | lmmp_powmod_2_ (mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mod) |
| 计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2] | |
| void | lmmp_powmod_odd_ (mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n) |
| 计算奇模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n] | |
| uint | lmmp_powmod_uint_odd_ (uint base, ulong exp, uint mod) |
| 计算 base^exp 对 mod 取模 | |
| ulong | lmmp_powmod_ulong_odd_ (ulong base, ulong exp, ulong mod) |
| 计算 base^exp 对 mod 取模 | |
| ulong | lmmp_prev_prime_ulong_ (ulong n) |
| 小于等于n的上一个素数 | |
| mp_size_t | lmmp_primefac_ (mp_ptr dst, mp_size_t rn, uint n) |
| 计算质数阶乘(不超过n的质数累乘) | |
| mp_size_t | lmmp_primefac_size_ (uint n) |
| 计算质数阶乘的 limb 缓冲区长度 | |
| mp_limb_t | lmmp_redc_ (mp_ptr dst, mp_srcptr tp, mp_srcptr ninv, mp_srcptr mp, mp_size_t n) |
| Montgomery 归约(REDC):计算 ([tp,2n] + q*[mp,n]) / B^n,其中 q = [tp,n] * [ninv,n] mod B^n,即结果为 [tp,2n] * B^(-n) % [mp,n] | |
| mp_size_t | lmmp_remove_ (mp_ptr np, mp_size_t *nn, mp_srcptr dp, mp_size_t dn) |
| 除去 [np,nn] 中的 [dp,dn] 的因子 | |
| void | lmmp_sqrt_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf) |
| 计算 [numa,na] * B^(2*nf) 的平方根和余数 | |
| mp_limb_t | lmmp_sqrt_1_ (mp_ptr dstr, mp_limb_t x) |
| 计算算术平方根 floor(sqrt(x)) | |
| mp_limb_t | lmmp_sqrt_2_ (mp_ptr dstr, mp_srcptr numa) |
| 计算算术平方根 floor(sqrt([numa,2])) | |
| void | lmmp_sqrt_3_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa) |
| 计算算术平方根 floor(sqrt([numa,3])) | |
| void | lmmp_sqrt_4_ (mp_ptr dsts, mp_ptr dstr, mp_srcptr numa) |
| 计算算术平方根 floor(sqrt([numa,4])) | |
| void | lmmp_sqrt_divide_ (mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr) |
| 计算算术平方根 floor(sqrt([numa,2*ns])) | |
| void | lmmp_sqrt_newton_ (mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf) |
| 计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf))) | |
| ulong | lmmp_sqrt_ulong_ (ulong a) |
| 计算算术平方根 floor(sqrt(a)) | |
| mp_size_t | lmmp_superfac_ (mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n) |
| 计算super阶乘(k! | |
| mp_size_t | lmmp_superfac_size_ (ushort n, mp_bitcnt_t *bits) |
| 计算super阶乘的 limb 缓冲区长度 | |
| mp_size_t | lmmp_u16_pow_1_ (mp_ptr dst, mp_size_t rn, ulong base, ulong exp) |
| 计算幂次方 [dst,rn] = [base,1] ^ exp | |
| mp_size_t | lmmp_u32_pow_1_ (mp_ptr dst, mp_size_t rn, ulong base, ulong exp) |
| 计算幂次方 [dst,rn] = [base,1] ^ exp | |
| mp_size_t | lmmp_u4_pow_1_ (mp_ptr dst, mp_size_t rn, ulong base, ulong exp) |
| 计算幂次方 [dst,rn] = [base,1] ^ exp | |
| mp_size_t | lmmp_u64_pow_1_ (mp_ptr dst, mp_size_t rn, ulong base, ulong exp) |
| 计算幂次方 [dst,rn] = [base,1] ^ exp | |
| mp_size_t | lmmp_u8_pow_1_ (mp_ptr dst, mp_size_t rn, ulong base, ulong exp) |
| 计算幂次方 [dst,rn] = [base,1] ^ exp | |
| struct lmmp_hgcd_matrix_t |
hgcd 变换矩阵
| 成员变量 | ||
|---|---|---|
| mp_size_t | alloc | |
| mp_ptr | m[2][2] | |
| mp_size_t | n[2][2] | |
| typedef uint8_t uchar |
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
| mp_size_t lmmp_2factorial_ | ( | mp_ptr | dst, |
| mp_bitcnt_t | bits, | ||
| mp_size_t | rn, | ||
| uint | n ) |
计算 n!
! 双阶乘
| dst | 结果指针 |
| bits | n!! 的2的因子数 |
| rn | 结果指针的 limb 长度 |
| n | 双阶乘的阶数 |
引用了 lmmp_2factorial_(), LMMP_API , 以及 n.
被这些函数引用 lmmp_2factorial_(), lmmp_2factorial_() , 以及 TEST_CASE().
| mp_size_t lmmp_2factorial_size_ | ( | uint | n, |
| mp_bitcnt_t * | bits ) |
计算 n!
! 双阶乘的 limb 缓冲区长度
| n | 双阶乘的阶数 |
| bits | 被修改为 n!! 的2的因子数 |
引用了 lmmp_2factorial_size_(), LMMP_API , 以及 n.
被这些函数引用 lmmp_2factorial_size_(), lmmp_2factorial_size_() , 以及 TEST_CASE().
计算等差数列乘积 x(x+m)...(x+n*m)
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| x | 首项 |
| n | 等差数列共n+1项 |
| m | 公差(大于1) |
引用了 LMMP_API, lmmp_arith_seqprod_() , 以及 n.
被这些函数引用 lmmp_arith_seqprod_(), lmmp_arith_seqprod_() , 以及 TEST_CASE().
计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
Copyright (C) 2026 HJimmyK (Jericho Knox)
| x | 首项 |
| n | 等差数列共n+1项 |
| m | 公差 |
计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
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
在文件 arith_seqprod.c 第 33 行定义.
引用了 LIMB_BITS, lmmp_arith_seqprod_size_(), LMMP_MIN, lmmp_param_assert , 以及 n.
被这些函数引用 lmmp_arith_seqprod_size_(), lmmp_multinomial_() , 以及 TEST_CASE().
计算 [numa,na] 在 B^n 下的逆元
| dst | 结果指针(长度为 n 个limb) |
| numa | 待求逆元指针(长度为 na 个limb) |
| na | 待求逆元的 limb 长度 |
| n | 结果的 limb 长度 |
引用了 LMMP_API, lmmp_binvert_(), lmmp_divexact_1_() , 以及 n.
被这些函数引用 lmmp_binvert_(), lmmp_binvert_(), lmmp_mont_init_(), lmmp_powmod_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算 [numa,2] 在 B^2 下的逆元
| numa | 待求逆元指针(长度为 2 个limb) |
| dst | 结果指针(长度为 2 个limb) |
在文件 binvert_1.c 第 63 行定义.
引用了 _umul64to128_(), a0, a1, k, lmmp_binvert_2_(), lmmp_binvert_ulong_(), lmmp_param_assert, t , 以及 xn.
被这些函数引用 lmmp_binvert_2_(), lmmp_binvert_3_(), lmmp_binvert_4_(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_2_(), lmmp_divexact_(), lmmp_powmod_2_(), mont2_preinv(), TEST_CASE() , 以及 TEST_CASE().
计算 [numa,3] 在 B^3 下的逆元
| numa | 待求逆元指针(长度为 3 个limb) |
| dst | 结果指针(长度为 3 个limb) |
引用了 LMMP_API , 以及 lmmp_binvert_3_().
被这些函数引用 lmmp_binvert_3_(), lmmp_binvert_3_(), lmmp_binvert_n_dc_() , 以及 TEST_CASE().
计算 [numa,4] 在 B^4 下的逆元
| numa | 待求逆元指针(长度为 4 个limb) |
| dst | 结果指针(长度为 4 个limb) |
引用了 LMMP_API , 以及 lmmp_binvert_4_().
被这些函数引用 lmmp_binvert_4_(), lmmp_binvert_4_(), lmmp_binvert_n_dc_() , 以及 TEST_CASE().
计算 [numa,n] 在 B^n 下的逆元
| numa | 待求逆元指针(长度为 n 个limb) |
| dst | 结果指针(长度为 n 个limb) |
| n | 结果的 limb 长度 |
| tp | 临时工作区指针(长度为 5*(n+1)/2 个limb) |
引用了 LMMP_API, lmmp_binvert_n_dc_(), n , 以及 tp.
被这些函数引用 lmmp_binvert_(), lmmp_binvert_n_dc_(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_(), lmmp_divexact_divide_(), lmmp_divexact_unbalance_() , 以及 TEST_CASE().
计算 a 在2^32下的逆元
| a | 待求逆元 |
在文件 binvert_1.c 第 37 行定义.
引用了 binv_tab, lmmp_binvert_uint_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_binvert_uint_() , 以及 TEST_CASE().
计算 a 在2^64下的逆元
| a | 待求逆元 |
在文件 binvert_1.c 第 49 行定义.
引用了 binv_tab, lmmp_binvert_ulong_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_binvert_2_(), lmmp_binvert_n_dc_(), lmmp_binvert_ulong_(), lmmp_binvert_unbalance_1_(), lmmp_divexact_(), lmmp_divexact_basecase_(), lmmp_is_prime_ulong_notrial_(), lmmp_mont_init_(), lmmp_powmod_1_(), lmmp_powmod_ulong_odd_(), TEST_CASE(), TEST_CASE() , 以及 trialdiv_init_chunk_().
计算 [numa,na] 在 B^n 下的逆元
| dst | 结果指针(长度为 n 个limb) |
| numa | 待求逆元指针(长度为 na 个limb) |
| na | 待求逆元的 limb 长度 |
| n | 结果的 limb 长度 |
| tp | 临时工作区指针(长度为 (9*na+5)/2 个limb) |
引用了 LMMP_API, lmmp_binvert_unbalance_(), n , 以及 tp.
被这些函数引用 lmmp_binvert_(), lmmp_binvert_unbalance_(), lmmp_binvert_unbalance_() , 以及 TEST_CASE().
计算 a 在 B^n 下的逆元
| dst | 结果指针(长度为 n 个limb) |
| a | 待求逆元 |
| n | 结果的 limb 长度 |
引用了 LMMP_API, lmmp_binvert_unbalance_1_() , 以及 n.
被这些函数引用 lmmp_binvert_(), lmmp_binvert_unbalance_1_(), lmmp_binvert_unbalance_1_() , 以及 TEST_CASE().
计算 [numa,2] 在 B^n 下的逆元
| dst | 结果指针(长度为 n 个limb) |
| numa | 待求逆元指针(长度为 2 个limb) |
| n | 结果的 limb 长度 |
引用了 LMMP_API, lmmp_binvert_unbalance_2_() , 以及 n.
被这些函数引用 lmmp_binvert_(), lmmp_binvert_unbalance_2_(), lmmp_binvert_unbalance_2_() , 以及 TEST_CASE().
计算 [numa,na] * B^(3*nf) 的立方根和余数
| dsts | 立方根结果输出指针(缓冲区长度至少 nf+na/3+3 个limb) |
| dstr | 余数结果输出指针(缓冲区长度至少 2*(nf+na/3)+3 个limb,NULL 表示不计算余数) |
| numa | 源操作数指针(长度为 na 个limb) |
| na | 操作数的 limb 长度 |
| nf | 精度因子 |
引用了 a2, CBRT_INVNEWTON_K_THRESHOLD, CBRT_INVNEWTON_NF_MIN, k, LIMB_BITS, lmmp_add_(), lmmp_add_1_(), lmmp_addmul_1_(), lmmp_cbrt_(), lmmp_cbrt_3_(), lmmp_cbrt_6_(), lmmp_cbrt_divide_(), lmmp_cbrt_knorm_(), lmmp_cbrt_newton_(), lmmp_cbrt_snorm_(), lmmp_cbrt_ulong_(), lmmp_copy, lmmp_cube_3_(), lmmp_cube_6_(), lmmp_debug_assert, lmmp_div_1_(), lmmp_mul_(), lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_shr_(), lmmp_sqr_, lmmp_sqr_hard_2_(), lmmp_sub_1_(), lmmp_sub_n_(), lmmp_submul_1_(), lmmp_zero, rp, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.
被这些函数引用 lmmp_cbrt_(), lmmp_invcbrt_newton_(), TEST_CASE() , 以及 TEST_CASE().
计算算数立方根 floor(cbrt(a0+a1*B+a2*B^2))
| a0 | 低位 limb |
| a1 | 中位 limb |
| a2 | 高位 limb |
引用了 a0, a1, a2, exp2_fixed_64(), LIMB_BITS, LIMB_MAX, lmmp_cbrt_3_(), lmmp_cmp_(), lmmp_cube_3_(), lmmp_debug_assert, lmmp_div3_(), lmmp_inc, lmmp_limb_bits_, lmmp_param_assert, log2_fixed_64() , 以及 t.
被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_3_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_invsqrt_newton_() , 以及 TEST_CASE().
计算算术立方根 floor(cbrt([numa,na]))
| dst | 结果指针(2个limb) |
| numa | 被开方数指针 |
| na | 被开方数的 limb 长度 |
引用了 CBRT_DIVIDE_MIN, lmmp_cbrt_6_(), lmmp_cbrt_6_est_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_6_fix_(), lmmp_param_assert, t , 以及 tp.
被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_6_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_() , 以及 TEST_CASE().
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))
| dst | 结果指针(2个limb) |
| numa | 被开方数指针(6个limb,会被修改;返回时 [numa,5] 储存余数,即[numa,6] - [dst,2]^3) |
| tp | 临时指针(至少8个limb) |
引用了 LMMP_API, lmmp_cbrt_6_fast_() , 以及 tp.
被这些函数引用 lmmp_cbrt_6_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_() , 以及 TEST_CASE().
计算算数立方根 floor(cbrt(n))
| n | 被开方数 |
在文件 cbrt_ulong.c 第 47 行定义.
引用了 coeff, factor_table, lmmp_cbrt_chebyshev_(), lmmp_param_assert , 以及 n.
被这些函数引用 lmmp_cbrt_chebyshev_(), lmmp_cbrt_ulong_(), lmmp_invsqrt_newton_() , 以及 TEST_CASE().
计算算术立方根 floor(cbrt([numa,3*ns]))
| dst | 结果指针(ns个limb) |
| numa | 被开方数指针(3*ns个limb,且会被修改,若计算余数,余数存储在[numa,2*ns+1]中) |
| ns | 结果指针的 limb 长度 |
| tp | 临时指针(6*ns+4个limb) |
| calr | 是否计算余数(0表示不计算余数,1表示计算余数) |
引用了 LMMP_API, lmmp_cbrt_divide_() , 以及 tp.
被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_divide_(), lmmp_cbrt_divide_() , 以及 TEST_CASE().
计算近似立方根 [dsts,na/3+nf+1]=[floor|round](cbrt([numa,na]*B^(3*nf))), 输入须已归一化:na ≡ 0 (mod 3) 且顶 limb >= B/8
| dsts | 目标数组(长度至少 na/3+nf+1 个limb) |
| numa | 输入数组(长度为 na 个limb,已 3 对齐归一化) |
| na | numa数组的 limb 长度(3 的倍数) |
| nf | 精度因子 |
引用了 LIMB_B_8, LIMB_BITS, lmmp_cbrt_newton_(), lmmp_copy, lmmp_inc, lmmp_invcbrt_newton_(), lmmp_mul_(), lmmp_param_assert, lmmp_sqr_, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.
被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_newton_() , 以及 lmmp_invcbrt_newton_().
计算算数立方根 floor(cbrt(n))
| n | 被开方数 |
在文件 cbrt_ulong.c 第 139 行定义.
引用了 lmmp_cbrt_chebyshev_(), lmmp_cbrt_estimate(), lmmp_cbrt_ulong_() , 以及 n.
被这些函数引用 lmmp_cbrt_(), lmmp_cbrt_ulong_(), lmmp_invsqrt_newton_(), lmmp_nthroot_ulong_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
| dst | 结果指针(长度为 nn-dn+1 个limb) |
| np | 被除数指针(长度为 nn 个limb) |
| nn | 被除数的 limb 长度 |
| dp | 除数指针(长度为 dn 个limb) |
| dn | 结除数的 limb 长度 |
引用了 LMMP_API, lmmp_divexact_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_22_(), lmmp_gcd_2_() , 以及 lmmp_gcd_lehmer_().
被这些函数引用 bench_divexact(), lmmp_divexact_(), lmmp_divexact_(), lmmp_gcdext_derive_(), lmmp_odd_nCr_div_(), make_divexact_ctx(), TEST_CASE() , 以及 TEST_CASE().
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
Copyright (C) 2026 HJimmyK (Jericho Knox)
| dst | 结果指针(长度为 nn 个limb) |
| np | 被除数指针(长度为 nn 个limb) |
| nn | 被除数的 limb 长度 |
| d | 除数 |
| dinv | 除数的逆元(d*dinv==1 mod 2^64) |
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
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
在文件 divexact.c 第 32 行定义.
引用了 _umul64to128_(), lmmp_debug_assert, lmmp_divexact_1_(), lmmp_param_assert, lo , 以及 s.
被这些函数引用 lmmp_binvert_(), lmmp_divexact_(), lmmp_divexact_1_(), lmmp_divexact_basecase_() , 以及 TEST_CASE().
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
| dst | 结果指针(长度为 nn-1 个limb) |
| np | 被除数指针(长度为 nn 个limb) |
| nn | 被除数的 limb 长度 |
| dp | 除数指针(长度为 2 个limb) |
| dinv | 除数的逆元指针(长度为 2 个limb) |
引用了 LMMP_API , 以及 lmmp_divexact_2_().
被这些函数引用 lmmp_divexact_(), lmmp_divexact_2_(), lmmp_divexact_2_() , 以及 TEST_CASE().
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
| dst | 结果指针(长度为 nn-dn+1 个limb) |
| np | 被除数指针(长度为 nn 个limb),将会被覆写为全零 |
| nn | 被除数的 limb 长度 |
| dp | 除数指针(长度为 dn 个limb) |
| dn | 除数的 limb 长度 |
引用了 LMMP_API , 以及 lmmp_divexact_basecase_().
被这些函数引用 lmmp_divexact_(), lmmp_divexact_basecase_(), lmmp_divexact_basecase_() , 以及 TEST_CASE().
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
| dst | 结果指针(长度为 nn-dn+1 个limb) |
| np | 被除数指针(长度为 nn 个limb) |
| nn | 被除数的 limb 长度 |
| dp | 除数指针(长度为 dn 个limb) |
| dn | 结除数的 limb 长度 |
引用了 LMMP_API , 以及 lmmp_divexact_divide_().
被这些函数引用 lmmp_divexact_(), lmmp_divexact_divide_(), lmmp_divexact_divide_() , 以及 TEST_CASE().
| void lmmp_divexact_unbalance_ | ( | mp_ptr | dst, |
| mp_srcptr | np, | ||
| mp_size_t | nn, | ||
| mp_srcptr | dp, | ||
| mp_size_t | dn, | ||
| mp_ptr | dinv ) |
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
| dst | 结果指针(长度为 nn-dn+1 个limb) |
| np | 被除数指针(长度为 nn 个limb),将会被修改为全零 |
| nn | 被除数的 limb 长度 |
| dp | 除数指针(长度为 dn 个limb) |
| dn | 结除数的 limb 长度 |
| dinv | 除数[dp,dn]关于B^dn的逆元,若为NULL,则自动计算 |
引用了 LMMP_API , 以及 lmmp_divexact_unbalance_().
被这些函数引用 lmmp_divexact_(), lmmp_divexact_unbalance_(), lmmp_divexact_unbalance_(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_factorial_ | ( | mp_ptr | dst, |
| mp_bitcnt_t | bits, | ||
| mp_size_t | rn, | ||
| uint | n ) |
计算 n!
阶乘
| dst | 结果指针 |
| bits | n! 的2的因子数 |
| rn | 结果指针的 limb 长度 |
| n | 阶乘的阶数 |
引用了 LMMP_API, lmmp_factorial_() , 以及 n.
被这些函数引用 bench_factorial(), lmmp_factorial_(), lmmp_factorial_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), test_fn_heap_balance_full_cycle(), test_fn_lifecycle_idempotent() , 以及 thread_worker().
| mp_size_t lmmp_factorial_size_ | ( | uint | n, |
| mp_bitcnt_t * | bits ) |
计算 n!
阶乘的 limb 缓冲区长度
| n | 阶乘的阶数 |
| bits | 被修改为 n! 的2的因子数 |
引用了 LMMP_API, lmmp_factorial_size_() , 以及 n.
被这些函数引用 bench_factorial(), lmmp_factorial_size_(), lmmp_factorial_size_(), lmmp_odd_nCr_uint_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), test_fn_heap_balance_full_cycle(), test_fn_lifecycle_idempotent(), test_fn_thread_isolation() , 以及 thread_worker().
计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
| dst | F[n] 结果指针 |
| dst2 | F[n-1] 结果指针 |
| rn | dst 与 dst2 各自的 limb 缓冲区长度 |
| n | Fibonacci 数列的下标 |
在文件 fibonacci.c 第 193 行定义.
引用了 fib2_core_(), fib_table, FIB_TABLE_LIMIT, lmmp_fibonacci2_(), lmmp_fibonacci_size_(), lmmp_param_assert, n, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.
被这些函数引用 fib_pair(), lmmp_fibonacci2_(), lmmp_pow_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算 Fibonacci 数 [dst,rn] = F[n]
| dst | 结果指针 |
| rn | dst 的 limb 缓冲区长度 |
| n | Fibonacci 数列的下标 |
在文件 fibonacci.c 第 211 行定义.
引用了 fib2_core_(), fib_limbs_bound_(), fib_table, FIB_TABLE_LIMIT, lmmp_add_1_(), lmmp_add_n_(), lmmp_addshl1_n_(), lmmp_debug_assert, lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_mul_(), lmmp_param_assert, lmmp_shl_(), lmmp_sub_1_(), lmmp_sub_n_(), n, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, tp , 以及 xp.
被这些函数引用 bench_fib(), lmmp_fibonacci_(), lmmp_pow_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
| n | Fibonacci 数列的下标 |
在文件 fibonacci.c 第 122 行定义.
引用了 fib_limbs_bound_(), FIB_TABLE_LIMIT, lmmp_fibonacci_size_() , 以及 n.
被这些函数引用 bench_fib(), fib_pair(), lmmp_fibonacci2_(), lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_pow_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数(通用分发入口)
Copyright (C) 2026 HJimmyK (Jericho Knox)
| dst | 结果指针(长度至少为 min(un,vn)) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
计算两个无符号整数的最大公约数(通用分发入口)
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
引用了 GCD_HGCD_THRESHOLD, lmmp_gcd_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_22_(), lmmp_gcd_2_(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_param_assert , 以及 LMMP_SWAP.
被这些函数引用 lmmp_gcd_(), small_factor_q(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数
Copyright (C) 2026 HJimmyK (Jericho Knox)
| u | 第一个无符号整数 |
| v | 第二个无符号整数 |
计算两个无符号整数的最大公约数
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
引用了 k, lmmp_gcd_11_(), lmmp_param_assert, lmmp_tailing_zeros_ , 以及 t.
被这些函数引用 lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_22_(), lmmp_gcd_lehmer_() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| v | 第二个无符号整数 |
引用了 lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_mod_1_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_1_(), lmmp_gcd_lehmer_(), TEST_CASE() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数
| up | 第一个无符号整数指针,长度为 2 |
| vp | 第二个无符号整数指针,长度为 2 |
| dst | 结果指针(长度为 2,两个 limb 都会进行写入,即使最高位可能为0) |
引用了 ctz_u128(), lmmp_gcd_11_(), lmmp_gcd_22_(), lmmp_param_assert, lmmp_tailing_zeros_, lshl_u128(), lshr_u128(), t, v0, v1 , 以及 w0.
被这些函数引用 lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_22_(), lmmp_gcd_2_(), TEST_CASE() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针,长度为 2 |
| dst | 结果指针(长度至少为 2,两个 limb 都会进行写入,即使最高位可能为0) |
引用了 lmmp_gcd_22_(), lmmp_gcd_2_(), lmmp_mod_2_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_2_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
| dst | 结果指针(长度至少为 bn) |
| up | 第一个无符号整数数组(长度为 un 个limb) |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数数组(长度为 vn 个limb) |
| vn | 第二个无符号整数的 limb 长度 |
引用了 ALLOC_TYPE, an, bn, HGCD_RECURSE_THRESHOLD, lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), lmmp_gcd_norm_(), lmmp_hgcd_core_(), lmmp_hgcd_matrix_init_buf_(), lmmp_hgcd_scratch_size_(), lmmp_param_assert, LMMP_SWAP, lmmp_zero, lmmp_zero_q_() , 以及 rp.
被这些函数引用 bench_gcd_hgcd(), lmmp_gcd_(), lmmp_gcd_hgcd_(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算两个无符号整数的最大公约数(Lehmer算法)
| dst | 结果指针(长度至少为 min(un,vn)) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
在文件 gcd_lehmer.c 第 159 行定义.
引用了 an, BALLOC_TYPE, bn, lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_gcd_11_(), lmmp_gcd_1_(), lmmp_gcd_lehmer_(), lmmp_gcd_lehmer_extract_(), lmmp_gcd_lehmer_step_(), lmmp_lehmer_mul_(), lmmp_param_assert, LMMP_SWAP, lmmp_gcd_lehmer_t::m21, lehmer_stack_t::mp, lehmer_stack_t::np, TEMP_B_DECL, TEMP_B_FREE , 以及 lehmer_stack_t::tp.
被这些函数引用 bench_gcd_lehmer(), lmmp_divexact_(), lmmp_gcd_(), lmmp_gcd_hgcd_(), lmmp_gcd_lehmer_(), run_gcdext_pair(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_gcdext_ | ( | mp_ptr | dstg, |
| mp_ptr | dsts, | ||
| mp_ssize_t * | sn, | ||
| mp_ptr | dstt, | ||
| mp_ssize_t * | tn, | ||
| mp_srcptr | up, | ||
| mp_size_t | un, | ||
| mp_srcptr | vp, | ||
| mp_size_t | vn ) |
扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g
| dstg | 结果指针(长度至少为 min(un,vn)) |
| dsts | u 的贝祖系数幅度(长度至少为 vn 个limb) |
| sn | 输出 s 的带符号 limb 长度 |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
引用了 GCD_HGCD_THRESHOLD, lmmp_gcdext_(), lmmp_gcdext_1_(), lmmp_gcdext_2_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_gcdext_(), lmmp_modinv_(), run_gcdext_pair(), TEST_CASE() , 以及 TEST_CASE().
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
Copyright (C) 2026 HJimmyK (Jericho Knox)
| u | 第一个无符号整数 |
| v | 第二个无符号整数 |
| s | 输出 u 的贝祖系数(带符号) |
| t | 输出 v 的贝祖系数(带符号,可为 NULL 表示不需要) |
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
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
在文件 gcdext_1.c 第 48 行定义.
引用了 lmmp_gcdext_11_(), lmmp_param_assert, LMMP_SWAP, r0, r1, r2, s , 以及 t.
被这些函数引用 lmmp_gcdext_11_(), lmmp_gcdext_1_(), lmmp_modinv_ulong_() , 以及 TEST_CASE().
| mp_size_t lmmp_gcdext_1_ | ( | mp_ptr | dstg, |
| mp_ptr | dsts, | ||
| mp_ssize_t * | sn, | ||
| mp_ptr | dstt, | ||
| mp_ssize_t * | tn, | ||
| mp_srcptr | up, | ||
| mp_size_t | un, | ||
| ulong | v ) |
扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g
| dstg | 结果指针(长度为 1 个limb) |
| dsts | u 的贝祖系数幅度(长度为 1 个limb,s==0 时写 0) |
| sn | 输出 s 的带符号 limb 长度([1|-1|0]) |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL 表示不需要) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略,可为 NULL) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| v | 第二个无符号整数(单 limb) |
在文件 gcdext_1.c 第 95 行定义.
引用了 BALLOC_TYPE, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcdext_11_(), lmmp_gcdext_1_(), lmmp_mod_1_(), lmmp_mul_1_(), lmmp_param_assert, lmmp_sub_(), TEMP_B_DECL, TEMP_B_FREE , 以及 xn.
被这些函数引用 lmmp_gcdext_(), lmmp_gcdext_1_(), lmmp_gcdext_lehmer_() , 以及 TEST_CASE().
| mp_size_t lmmp_gcdext_2_ | ( | mp_ptr | dstg, |
| mp_ptr | dsts, | ||
| mp_ssize_t * | sn, | ||
| mp_ptr | dstt, | ||
| mp_ssize_t * | tn, | ||
| mp_srcptr | up, | ||
| mp_size_t | un, | ||
| mp_srcptr | vp ) |
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
Copyright (C) 2026 HJimmyK (Jericho Knox)
| dstg | 结果指针(长度至少为 2 个limb) |
| dsts | u 的贝祖系数幅度(长度至少为 2 个limb,s==0 时写 0) |
| sn | 输出 s 的带符号 limb 长度 |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针(长度为 2) |
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
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
在文件 gcdext_2.c 第 40 行定义.
引用了 BALLOC_TYPE, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcdext_2_(), lmmp_gcdext_lehmer_(), lmmp_mod_2_(), lmmp_mul_(), lmmp_param_assert, lmmp_sub_(), TEMP_B_DECL, TEMP_B_FREE , 以及 xn.
被这些函数引用 lmmp_gcdext_(), lmmp_gcdext_2_() , 以及 TEST_CASE().
| mp_size_t lmmp_gcdext_hgcd_ | ( | mp_ptr | dstg, |
| mp_ptr | dsts, | ||
| mp_ssize_t * | sn, | ||
| mp_ptr | dstt, | ||
| mp_ssize_t * | tn, | ||
| mp_srcptr | up, | ||
| mp_size_t | un, | ||
| mp_srcptr | vp, | ||
| mp_size_t | vn ) |
扩展欧几里得(hgcd 分治,长输入优选):g = gcd(u,v),s*u + t*v = g
| dstg | 结果指针(长度至少为 min(un,vn)) |
| dsts | u 的贝祖系数幅度(长度至少为 vn 个limb,s==0 时写 0) |
| sn | 输出 s 的带符号 limb 长度([1|-1|0]) |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
引用了 ALLOC_TYPE, gcdext_pick_s_(), gcdext_row_mul_(), gcdext_row_qscalar_(), HGCD_RECURSE_THRESHOLD, lmmp_add_(), lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_gcd_matrix_init_buf_(), lmmp_gcd_matrix_maxlen_(), lmmp_gcd_matrix_swap_cols_(), lmmp_gcd_mul_(), lmmp_gcd_norm_(), lmmp_gcdext_emit_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_(), lmmp_gcdext_smag_(), lmmp_hgcd_adjust_(), lmmp_hgcd_core_(), lmmp_hgcd_salloc_(), lmmp_hgcd_scratch_size_(), lmmp_mul_1_(), lmmp_param_assert, lmmp_sub_(), LMMP_SWAP, lmmp_zero, M1, n , 以及 r0.
被这些函数引用 lmmp_gcdext_() , 以及 lmmp_gcdext_hgcd_().
| mp_size_t lmmp_gcdext_lehmer_ | ( | mp_ptr | dstg, |
| mp_ptr | dsts, | ||
| mp_ssize_t * | sn, | ||
| mp_ptr | dstt, | ||
| mp_ssize_t * | tn, | ||
| mp_srcptr | up, | ||
| mp_size_t | un, | ||
| mp_srcptr | vp, | ||
| mp_size_t | vn ) |
扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g
| dstg | 结果指针(长度至少为 min(un,vn)) |
| dsts | u 的贝祖系数幅度(长度至少为 vn 个limb,s==0 时写 0) |
| sn | 输出 s 的带符号 limb 长度([1|-1|0]) |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL 表示不需要) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略,可为 NULL) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
在文件 gcdext_lehmer.c 第 209 行定义.
引用了 an, BALLOC_TYPE, bn, lc1_(), lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcd_lehmer_extract_(), lmmp_gcd_lehmer_step_(), lmmp_gcdext_1_(), lmmp_gcdext_emit_(), lmmp_gcdext_lehmer_(), lmmp_gcdext_smag_(), lmmp_mul_(), lmmp_mul_1_(), lmmp_param_assert, lmmp_sub_(), LMMP_SWAP, lmmp_gcd_lehmer_t::m11, lmmp_gcd_lehmer_t::m12, lmmp_gcd_lehmer_t::m21, lmmp_gcd_lehmer_t::m22, mag_cmp_(), sco_t::n, sco_t::neg, sco_t::p, pool_free2_(), TEMP_B_DECL , 以及 TEMP_B_FREE.
被这些函数引用 lmmp_gcdext_(), lmmp_gcdext_2_(), lmmp_gcdext_hgcd_() , 以及 lmmp_gcdext_lehmer_().
| mp_size_t lmmp_hgcd_ | ( | lmmp_hgcd_matrix_t * | M, |
| mp_ptr | ap, | ||
| mp_ptr | bp, | ||
| mp_size_t | n ) |
半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
| M | 变换矩阵(入口应为单位矩阵,出口满足 (a;b) = M*(a';b')) |
| ap | 较大分量输入兼输出数组(长度为 n 个limb,出口保证较大者位于 ap) |
| bp | 较小分量输入兼输出数组(长度为 n 个limb,允许高位零填充) |
| n | ap,bp 的公共长度 |
引用了 lmmp_hgcd_matrix_t::alloc, ALLOC_TYPE, lmmp_cmp_(), lmmp_debug_assert, lmmp_free(), lmmp_hgcd_(), lmmp_hgcd_core_(), lmmp_hgcd_scratch_size_(), lmmp_param_assert , 以及 n.
被这些函数引用 lmmp_hgcd_() , 以及 TEST_CASE().
| void lmmp_hgcd_matrix_free_ | ( | lmmp_hgcd_matrix_t * | M | ) |
释放 hgcd 变换矩阵的元素缓冲
| M | 变换矩阵 |
引用了 lmmp_hgcd_matrix_t::alloc, lmmp_free(), lmmp_hgcd_matrix_free_(), lmmp_param_assert, lmmp_hgcd_matrix_t::m , 以及 lmmp_hgcd_matrix_t::n.
被这些函数引用 lmmp_hgcd_matrix_free_() , 以及 TEST_CASE().
| void lmmp_hgcd_matrix_init_ | ( | lmmp_hgcd_matrix_t * | M, |
| mp_size_t | alloc ) |
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
| M | 变换矩阵 |
| alloc | 每元素容量(limb)。若随后用于 n limb 数对的 hgcd,需 alloc >= n+2 |
引用了 ALLOC_TYPE, lmmp_hgcd_matrix_init_(), lmmp_hgcd_matrix_init_buf_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_hgcd_matrix_init_() , 以及 TEST_CASE().
| mp_size_t lmmp_hyperfac_ | ( | mp_ptr | dst, |
| mp_bitcnt_t | bits, | ||
| mp_size_t | rn, | ||
| ushort | n ) |
计算hyper阶乘(k^k累乘至n)
| dst | 结果指针 |
| bits | hyper阶乘的2的因子数 |
| rn | 结果指针的 limb 长度 |
| n | hyper阶乘的阶数 |
引用了 LMMP_API, lmmp_hyperfac_() , 以及 n.
被这些函数引用 lmmp_hyperfac_(), lmmp_hyperfac_() , 以及 TEST_CASE().
| mp_size_t lmmp_hyperfac_size_ | ( | ushort | n, |
| mp_bitcnt_t * | bits ) |
计算hyper阶乘的 limb 缓冲区长度
| n | hyper阶乘的阶数 |
| bits | 被修改为 hyper阶乘的2的因子数 |
引用了 LMMP_API, lmmp_hyperfac_size_() , 以及 n.
被这些函数引用 lmmp_hyperfac_size_(), lmmp_hyperfac_size_() , 以及 TEST_CASE().
计算逆立方根的定点下近似:记 I=floor(cbrt(B^(3*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,ns+1] <= I,且 dstis[ns]>=1
| dstis | 目标数组(长度为 ns+1 个limb) |
| ns | dstis数组的 limb 长度为 ns+1 |
| numa | 输入数组 |
| na | numa数组的 limb 长度 |
引用了 LMMP_API, lmmp_cbrt_(), lmmp_cbrt_newton_(), lmmp_invcbrt_newton_(), lmmp_mod_2p48sub1_(), lmmp_nthroot_(), lmmp_nthroot_size_(), lmmp_nthroot_ulong_(), lmmp_perfsqr_(), lmmp_perfsqr_filter_(), lmmp_perfsqr_filter_1_(), n , 以及 tp.
被这些函数引用 lmmp_cbrt_newton_(), lmmp_invcbrt_newton_(), lmmp_invcbrt_newton_() , 以及 TEST_CASE().
计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,ns+1] <= I,且 dstis[ns]=1
| dstis | 目标数组 |
| ns | dstis数组的 limb 长度为 ns+1 |
| numa | 输入数组 |
| na | numa数组的 limb 长度 |
引用了 a0, a1, a2, LMMP_API, lmmp_cbrt_3_(), lmmp_cbrt_6_(), lmmp_cbrt_chebyshev_(), lmmp_cbrt_ulong_(), lmmp_invsqrt_newton_(), lmmp_sqrt_(), lmmp_sqrt_newton_() , 以及 n.
被这些函数引用 lmmp_invsqrt_newton_(), lmmp_invsqrt_newton_(), lmmp_sqrt_newton_() , 以及 TEST_CASE().
判断 128 位素数
| lo | 待判断数的低 64 位 |
| hi | 待判断数的高 64 位 |
在文件 is_prime_2.c 第 739 行定义.
引用了 _umul128to128_(), abound0, abound1, ainv0, ainv1, bbound0, bbound1, binv0, binv1, FAST_TRIAL_BOUND, is2_notrial_i_(), ll_le(), lmmp_is_prime_2_(), lmmp_param_assert , 以及 lo.
被这些函数引用 bench_is_prime_2(), check_prime_2_agreement(), ipn_proth_i_(), lmmp_is_prime_2_(), lmmp_is_prothprime_(), lmmp_powmod_(), pool_2() , 以及 TEST_CASE().
判断 128 位素数(无试除法)
| lo | 待判断数的低 64 位 |
| hi | 待判断数的高 64 位 |
在文件 is_prime_2.c 第 733 行定义.
引用了 is2_notrial_i_(), lmmp_is_prime_2_notrial_(), lmmp_param_assert , 以及 lo.
被这些函数引用 bench_is_prime_2_notrial(), check_prime_2_agreement(), lmmp_is_prime_2_notrial_() , 以及 lmmp_powmod_().
大整数素性检验(强度分档,大于 128 位)
| np | 待测数指针(nn 个limb) |
| nn | 待测数的 limb 长度 |
| strength | 检测强度 [0,7],语义同 lmmp_is_prime_n_notrial_,强度越高理论误判率越低。 强度>=4时,已是接受集为标准 BPSW 素性(学界目前无已知反例)接受集的子集。 |
在文件 is_prime_n.c 第 646 行定义.
引用了 ipn_notrial_i_(), ipn_trial_bound, lmmp_is_prime_n_(), lmmp_param_assert , 以及 lmmp_trialdiv_().
被这些函数引用 bench_is_prime_n(), bench_is_prime_n_proth(), ipn_proth_i_(), lmmp_is_prime_n_(), lmmp_powmod_(), pool_n(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
大整数素性检验(无试除法,强度分档,大于 128 位)
| np | 待测数指针(nn 个limb) | |||||||||||||||||||||||||||||||||||||||||||||
| nn | 待测数的 limb 长度 | |||||||||||||||||||||||||||||||||||||||||||||
| strength | 检测强度 [0,7]。随机基底 MR 分两层:"1+n" 搭配指先跑至多 x 轮 1 limb 随机基底(a in [3,B) 均匀,廉价,可尽早拒判)再跑至多 y 轮 全域(n limb 随机基底,[2,n-2] 均匀)基底。各层均为“至多”轮数,任一轮检出 合数即提前终止:
|
在文件 is_prime_n.c 第 659 行定义.
引用了 ipn_notrial_i_(), lmmp_is_prime_n_notrial_() , 以及 lmmp_param_assert.
被这些函数引用 bench_is_prime_n_notrial(), lmmp_is_prime_n_notrial_(), lmmp_powmod_() , 以及 TEST_CASE().
| bool lmmp_is_prime_uint_ | ( | uint | n | ) |
判断素数
| n | 待判断的数 |
在文件 is_prime_uint.c 第 124 行定义.
引用了 lmmp_is_prime_table_(), lmmp_is_prime_uint_(), lmmp_is_prime_uint_notrial_(), n , 以及 trial_div35711().
被这些函数引用 lmmp_is_prime_uint_(), lmmp_powmod_(), TEST_CASE() , 以及 TEST_CASE().
| bool lmmp_is_prime_ulong_ | ( | ulong | n | ) |
判断素数
| n | 待判断的数 |
在文件 is_prime_ulong.c 第 345 行定义.
引用了 lmmp_is_prime_table_(), lmmp_is_prime_ulong_(), lmmp_is_prime_ulong_notrial_(), MP_UINT_MAX, n , 以及 trial_div35711().
被这些函数引用 bench_is_prime_ulong(), lmmp_is_prime_ulong_(), lmmp_is_prothprime_(), lmmp_powmod_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
| bool lmmp_is_prime_ulong_notrial_ | ( | ulong | n | ) |
判断素数(无试除法,单 limb 档)
| n | 待判断的数(建议为极有可能为素数的数) |
在文件 is_prime_ulong.c 第 257 行定义.
引用了 bm1, ctz_shr_u64, dj_base49, dj_base64, lmmp_binvert_ulong_(), lmmp_is_prime_uint_notrial_(), lmmp_is_prime_ulong_notrial_(), lmmp_limb_bits_, LMMP_NOINLINE, lmmp_param_assert, MONT63_MAX, mont63_R2(), mont64_R2(), MP_UINT_MAX, n, powmod2_63(), powmod2_64(), powmod2_win3_63(), powmod2_win3_64(), powmod_win3_63(), sprp_check63(), sprp_check64(), t, to_mont63(), to_mont64(), v1 , 以及 v2.
被这些函数引用 bench_is_prime_ulong_notrial(), lmmp_is_prime_ulong_(), lmmp_is_prime_ulong_notrial_(), lmmp_next_prime_ulong_(), lmmp_powmod_(), lmmp_prev_prime_ulong_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
Proth 数 k*2^n+1 的素性判定(普罗斯定理)
| k | 系数(k < 2^32) |
| n | 指数(2 的幂次) |
在文件 is_prime_n.c 第 768 行定义.
引用了 ipn_proth_i_(), k, LIMB_BITS, lmmp_is_prime_2_(), lmmp_is_prime_ulong_(), lmmp_is_prothprime_(), lmmp_limb_bits_, lmmp_param_assert, lmmp_zero, n, s, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.
被这些函数引用 bench_is_prothprime(), lmmp_is_prothprime_(), lmmp_powmod_(), pool_proth(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
强 Lucas-Selfridge 测试(大于 128 位)
| np | 待测奇数指针(nn 个limb) |
| nn | 待测数的 limb 长度 |
在文件 is_prime_n.c 第 506 行定义.
引用了 ipn_lucas_i_(), ipn_sdiv_init_(), lmmp_is_strong_lucas_(), lmmp_param_assert, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.
被这些函数引用 bench_is_strong_lucas(), lmmp_is_strong_lucas_(), lmmp_powmod_() , 以及 TEST_CASE().
计算 [p,n] % 2^48-1
| p | 被除数指针 |
| n | 被除数的 limb 长度 |
引用了 a0, a1, a2, ADD, B3, c0, c1, lmmp_mod_2p48sub1_(), lmmp_param_assert, MASK48, n, PARTS0, PARTS1 , 以及 PARTS2.
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_mod_2p48sub1_() , 以及 lmmp_perfsqr_filter_().
模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
| dst | 结果指针(长度至少为 mn 个limb) |
| up | 被求逆元数指针 |
| un | 被求逆元数的 limb 长度 |
| mp | 模数指针 |
| mn | 模数的 limb 长度 |
引用了 BALLOC_TYPE, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcdext_(), lmmp_mod_1_(), lmmp_modinv_(), lmmp_modinv_ulong_(), lmmp_param_assert, lmmp_sub_(), s, TEMP_B_DECL , 以及 TEMP_B_FREE.
被这些函数引用 lmmp_modinv_() , 以及 TEST_CASE().
模逆元(单 limb):求 u^{-1} mod m
| u | 被求逆元数 |
| m | 模数 |
引用了 lmmp_gcdext_11_(), lmmp_modinv_ulong_(), lmmp_param_assert , 以及 s.
被这些函数引用 lmmp_modinv_(), lmmp_modinv_ulong_() , 以及 TEST_CASE().
计算两个无符号整数的乘积,对mod取模,商放入 q 中
| a | 第一个无符号整数 |
| b | 第二个无符号整数 |
| q | 商的结果指针 |
| mod | 取模数 |
引用了 LMMP_API, lmmp_mulmod_ulong_(), lmmp_powmod_uint_odd_() , 以及 lmmp_powmod_ulong_odd_().
被这些函数引用 lmmp_mulmod_ulong_(), lmmp_mulmod_ulong_(), TEST_CASE() , 以及 TEST_CASE().
计算多项式系数
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| n | r[i] 的总和 |
| r | 需要计算的系数的数组 |
| m | 系数的个数 |
引用了 LMMP_API, lmmp_arith_seqprod_size_(), lmmp_multinomial_() , 以及 n.
被这些函数引用 lmmp_multinomial_(), lmmp_multinomial_() , 以及 TEST_CASE().
计算多项式系数的 limb 缓冲区长度
| r | 需要计算的系数的数组 |
| m | 系数的个数 |
| n | 输出变量,将会被修改为 r[i] 的总和,即r1+r2+...+rm |
引用了 LMMP_API, lmmp_multinomial_size_() , 以及 n.
被这些函数引用 lmmp_multinomial_size_(), lmmp_multinomial_size_() , 以及 TEST_CASE().
计算 nCr 组合数 ( nCr = n!
/ (r!(n-r)!) )
| dst | 结果指针 |
| bits | nCr 的2的因子数 |
| rn | 结果指针的 limb 长度 |
| n | 组合数的总数 |
| r | 组合数的选择数 |
引用了 LMMP_API, lmmp_nCr_() , 以及 n.
被这些函数引用 lmmp_nCr_(), lmmp_nCr_(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_nCr_size_ | ( | uint | n, |
| uint | r, | ||
| mp_bitcnt_t * | bits ) |
计算 nCr 组合数的 limb 缓冲区长度
| n | 组合数的总数 |
| r | 组合数的选择数 |
| bits | 被修改为 nCr 的2的因子数 |
引用了 LMMP_API, lmmp_nCr_size_() , 以及 n.
被这些函数引用 lmmp_nCr_size_(), lmmp_nCr_size_(), TEST_CASE() , 以及 TEST_CASE().
大于n的下一个素数
| n | 起始点(不含) |
在文件 is_prime_ulong.c 第 375 行定义.
引用了 lmmp_is_prime_ulong_notrial_(), lmmp_next_prime_ulong_(), lmmp_prime_cnt16_(), MP_ULONG_MAX, n, prime_short_table, PRIME_SHORT_TABLE_SIZE, trial_div16() , 以及 ULONG_PRIME_MAX.
被这些函数引用 lmmp_next_prime_ulong_(), lmmp_powmod_(), pool_bits(), TEST_CASE() , 以及 TEST_CASE().
计算 nPr 排列数 ( nPr = n!
/ (n-r)! )
| dst | 结果指针 |
| bits | nPr 的2的因子数 |
| rn | 结果指针的 limb 长度 |
| n | 排列数的总数 |
| r | 排列数的选择数 |
引用了 LMMP_API, lmmp_nPr_() , 以及 n.
被这些函数引用 lmmp_nPr_(), lmmp_nPr_(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_nPr_size_ | ( | ulong | n, |
| ulong | r, | ||
| mp_bitcnt_t * | bits ) |
计算 nPr 排列数的 limb 缓冲区长度
| n | 排列数的总数 |
| r | 排列数的选择数 |
| bits | 被修改为 nPr 的2的因子数 |
引用了 LMMP_API, lmmp_nPr_size_() , 以及 n.
被这些函数引用 lmmp_nPr_size_(), lmmp_nPr_size_(), lmmp_odd_nCr_uint_(), pow_nPr_(), TEST_CASE() , 以及 TEST_CASE().
| void lmmp_nthroot_ | ( | mp_ptr | dsts, |
| mp_ptr | dstr, | ||
| mp_srcptr | numa, | ||
| mp_size_t | na, | ||
| ulong | root, | ||
| mp_ptr | tp ) |
计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
| dsts | 结果指针(nr = ceil(na/root) 个 limb,顶 limb 恒非零) |
| dstr | 余数结果输出指针((root-1)*nr+1 个 limb,NULL 表示不计算余数) |
| numa | 被开方数指针(只读) |
| na | 被开方数的 limb 长度 |
| root | 开方次数 |
| tp | 临时区(至少 lmmp_nthroot_size_(na,root) 个 limb) |
引用了 a1, B, b2, bp1, c1, exp2_fixed_128(), LIMB_BITS, lmmp_add_(), lmmp_add_1_(), lmmp_copy, lmmp_debug_assert, lmmp_dec, lmmp_div_(), lmmp_div_1_(), lmmp_limb_bits_, lmmp_mul_(), lmmp_mul_1_(), lmmp_nthroot_(), lmmp_nthroot_ulong_(), lmmp_param_assert, lmmp_pow_(), lmmp_shl_(), lmmp_shr64_(), lmmp_shr_(), lmmp_sqr_, lmmp_sqrt_(), lmmp_sub_(), lmmp_zero, log2_fixed_128(), nthroot_add_small_(), nthroot_cmp_ext_(), nthroot_dec_len_(), nthroot_inc_len_(), nthroot_pow_trunc_(), nthroot_sub_small_(), nthroot_top_limbs_(), r1, s, tp , 以及 xn.
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_nthroot_(), TEST_CASE() , 以及 TEST_CASE().
计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
| na | 被开方数的 limb 长度 |
| root | 开方次数 |
引用了 lmmp_nthroot_size_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_nthroot_size_(), TEST_CASE() , 以及 TEST_CASE().
计算 floor(n^(1/root))
| n | 被开方数 |
| root | 开方次数 |
在文件 nthroot_ulong.c 第 51 行定义.
引用了 inv_table, LIMB_BITS, lmmp_cbrt_ulong_(), lmmp_debug_assert, lmmp_nthroot_ulong_(), lmmp_sqrt_ulong_(), max_base, n , 以及 pow_n().
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_nthroot_(), lmmp_nthroot_ulong_(), TEST_CASE() , 以及 TEST_CASE().
计算 n!
阶乘的奇数部分
| dst | 结果指针 |
| rn | 结果指针的 limb 长度(factorial_size_ 函数的返回值 - bits/LIMB_BITS) |
| n | 阶乘的阶数 |
引用了 LMMP_API, lmmp_odd_factorial_uint_() , 以及 n.
被这些函数引用 lmmp_2factorial_(), lmmp_factorial_(), lmmp_odd_factorial_(), lmmp_odd_factorial_uint_() , 以及 lmmp_odd_factorial_uint_().
计算 nCr 组合数的奇数部分
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| n | 组合数的总数 |
| r | 组合数的选择数 |
引用了 LMMP_API, lmmp_odd_nCr_uint_() , 以及 n.
被这些函数引用 lmmp_nCr_(), lmmp_odd_nCr_uint_() , 以及 lmmp_odd_nCr_uint_().
计算 nCr 组合数的奇数部分
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| n | 组合数的总数 |
| r | 组合数的选择数 |
引用了 LMMP_API, lmmp_odd_nCr_ushort_() , 以及 n.
被这些函数引用 lmmp_nCr_(), lmmp_odd_nCr_ushort_() , 以及 lmmp_odd_nCr_ushort_().
计算 nPr 排列数的奇数部分
| dst | 结果指针 |
| rn | 结果指针的 limb 长度(nPr_size_ 函数的返回值 - bits/LIMB_BITS) |
| n | 排列数的总数 |
| r | 排列数的选择数 |
引用了 LMMP_API, lmmp_odd_nPr_uint_() , 以及 n.
被这些函数引用 _odd_nPr_(), lmmp_nPr_(), lmmp_odd_nPr_uint_() , 以及 lmmp_odd_nPr_uint_().
计算 nPr 排列数的奇数部分
| dst | 结果指针 |
| rn | 结果指针的 limb 长度(nPr_size_ 函数的返回值 - bits/LIMB_BITS) |
| n | 排列数的总数 |
| r | 排列数的选择数 |
引用了 LMMP_API, lmmp_odd_nPr_ulong_() , 以及 n.
被这些函数引用 lmmp_nPr_(), lmmp_odd_nPr_ulong_() , 以及 lmmp_odd_nPr_ulong_().
计算 nPr 排列数的奇数部分
| dst | 结果指针 |
| rn | 结果指针的 limb 长度(nPr_size_ 函数的返回值 - bits/LIMB_BITS) |
| n | 排列数的总数 |
| r | 排列数的选择数 |
引用了 LMMP_API, lmmp_odd_nPr_ushort_() , 以及 n.
被这些函数引用 _odd_nPr_(), lmmp_2factorial_(), lmmp_factorial_(), lmmp_nPr_(), lmmp_odd_factorial_(), lmmp_odd_multinomial_ushort_(), lmmp_odd_nCr_ushort_(), lmmp_odd_nPr_ushort_() , 以及 lmmp_odd_nPr_ushort_().
判断[p,n]是否为完全平方数
| p | 输入指针 |
| n | 输入的 limb 长度 |
引用了 lmmp_param_assert, lmmp_perfsqr_(), lmmp_perfsqr_filter_(), lmmp_sqrt_(), lmmp_zero_q_(), n, restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.
被这些函数引用 ipn_lucas_i_(), lmmp_invcbrt_newton_(), lmmp_perfsqr_() , 以及 TEST_CASE().
非完全平方数过滤器
| p | 输入指针 |
| n | 输入的 limb 长度 |
引用了 is_perfsqr_p13(), is_perfsqr_p17(), is_perfsqr_p241(), is_perfsqr_p256(), is_perfsqr_p257(), is_perfsqr_p5(), is_perfsqr_p673(), is_perfsqr_p7(), is_perfsqr_p9(), is_perfsqr_p97(), lmmp_mod_2p48sub1_(), lmmp_param_assert, lmmp_perfsqr_filter_(), lmmp_perfsqr_filter_1_() , 以及 n.
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_perfsqr_(), lmmp_perfsqr_filter_() , 以及 TEST_CASE().
| bool lmmp_perfsqr_filter_1_ | ( | mp_limb_t | p | ) |
非完全平方数过滤器
| p | 输入数 |
引用了 is_perfsqr_p13(), is_perfsqr_p17(), is_perfsqr_p241(), is_perfsqr_p256(), is_perfsqr_p257(), is_perfsqr_p5(), is_perfsqr_p673(), is_perfsqr_p7(), is_perfsqr_p9(), is_perfsqr_p97(), lmmp_param_assert, lmmp_perfsqr_filter_1_() , 以及 MASK48.
被这些函数引用 lmmp_invcbrt_newton_(), lmmp_perfsqr_filter_(), lmmp_perfsqr_filter_1_() , 以及 TEST_CASE().
计算大整数幂 [dst,rn] = [base,n] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数指针 |
| n | 底数指针的 limb 长度 |
| exp | 指数 |
引用了 LMMP_API, lmmp_fibonacci2_(), lmmp_fibonacci_(), lmmp_fibonacci_size_(), lmmp_pow_() , 以及 n.
被这些函数引用 check_floor(), lmmp_nthroot_(), lmmp_pow_(), lmmp_pow_(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算幂次方 [dst,rn] = [base,1] ^ exp
| dst | 结果指针 |
| base | 底数 |
| exp | 指数 |
引用了 LMMP_API , 以及 lmmp_pow_1_().
被这些函数引用 check_pow1_agree(), check_pow1_laws(), lmmp_pow_(), lmmp_pow_1_(), lmmp_pow_1_(), TEST_CASE() , 以及 TEST_CASE().
计算幂次方需要的limb缓冲区长度 base ^ exp
| base | 底数 |
| exp | 指数 |
引用了 floor1_u64(), LIMB_BITS, lmmp_limb_bits_, lmmp_param_assert, lmmp_pow_1_size_(), MP_SIZE_MAX , 以及 ulong_upper_d().
被这些函数引用 check_pow1_agree(), check_pow1_laws(), lmmp_nCr_size_(), lmmp_nPr_size_(), lmmp_pow_1_size_(), lmmp_pow_size_(), lmmp_powmod_() , 以及 pow_nPr_().
计算奇数次幂算法 [dst,rn] = [base,n] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 缓冲区长度 |
| base | 底数指针 |
| n | 底数指针的 limb 长度 |
| exp | 指数 |
引用了 LMMP_API, lmmp_pow_basecase_() , 以及 n.
被这些函数引用 lmmp_pow_(), lmmp_pow_basecase_(), lmmp_pow_basecase_() , 以及 TEST_CASE().
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
| base | 底数指针 |
| n | 底数 limb 长度 |
| exp | 指数 |
引用了 floor1_u64(), LIMB_BITS, lmmp_limb_bits_, lmmp_param_assert, lmmp_pow_1_size_(), lmmp_pow_size_(), MP_SIZE_MAX, n, t , 以及 ulong_upper_d().
被这些函数引用 lmmp_pow_(), lmmp_pow_size_(), lmmp_powmod_(), TEST_CASE() , 以及 TEST_CASE().
计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数指针 |
| n | 底数指针的 limb 长度 |
| exp | 指数 |
引用了 LMMP_API, lmmp_pow_win2_() , 以及 n.
被这些函数引用 lmmp_pow_(), lmmp_pow_win2_(), lmmp_pow_win2_() , 以及 TEST_CASE().
计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
| dst | 结果指针(长度为 n 个limb) |
| bp | 底数指针 |
| n | 底数的 limb 长度 |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
引用了 LMMP_API, lmmp_powlo_() , 以及 n.
被这些函数引用 bench_powlo(), lmmp_powlo_(), lmmp_powlo_(), lmmp_powmod_() , 以及 TEST_CASE().
计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)
| dst | 结果指针(长度为 1 个limb) |
| bp | 底数指针(长度为 1 个limb) |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
引用了 LMMP_API , 以及 lmmp_powlo_1_().
被这些函数引用 lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_1_() , 以及 TEST_CASE().
计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
| dst | 结果指针(长度为 2 个limb) |
| bp | 底数指针(长度为 2 个limb) |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
引用了 LMMP_API , 以及 lmmp_powlo_2_().
被这些函数引用 lmmp_powlo_(), lmmp_powlo_2_(), lmmp_powlo_2_() , 以及 TEST_CASE().
| void lmmp_powmod_ | ( | mp_ptr | dst, |
| mp_srcptr | bp, | ||
| mp_srcptr | ep, | ||
| mp_size_t | en, | ||
| mp_srcptr | mp, | ||
| mp_size_t | n ) |
计算任意模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
| dst | 结果指针(长度为 n 个limb,规范剩余 < [mp,n],高位可能为 0) |
| bp | 底数指针(长度为 n 个limb) |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
| mp | 模数指针(长度为 n 个limb,奇偶皆可) |
| n | 模数的 limb 长度 |
引用了 k, LMMP_API, lmmp_is_prime_2_(), lmmp_is_prime_2_notrial_(), lmmp_is_prime_n_(), lmmp_is_prime_n_notrial_(), lmmp_is_prime_uint_(), lmmp_is_prime_ulong_(), lmmp_is_prime_ulong_notrial_(), lmmp_is_prothprime_(), lmmp_is_strong_lucas_(), lmmp_next_prime_ulong_(), lmmp_pow_1_size_(), lmmp_pow_size_(), lmmp_powmod_(), lmmp_prev_prime_ulong_(), lo , 以及 n.
被这些函数引用 bench_powmod_even(), lmmp_powmod_(), lmmp_powmod_(), proth_cert_g(), proth_certified(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算奇模数模幂 [dst,1] = [bp,1]^[ep,en] % mod
| dst | 结果指针(长度为 1 个limb) |
| bp | 底数指针(长度为 1 个limb) |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
| mod | 模数 |
引用了 LMMP_API , 以及 lmmp_powmod_1_().
被这些函数引用 lmmp_powmod_1_(), lmmp_powmod_1_(), lmmp_powmod_odd_() , 以及 TEST_CASE().
计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2]
| dst | 结果指针(长度为 2 个limb) |
| bp | 底数指针(长度为 2 个limb) |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
| mod | 模数指针(长度为 2 个limb) |
引用了 LMMP_API , 以及 lmmp_powmod_2_().
被这些函数引用 lmmp_powmod_2_(), lmmp_powmod_2_(), lmmp_powmod_odd_() , 以及 TEST_CASE().
| void lmmp_powmod_odd_ | ( | mp_ptr | dst, |
| mp_srcptr | bp, | ||
| mp_srcptr | ep, | ||
| mp_size_t | en, | ||
| mp_srcptr | mp, | ||
| mp_size_t | n ) |
计算奇模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
| dst | 结果指针(长度为 n 个limb,规范剩余 < [mp,n],高位可能为 0) |
| bp | 底数指针(长度为 n 个limb) |
| ep | 指数指针 |
| en | 指数的 limb 长度 |
| mp | 模数指针(长度为 n 个limb) |
| n | 模数的 limb 长度 |
引用了 LMMP_API, lmmp_powmod_odd_() , 以及 n.
被这些函数引用 bench_powmod_odd(), lmmp_powmod_(), lmmp_powmod_odd_(), lmmp_powmod_odd_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算 base^exp 对 mod 取模
| base | 底数 |
| exp | 指数 |
| mod | 模数 |
在文件 powmod_ulong.c 第 94 行定义.
引用了 _udiv64_gen(), _udiv64by64_q_preinv(), lmmp_param_assert , 以及 lmmp_powmod_uint_odd_().
被这些函数引用 lmmp_mulmod_ulong_(), lmmp_powmod_uint_odd_(), lmmp_powmod_ulong_odd_() , 以及 TEST_CASE().
计算 base^exp 对 mod 取模
| base | 底数 |
| exp | 指数 |
| mod | 模数 |
在文件 powmod_ulong.c 第 118 行定义.
引用了 from_mont63(), from_mont64(), lmmp_binvert_ulong_(), lmmp_param_assert, lmmp_powmod_uint_odd_(), lmmp_powmod_ulong_odd_(), MONT63_MAX, mont63_mul(), mont63_R2(), mont64_mul(), mont64_R2(), MP_UINT_MAX, to_mont63() , 以及 to_mont64().
被这些函数引用 lmmp_mulmod_ulong_(), lmmp_powmod_ulong_odd_() , 以及 TEST_CASE().
小于等于n的上一个素数
| n | 起始点(含) |
在文件 is_prime_ulong.c 第 397 行定义.
引用了 lmmp_is_prime_ulong_notrial_(), lmmp_prev_prime_ulong_(), lmmp_prime_cnt16_(), n, prime_short_table, PRIME_SHORT_TABLE_N, trial_div16() , 以及 ULONG_PRIME_MIN.
被这些函数引用 lmmp_powmod_(), lmmp_prev_prime_ulong_() , 以及 TEST_CASE().
计算质数阶乘(不超过n的质数累乘)
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| n | 质数阶乘的阶数 |
引用了 LMMP_API, lmmp_primefac_() , 以及 n.
被这些函数引用 lmmp_primefac_(), lmmp_primefac_(), small_factor_q() , 以及 TEST_CASE().
计算质数阶乘的 limb 缓冲区长度
| n | 质数阶乘的阶数 |
在文件 factorial_extra.c 第 446 行定义.
引用了 LIMB_BITS, lmmp_primefac_size_() , 以及 n.
被这些函数引用 lmmp_primefac_size_(), lmmp_superfac_(), small_factor_q() , 以及 TEST_CASE().
Montgomery 归约(REDC):计算 ([tp,2n] + q*[mp,n]) / B^n,其中 q = [tp,n] * [ninv,n] mod B^n,即结果为 [tp,2n] * B^(-n) % [mp,n]
| dst | 结果指针(长度为 n 个limb) |
| tp | 被归约数指针(长度为 2n 个limb) |
| ninv | -[mp,n]^(-1) mod B^n(长度为 n 个limb) |
| mp | 模数指针(长度为 n 个limb) |
| n | 模数的 limb 长度 |
引用了 LMMP_API, lmmp_redc_(), n , 以及 tp.
被这些函数引用 lmmp_redc_(), lmmp_redc_() , 以及 TEST_CASE().
除去 [np,nn] 中的 [dp,dn] 的因子
| np | 被除数指针,将会被修改为除去因子后的数 |
| nn | 被除数指针的 limb 长度,将会被修改除去因子后的长度 |
| dp | 除数指针 |
| dn | 除数指针的 limb 长度 |
引用了 LMMP_API, lmmp_remove_(), lmmp_sqrt_1_(), lmmp_sqrt_2_(), lmmp_sqrt_3_(), lmmp_sqrt_4_() , 以及 lmmp_sqrt_ulong_().
被这些函数引用 lmmp_remove_(), lmmp_remove_() , 以及 TEST_CASE().
计算 [numa,na] * B^(2*nf) 的平方根和余数
| dsts | 平方根结果输出指针(长度为 nf+na/2+1 个limb) |
| dstr | 余数结果输出指针(NULL表示不计算余数) |
| numa | 源操作数指针(长度为 na 个limb) |
| na | 操作数的 limb 长度 |
| nf | 精度因子 |
引用了 LIMB_BITS, lmmp_addmul_1_(), lmmp_copy, lmmp_debug_assert, lmmp_leading_zeros_, lmmp_shl_(), lmmp_shr_(), lmmp_sqrt_(), lmmp_sqrt_1_(), lmmp_sqrt_2_(), lmmp_sqrt_3_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_(), lmmp_sqrt_newton_(), lmmp_sub_1_(), lmmp_submul_1_(), lmmp_zero, restrict, s, SQRT_INVNEWTON_K_THRESHOLD, t, TALLOC_TYPE, TEMP_DECL, TEMP_FREE, tmp , 以及 tp.
被这些函数引用 bench_sqrt(), lmmp_invsqrt_newton_(), lmmp_nthroot_(), lmmp_perfsqr_(), lmmp_sqrt_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().
计算算术平方根 floor(sqrt(x))
| dstr | 余数指针(1个limb) |
| x | 被开方数 |
引用了 LIMB_B_4, lmmp_param_assert, lmmp_sqrt_1_(), lmmp_sqrt_ulong_() , 以及 s.
被这些函数引用 lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_1_(), lmmp_sqrt_2_() , 以及 TEST_CASE().
计算算术平方根 floor(sqrt([numa,2]))
| dstr | 余数指针(2个limb) |
| numa | 被开方数指针 |
引用了 LIMB_B_4, lmmp_param_assert, lmmp_sqrt_1_(), lmmp_sqrt_2_() , 以及 s.
被这些函数引用 is_square_2(), lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_2_(), lmmp_sqrt_3_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_() , 以及 TEST_CASE().
计算算术平方根 floor(sqrt([numa,3]))
| dsts | 结果指针(2个limb) |
| dstr | 余数指针(3个limb,最高位补零),传 NULL 表示不计算余数 |
| numa | 被开方数指针 |
引用了 _add_ssaaaa, _sub_ddmmss, _udiv128by64to64_(), a0, LIMB_B_4, LIMB_BITS, lmmp_mullh_, lmmp_param_assert, lmmp_sqrt_2_(), lmmp_sqrt_3_(), r0 , 以及 r1.
被这些函数引用 lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_3_() , 以及 TEST_CASE().
计算算术平方根 floor(sqrt([numa,4]))
| dsts | 结果指针(2个limb) |
| dstr | 余数指针(3个limb),传 NULL 表示不计算余数 |
| numa | 被开方数指针 |
引用了 _add_ssaaaa, _sub_ddmmss, _udiv128by64to64_(), LIMB_B_4, LIMB_BITS, lmmp_mullh_, lmmp_param_assert, lmmp_sqrt_2_(), lmmp_sqrt_4_(), r0, r1, r2 , 以及 t.
被这些函数引用 lmmp_remove_(), lmmp_sqrt_(), lmmp_sqrt_4_(), lmmp_sqrt_divide_() , 以及 TEST_CASE().
计算算术平方根 floor(sqrt([numa,2*ns]))
| dst | 结果指针(ns个limb) |
| numa | 被开方数指针(2*ns个limb,且会被修改,若计算余数,余数存储在[numa,ns+1]中) |
| ns | 结果指针的 limb 长度 |
| tp | 临时指针(3*ns/2+1个limb) |
| calr | 是否计算余数(0表示不计算余数,1表示计算余数) |
引用了 LMMP_API, lmmp_sqrt_divide_() , 以及 tp.
被这些函数引用 lmmp_invsqrt_newton_(), lmmp_sqrt_(), lmmp_sqrt_divide_(), lmmp_sqrt_divide_() , 以及 TEST_CASE().
计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))
| dsts | 目标数组(长度为 nf+na/2+1 个limb) |
| numa | 输入数组(长度为 na 个limb) |
| na | numa数组的 limb 长度 |
| nf | 精度因子 |
引用了 LIMB_BITS, lmmp_copy, lmmp_inc, lmmp_invsqrt_newton_(), lmmp_leading_zeros_, lmmp_mul_(), lmmp_param_assert, lmmp_shl_(), lmmp_shr_(), lmmp_sqrt_newton_(), restrict, TALLOC_TYPE, TEMP_DECL, TEMP_FREE , 以及 tp.
被这些函数引用 lmmp_invsqrt_newton_(), lmmp_sqrt_(), lmmp_sqrt_newton_() , 以及 TEST_CASE().
计算算术平方根 floor(sqrt(a))
Copyright (C) 2026 HJimmyK (Jericho Knox)
| a | 被开方数 |
计算算术平方根 floor(sqrt(a))
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
引用了 lmmp_sqrt_ulong_().
被这些函数引用 lmmp_nthroot_ulong_(), lmmp_remove_(), lmmp_sqrt_1_(), lmmp_sqrt_ulong_(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_superfac_ | ( | mp_ptr | dst, |
| mp_bitcnt_t | bits, | ||
| mp_size_t | rn, | ||
| ushort | n ) |
计算super阶乘(k!
累乘至n)
| dst | 结果指针 |
| bits | super阶乘的2的因子数 |
| rn | 结果指针的 limb 长度 |
| n | super阶乘的阶数 |
引用了 LMMP_API, lmmp_primefac_size_(), lmmp_superfac_() , 以及 n.
被这些函数引用 lmmp_superfac_(), lmmp_superfac_() , 以及 TEST_CASE().
| mp_size_t lmmp_superfac_size_ | ( | ushort | n, |
| mp_bitcnt_t * | bits ) |
计算super阶乘的 limb 缓冲区长度
| n | super阶乘的阶数 |
| bits | 被修改为 super阶乘的2的因子数 |
引用了 LMMP_API, lmmp_superfac_size_() , 以及 n.
被这些函数引用 lmmp_superfac_size_(), lmmp_superfac_size_() , 以及 TEST_CASE().
计算幂次方 [dst,rn] = [base,1] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数(16位无符号整数) |
| exp | 指数 |
引用了 LMMP_API , 以及 lmmp_u16_pow_1_().
被这些函数引用 _odd_pow_(), lmmp_pow_1_(), lmmp_u16_pow_1_(), lmmp_u16_pow_1_() , 以及 TEST_CASE().
计算幂次方 [dst,rn] = [base,1] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数(32位无符号整数) |
| exp | 指数 |
引用了 LMMP_API , 以及 lmmp_u32_pow_1_().
被这些函数引用 _odd_pow_(), lmmp_pow_1_(), lmmp_u32_pow_1_(), lmmp_u32_pow_1_() , 以及 TEST_CASE().
计算幂次方 [dst,rn] = [base,1] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数(4位无符号整数) |
| exp | 指数 |
引用了 LMMP_API , 以及 lmmp_u4_pow_1_().
被这些函数引用 _odd_pow_(), lmmp_pow_1_(), lmmp_u4_pow_1_(), lmmp_u4_pow_1_() , 以及 TEST_CASE().
计算幂次方 [dst,rn] = [base,1] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数(64位无符号整数) |
| exp | 指数 |
引用了 LMMP_API , 以及 lmmp_u64_pow_1_().
被这些函数引用 lmmp_pow_1_(), lmmp_u64_pow_1_(), lmmp_u64_pow_1_() , 以及 TEST_CASE().
计算幂次方 [dst,rn] = [base,1] ^ exp
| dst | 结果指针 |
| rn | 结果指针的 limb 长度 |
| base | 底数(8位无符号整数) |
| exp | 指数 |
引用了 LMMP_API , 以及 lmmp_u8_pow_1_().
被这些函数引用 _odd_pow_(), lmmp_pow_1_(), lmmp_u8_pow_1_(), lmmp_u8_pow_1_() , 以及 TEST_CASE().