LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
trialdiv.h 文件参考
#include "lmmp/numth.h"
#include "lmmp/lmmpn.h"
trialdiv.h 的引用(Include)关系图:
此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

函数

mp_limb_t lmmp_mod_4chunk_1_ (mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
 4 链折叠取模:r = [numa,na] mod d
mp_limb_t lmmp_mod_8chunk_1_ (mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
 8 链折叠取模:r = [numa,na] mod d
bool lmmp_trialdiv_ (mp_srcptr np, mp_size_t nn, ushort N)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_trialdiv_table_free_ (void)
static int trial_div35711 (ulong n)
 校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0

变量

const mp_limb_t r35711_mask_map [19]

函数说明

◆ lmmp_mod_4chunk_1_()

mp_limb_t lmmp_mod_4chunk_1_ ( mp_srcptr numa,
mp_size_t na,
mp_limb_t d,
mp_limb_t dinv,
mp_limb_t r2,
mp_limb_t base,
mp_limb_t mi )

4 链折叠取模:r = [numa,na] mod d

参数
numa被除数(长度为 na 个limb)
na被除数的 limb 长度
d除数(单个 limb)
dinv除数的逆元(d*dinv==1 mod 2^64)
r2蒙域预处理(r2=B^2 mod d)
base蒙域预处理(base=B mod d)
mi蒙域预处理(mi=-dinv mod 2^64)
警告
na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64, dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
返回
[numa,na] mod d

在文件 mod_chunk.c 第 52 行定义.

53 {
54 lmmp_param_assert(na > 0);
55 lmmp_param_assert(numa != NULL);
56 lmmp_param_assert(d % 2 == 1);
58 lmmp_param_assert(dinv * d == 1);
59 lmmp_param_assert(dinv + mi == 0);
60 lmmp_param_assert(base < d);
62
63 mp_size_t L = na >> 2, t = na & 3;
64 ulong bw = r2, wm = base;
65 for (mp_size_t ee = L; ee; ee >>= 1) {
66 if (ee & 1) wm = mont63_mul(wm, bw, d, mi);
67 bw = mont63_mul(bw, bw, d, mi);
68 }
69 ulong bt = r2; /* mont(B^t):t=0 时终段有 if(t) 守卫 */
70 for (mp_size_t k = 1; k < t; ++k) bt = mont63_mul(bt, r2, d, mi);
71
72 const mp_limb_t *p0 = numa + t, *p1 = numa + t + L, *p2 = numa + t + 2 * L,
73 *p3 = numa + t + 3 * L, *e = numa + t + L;
74 ulong c0 = 0, c1 = 0, c2 = 0, c3 = 0;
75 while (p0 < e) {
76 ulong s, l, q;
77 s = *p0++;
78 l = s - c0;
79 q = l * dinv;
80 c0 = _u128high((u128)q * d) + (s < c0);
81 s = *p1++;
82 l = s - c1;
83 q = l * dinv;
84 c1 = _u128high((u128)q * d) + (s < c1);
85 s = *p2++;
86 l = s - c2;
87 q = l * dinv;
88 c2 = _u128high((u128)q * d) + (s < c2);
89 s = *p3++;
90 l = s - c3;
91 q = l * dinv;
92 c3 = _u128high((u128)q * d) + (s < c3);
93 }
94 ulong cb = 0;
95 for (mp_size_t i = 0; i < t; ++i) {
96 ulong s = numa[i], l = s - cb;
97 ulong q = l * dinv;
98 cb = _u128high((u128)q * d) + (s < cb);
99 }
100 ulong cj[4] = {c0, c1, c2, c3}, wT = wm, acc = 0;
101 for (int j = 0; j < 3; ++j) {
102 acc += mont63_mul(cj[j], wm, d, mi);
103 acc = acc >= d ? acc - d : acc;
104 wm = mont63_mul(wm, wT, d, mi);
105 }
106 acc += mont63_mul(cj[3], wm, d, mi);
107 acc = acc >= d ? acc - d : acc;
108 acc += cb; /* 底组项权重 B^t*w^0 */
109 acc = acc >= d ? acc - d : acc;
110 if (t) acc = mont63_mul(acc, bt, d, mi); /* ×B^t:N ≡ -B^t*acc */
111 return acc ? d - acc : 0;
112}
#define k
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define r2
#define t
#define s
#define c1
#define c0
uint64_t ulong
定义 numth.h:39

引用了 c0, c1, k, lmmp_mod_4chunk_1_(), lmmp_param_assert, MONT63_MAX, mont63_mul(), r2, s , 以及 t.

被这些函数引用 lmmp_mod_4chunk_1_(), lmmp_trialdiv_() , 以及 trialdiv_leg_4_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_mod_8chunk_1_()

mp_limb_t lmmp_mod_8chunk_1_ ( mp_srcptr numa,
mp_size_t na,
mp_limb_t d,
mp_limb_t dinv,
mp_limb_t r2,
mp_limb_t base,
mp_limb_t mi )

8 链折叠取模:r = [numa,na] mod d

参数
numa被除数(长度为 na 个limb)
na被除数的 limb 长度
d除数(单个 limb)
dinv除数的逆元(d*dinv==1 mod 2^64)
r2蒙域预处理(r2=B^2 mod d)
base蒙域预处理(base=B mod d)
mi蒙域预处理(mi=-dinv mod 2^64)
警告
na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64, dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
返回
[numa,na] mod d

在文件 mod_chunk.c 第 114 行定义.

115 {
116 lmmp_param_assert(na > 0);
117 lmmp_param_assert(numa != NULL);
118 lmmp_param_assert(d % 2 == 1);
120 lmmp_param_assert(dinv * d == 1);
121 lmmp_param_assert(dinv + mi == 0);
122 lmmp_param_assert(base < d);
124
125 mp_size_t L = na >> 3, t = na & 7;
126 ulong bw = r2, wm = base;
127 for (mp_size_t ee = L; ee; ee >>= 1) {
128 if (ee & 1) wm = mont63_mul(wm, bw, d, mi);
129 bw = mont63_mul(bw, bw, d, mi);
130 }
131 ulong bt = r2; /* mont(B^t):t=0 时终段有 if(t) 守卫 */
132 for (mp_size_t k = 1; k < t; ++k) bt = mont63_mul(bt, r2, d, mi);
133
134 const mp_limb_t *p0 = numa + t, *p1 = numa + t + L, *p2 = numa + t + 2 * L,
135 *p3 = numa + t + 3 * L, *p4 = numa + t + 4 * L, *p5 = numa + t + 5 * L,
136 *p6 = numa + t + 6 * L, *p7 = numa + t + 7 * L, *e = numa + t + L;
137 ulong c0 = 0, c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0, c7 = 0;
138 while (p0 < e) {
139 ulong s, l, q;
140 s = *p0++;
141 l = s - c0;
142 q = l * dinv;
143 c0 = _u128high((u128)q * d) + (s < c0);
144 s = *p1++;
145 l = s - c1;
146 q = l * dinv;
147 c1 = _u128high((u128)q * d) + (s < c1);
148 s = *p2++;
149 l = s - c2;
150 q = l * dinv;
151 c2 = _u128high((u128)q * d) + (s < c2);
152 s = *p3++;
153 l = s - c3;
154 q = l * dinv;
155 c3 = _u128high((u128)q * d) + (s < c3);
156 s = *p4++;
157 l = s - c4;
158 q = l * dinv;
159 c4 = _u128high((u128)q * d) + (s < c4);
160 s = *p5++;
161 l = s - c5;
162 q = l * dinv;
163 c5 = _u128high((u128)q * d) + (s < c5);
164 s = *p6++;
165 l = s - c6;
166 q = l * dinv;
167 c6 = _u128high((u128)q * d) + (s < c6);
168 s = *p7++;
169 l = s - c7;
170 q = l * dinv;
171 c7 = _u128high((u128)q * d) + (s < c7);
172 }
173 ulong cb = 0;
174 for (mp_size_t i = 0; i < t; ++i) {
175 ulong s = numa[i], l = s - cb;
176 ulong q = l * dinv;
177 cb = _u128high((u128)q * d) + (s < cb);
178 }
179 ulong cj[8] = {c0, c1, c2, c3, c4, c5, c6, c7}, wT = wm, acc = 0;
180 for (int j = 0; j < 7; ++j) {
181 acc += mont63_mul(cj[j], wm, d, mi);
182 acc = acc >= d ? acc - d : acc;
183 wm = mont63_mul(wm, wT, d, mi);
184 }
185 acc += mont63_mul(cj[7], wm, d, mi);
186 acc = acc >= d ? acc - d : acc;
187 acc += cb; /* 底组项权重 B^t*w^0 */
188 acc = acc >= d ? acc - d : acc;
189 if (t) acc = mont63_mul(acc, bt, d, mi); /* ×B^t:N ≡ -B^t*acc */
190 return acc ? d - acc : 0;
191}

引用了 c0, c1, k, lmmp_mod_8chunk_1_(), lmmp_param_assert, MONT63_MAX, mont63_mul(), r2, s , 以及 t.

被这些函数引用 lmmp_mod_8chunk_1_(), lmmp_trialdiv_() , 以及 trialdiv_leg_8_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_trialdiv_()

bool lmmp_trialdiv_ ( mp_srcptr np,
mp_size_t nn,
ushort N )

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

试除法:判定 [np,nn] 是否存在小奇素数因子

参数
np被除数(长度为 nn 个limb)
nn被除数的 limb 长度
N试除上界提示
警告
np!=NULL, nn>0
注解
试除素数自 3 起(因子 2 由调用方自理);N 仅为上界提示——实际试除 范围为所有含 <=N 素数的块之并(块粒度向上取整,可能试除 N 之后的 素数),需要精确 N 边界者勿用
返回
存在能整除 [np,nn] 的试除素数则返回true,否则返回false

引用了 lmmp_mod_4chunk_1_(), lmmp_mod_8chunk_1_(), lmmp_trialdiv_(), lmmp_trialdiv_table_free_(), r2 , 以及 r35711_mask_map.

被这些函数引用 lmmp_is_prime_n_(), lmmp_trialdiv_() , 以及 lmmp_trialdiv_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_trialdiv_table_free_()

void lmmp_trialdiv_table_free_ ( void )

在文件 trialdiv.c 第 205 行定义.

205 {
206 lmmp_free(G.blks);
207 G.blks = NULL;
208 G.blkc = 0;
209 G.bn = 0;
210 G.bn_inv = 0;
211 G.bn_chunk = 0;
212 G.pi = 1;
213 G.t = 1;
214}
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define G

引用了 G, lmmp_free() , 以及 lmmp_trialdiv_table_free_().

被这些函数引用 lmmp_trialdiv_() , 以及 lmmp_trialdiv_table_free_().

函数调用图:
这是这个函数的调用关系图:

◆ trial_div35711()

int trial_div35711 ( ulong n)
inlinestatic

校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0

在文件 trialdiv.h 第 83 行定义.

83 {
84 uint rem = n % 1155; // 1155 = 3 * 5 * 7 * 11
85 uint idx = rem / LIMB_BITS;
86 uint bit = rem % LIMB_BITS;
87 return (r35711_mask_map[idx] >> bit) & 1ULL;
88}
#define LIMB_BITS
定义 lmmp.h:102
#define n
uint32_t uint
定义 numth.h:38
const mp_limb_t r35711_mask_map[19]

引用了 LIMB_BITS, n, r35711_mask_map , 以及 trial_div35711().

被这些函数引用 lmmp_is_prime_uint_(), lmmp_is_prime_ulong_(), trial_div16() , 以及 trial_div35711().

函数调用图:
这是这个函数的调用关系图:

变量说明

◆ r35711_mask_map

const mp_limb_t r35711_mask_map[19]
extern

在文件 trialdiv.c 第 216 行定义.

216 {
217 (mp_limb_t)(0x93cf359a5b74dee9), (mp_limb_t)(0x6badd25dadb36966), (mp_limb_t)(0x6ed3cd279e4bb4b6),
218 (mp_limb_t)(0xb66d6cd35ba6bb59), (mp_limb_t)(0xc976b2cde59a4f3c), (mp_limb_t)(0x34de792dd2f9a6b7),
219 (mp_limb_t)(0xb34d6e96ede59b4b), (mp_limb_t)(0xcf3696793ef259ad), (mp_limb_t)(0xf4b34b669add25fa),
220 (mp_limb_t)(0xfa4bb5966d2cd2f9), (mp_limb_t)(0x59a4f7c9e696cf35), (mp_limb_t)(0x2d9a7b76976b2cdb),
221 (mp_limb_t)(0xd659f4bb49e7b2cd), (mp_limb_t)(0xcf259a7b34d6e93e), (mp_limb_t)(0xadd65dacb36b66d3),
222 (mp_limb_t)(0xd2dd279e4b3cb769), (mp_limb_t)(0x696cdb5ba4bb5d66), (mp_limb_t)(0x77b2eda59acf3c96),
223 (mp_limb_t)(0x0000000000000001)};

被这些函数引用 lmmp_trialdiv_() , 以及 trial_div35711().