|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "impl/tmp_alloc.h"#include "impl/inlines.h"#include "impl/longlong.h"#include "numth/powmod.h"#include "impl/rand_state.h"#include "impl/trialdiv.h"#include "lmmp/lmmpn.h"#include "lmmp/mprand.h"#include "lmmp/numth.h"结构体 | |
| struct | ipn_sdiv_t |
宏定义 | |
| #define | IPN_PROTH_WITNESS_MAX 65535u |
变量 | |
| static const uchar | ipn_r1_rounds [8] = {3, 4, 5, 6, 0, 2, 3, 4} |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| static const uchar | ipn_rn_rounds [8] = {2, 3, 4, 5, 0, 0, 1, 2} |
| static const ushort | ipn_trial_bound [8] = {100, 300, 1000, 3000, 1000, 3000, 5000, 10000} |
| struct ipn_sdiv_t |
在文件 is_prime_n.c 第 179 行定义.
| 成员变量 | ||
|---|---|---|
| mp_limb_t | d0 | |
| mp_limb_t | d1 | |
| mp_limb_t | dinv | |
| mp_srcptr | n | |
| mp_size_t | nn | |
| mp_bitcnt_t | sh | |
| #define IPN_PROTH_WITNESS_MAX 65535u |
在文件 is_prime_n.c 第 703 行定义.
被这些函数引用 ipn_proth_i_().
|
inlinestatic |
在文件 is_prime_n.c 第 115 行定义.
引用了 ipn_ctz_(), LIMB_BITS , 以及 lmmp_tailing_zeros_.
被这些函数引用 ipn_ctz_(), ipn_lucas_i_() , 以及 ipn_notrial_i_().
在文件 is_prime_n.c 第 358 行定义.
引用了 A, ipn_jacobi_D_(), ipn_jacobi_small_(), lmmp_mod_1_() , 以及 LMMP_NOINLINE.
被这些函数引用 ipn_jacobi_D_(), ipn_lucas_i_() , 以及 ipn_proth_i_().
在文件 is_prime_n.c 第 333 行定义.
引用了 A, ipn_jacobi_small_(), lmmp_tailing_zeros_ , 以及 s.
被这些函数引用 ipn_jacobi_D_() , 以及 ipn_jacobi_small_().
|
static |
在文件 is_prime_n.c 第 381 行定义.
引用了 ipn_ctz_(), ipn_jacobi_D_(), ipn_lucas_i_(), ipn_mont_add_(), ipn_mont_dbl_(), ipn_mont_half_(), ipn_mont_mul_small_(), ipn_mont_neg_(), ipn_mont_sub_(), ipn_norm_(), LIMB_BITS, lmmp_cmp_(), lmmp_copy, lmmp_inc, lmmp_limb_bits_, lmmp_mont_redc_(), lmmp_perfsqr_(), lmmp_shr_(), lmmp_sqr_, lmmp_zero_q_(), prod, restrict, s, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.
被这些函数引用 ipn_lucas_i_(), ipn_notrial_i_() , 以及 lmmp_is_strong_lucas_().
|
inlinestatic |
在文件 is_prime_n.c 第 96 行定义.
引用了 ipn_mont_add_(), lmmp_add_n_(), lmmp_cmp_(), lmmp_sub_n_() , 以及 restrict.
被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_add_().
|
inlinestatic |
在文件 is_prime_n.c 第 74 行定义.
引用了 ipn_mont_dbl_(), lmmp_add_n_(), lmmp_cmp_(), lmmp_sub_n_() , 以及 restrict.
被这些函数引用 ipn_lucas_i_(), ipn_mont_dbl_(), ipn_mont_mul_small_() , 以及 ipn_sprp_base2_().
|
inlinestatic |
在文件 is_prime_n.c 第 107 行定义.
引用了 ipn_mont_half_(), LIMB_BITS, lmmp_add_n_(), lmmp_shr_(), n , 以及 restrict.
被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_half_().
|
static |
在文件 is_prime_n.c 第 252 行定义.
引用了 ipn_mont_dbl_(), ipn_mont_mul_small_(), ipn_mont_neg_(), ipn_sdiv_mul1_(), lmmp_copy, lmmp_zero, lmmp_zero_q_(), lmmp_mont_t::n , 以及 restrict.
被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_mul_small_().
|
inlinestatic |
在文件 is_prime_n.c 第 90 行定义.
引用了 ipn_mont_neg_(), lmmp_sub_n_() , 以及 restrict.
被这些函数引用 ipn_lucas_i_(), ipn_mont_mul_small_() , 以及 ipn_mont_neg_().
|
inlinestatic |
在文件 is_prime_n.c 第 83 行定义.
引用了 ipn_mont_sub_(), lmmp_add_n_(), lmmp_sub_n_() , 以及 restrict.
被这些函数引用 ipn_lucas_i_() , 以及 ipn_mont_sub_().
在文件 is_prime_n.c 第 121 行定义.
引用了 ipn_norm_().
被这些函数引用 ipn_lucas_i_(), ipn_norm_() , 以及 ipn_notrial_i_().
在文件 is_prime_n.c 第 524 行定义.
引用了 b2, bn, ipn_ctz_(), ipn_lucas_i_(), ipn_norm_(), ipn_notrial_i_(), ipn_r1_rounds, ipn_rn_rounds, ipn_sdiv_init_(), ipn_sprp_1_(), ipn_sprp_base2_(), LIMB_BITS, lmmp_cmp_(), lmmp_copy, lmmp_dec, lmmp_limb_bits_, lmmp_mont_redc_(), LMMP_NOINLINE, lmmp_powmod_odd_mont_(), lmmp_randlimb_(), lmmp_random_(), lmmp_shr_(), lmmp_sqr_, lmmp_zero_q_(), lmmp_mont_t::m1, lmmp_mont_t::one, prod, restrict, t, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.
被这些函数引用 ipn_notrial_i_(), lmmp_is_prime_n_() , 以及 lmmp_is_prime_n_notrial_().
|
static |
在文件 is_prime_n.c 第 705 行定义.
引用了 ipn_jacobi_D_(), ipn_proth_i_(), IPN_PROTH_WITNESS_MAX, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_is_prime_2_(), lmmp_is_prime_n_(), lmmp_limb_bits_, lmmp_mul_n_, lmmp_sqr_, lmmp_sub_n_(), lmmp_zero, prod, restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.
被这些函数引用 ipn_proth_i_() , 以及 lmmp_is_prothprime_().
|
static |
短除上下文初始化:归一化除数顶 2 limb 与其 2/1 逆元
| sd | 上下文 |
| np | 模数(nn 个limb) |
| nn | 模数 limb 长度 |
在文件 is_prime_n.c 第 195 行定义.
引用了 ipn_sdiv_t::d0, ipn_sdiv_t::d1, ipn_sdiv_t::dinv, ipn_sdiv_init_(), LIMB_BITS, lmmp_inv_2_1_(), lmmp_leading_zeros_, ipn_sdiv_t::n, ipn_sdiv_t::nn , 以及 ipn_sdiv_t::sh.
被这些函数引用 ipn_notrial_i_(), ipn_sdiv_init_() , 以及 lmmp_is_strong_lucas_().
|
inlinestatic |
蒙域内乘裸 1 limb 标量:x <- x*a mod n(结果仍是蒙域剩余)
| x | 蒙域剩余(nn 个limb,原地读写) |
| a | 裸标量(a < B) |
| sd | 短除上下文 |
在文件 is_prime_n.c 第 218 行定义.
引用了 _udiv_qr_3by2, ipn_sdiv_t::d0, ipn_sdiv_t::d1, ipn_sdiv_t::dinv, ipn_sdiv_mul1_(), LIMB_BITS, LIMB_MAX, lmmp_add_n_(), lmmp_mul_1_(), lmmp_submul_1_(), ipn_sdiv_t::n, ipn_sdiv_t::nn, r0, r1 , 以及 ipn_sdiv_t::sh.
被这些函数引用 ipn_mont_mul_small_(), ipn_sdiv_mul1_() , 以及 ipn_sprp_1_().
|
static |
短基底 MR 单轮:基底为 1 limb 裸标量,梯子与探测全程蒙域
| mc | 蒙域上下文(含 one/m1,已完成 lmmp_mont_init_) |
| sd | 短除上下文(ipn_sdiv_init_ 就绪,模数同 mc) |
| a | 基底(1 个limb,a < B) |
| d | (n-1)>>t(奇) |
| dbits | d 的位长 |
| t | v2(n-1) |
| u | 梯子累加器兼探测载体(mc->n 个limb) |
| prod | 工作区(2*mc->n 个limb,平方全积,出口被破坏) |
在文件 is_prime_n.c 第 289 行定义.
引用了 ipn_sdiv_mul1_(), ipn_sprp_1_(), LIMB_BITS, lmmp_cmp_(), lmmp_copy, lmmp_mont_redc_(), lmmp_sqr_, prod, restrict , 以及 t.
被这些函数引用 ipn_notrial_i_() , 以及 ipn_sprp_1_().
|
static |
单轮 Rabin-Miller 强伪素数测试(大于 128 位,基底硬编码为 2)
| mc | 蒙域上下文(含 one/m1,已完成 lmmp_mont_init_) |
| d | (n-1)>>t(奇,探测梯子的指数窗口) |
| dbits | d 的位长 |
| t | v2(n-1) |
| u | 梯子累加器兼探测载体(mc->n 个limb) |
| prod | 工作区(2*mc->n 个limb,平方全积,出口被破坏) |
在文件 is_prime_n.c 第 142 行定义.
引用了 ipn_mont_dbl_(), ipn_sprp_base2_(), LIMB_BITS, lmmp_cmp_(), lmmp_mont_redc_(), lmmp_sqr_, prod, restrict , 以及 t.
被这些函数引用 ipn_notrial_i_() , 以及 ipn_sprp_base2_().
大整数素性检验(强度分档,大于 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().
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().
|
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
在文件 is_prime_n.c 第 60 行定义.
被这些函数引用 ipn_notrial_i_().
|
static |
在文件 is_prime_n.c 第 63 行定义.
被这些函数引用 ipn_notrial_i_().
|
static |
在文件 is_prime_n.c 第 70 行定义.
被这些函数引用 lmmp_is_prime_n_().