LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime_ulong.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#include "impl/inlines.h"
24#include "impl/longlong.h"
25#include "impl/prime_table.h"
26#include "impl/trialdiv.h"
27#include "lmmp/lmmpn.h"
28#include "lmmp/numth.h"
29#include "mparam.h"
30#include "numth/is_prime.h"
31
32/*
33mont63 只能用于小于 2^63 的数,否则会溢出导致计算结果不正确
34mont64 可以用于任意大小的数,但由于考虑了溢出的情况,所以速度理论上会慢一些(并未详细测试)
35*/
36#define MONT63_MAX ((ulong)(0x7fffffffffffffff))
37
38static inline ulong mont64_reduce(u128 t, ulong m, ulong m_inv) {
39 // sum = k*m + t < 2^129,第 129 位 c 由 128 位回绕捕获
40 ulong k = _u128low(t) * m_inv;
41 u128 km = (u128)k * m;
42 u128 sum = km + t;
43 uint c = sum < km;
44 ulong hi = _u128high(sum);
45 if (c) return hi - m; // 2^128 + hi - m 的低 128 位高位即结果
46 return hi >= m ? hi - m : hi;
47}
48
49static inline ulong mont_R2(ulong m) {
50 mp_bitcnt_t shift = 0;
51 clz_shl_u64(m, m, shift);
52 return _bpow_preinv_(m, shift, 2, lmmp_inv_1_(m));
53}
54
55static inline ulong mont64_R2(ulong m) {
56 return mont_R2(m);
57}
58
59static inline ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv) {
60 return mont64_reduce((u128)x * R2, m, m_inv);
61}
62
63static inline ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv) {
64 return mont64_reduce((u128)a * b, m, m_inv);
65}
66
67static inline ulong mont63_reduce(u128 t, ulong m, ulong m_inv) {
68 // m < 2^63 时 k*m + t < 2^127,无 129 位溢出
69 ulong k = _u128low(t) * m_inv;
70 u128 sum = (u128)k * m + t;
71 ulong hi = _u128high(sum);
72 return hi >= m ? hi - m : hi;
73}
74
75static inline ulong mont63_R2(ulong m) {
76 return mont_R2(m);
77}
78
79static inline ulong to_mont63(ulong x, ulong R2, ulong m, ulong m_inv) {
80 return mont63_reduce((u128)x * R2, m, m_inv);
81}
82
83static inline ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv) {
84 return mont63_reduce((u128)a * b, m, m_inv);
85}
86
87/*
88 强伪素数第二阶段检查:v = b^d(蒙域)已算出。
89 one/m_1 为蒙域的 1 与 m-1。
90*/
91static inline int sprp_check63(ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1) {
92 if (v == one || v == m_1) return 1;
93 for (t--; t > 0; t--) {
94 v = mont63_mul(v, v, m, m_inv);
95 if (v == m_1) return 1;
96 if (v == one) return 0;
97 }
98 return 0;
99}
100
101static inline int sprp_check64(ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1) {
102 if (v == one || v == m_1) return 1;
103 for (t--; t > 0; t--) {
104 v = mont64_mul(v, v, m, m_inv);
105 if (v == m_1) return 1;
106 if (v == one) return 0;
107 }
108 return 0;
109}
110
111/*
112 基底 2 专用幂(蒙域,LSB 链):基底以蒙域值起步后,平方链保持
113 base_j = 2^(2^j)*B 不变量,结果恒在蒙域;平方链与 v 乘链相互独立,
114 乱序执行可重叠。
115*/
116static inline ulong powmod2_63(ulong d, ulong R2, ulong m, ulong m_inv) {
117 ulong v = to_mont63(1, R2, m, m_inv);
118 ulong base = to_mont63(2, R2, m, m_inv);
119 while (1) {
120 if (d & 1) v = mont63_mul(v, base, m, m_inv);
121 d >>= 1;
122 if (d == 0) break;
123 base = mont63_mul(base, base, m, m_inv);
124 }
125 return v;
126}
127
128static inline ulong powmod2_64(ulong d, ulong R2, ulong m, ulong m_inv) {
129 ulong v = to_mont64(1, R2, m, m_inv);
130 ulong base = to_mont64(2, R2, m, m_inv);
131 while (1) {
132 if (d & 1) v = mont64_mul(v, base, m, m_inv);
133 d >>= 1;
134 if (d == 0) break;
135 base = mont64_mul(base, base, m, m_inv);
136 }
137 return v;
138}
139
140static void powmod_win3_63(ulong *pv, ulong bm, ulong d, int ebits, ulong m, ulong m_inv) {
141 ulong w[8], v = bm;
142 int bit = ebits - 2;
143 w[1] = bm;
144 w[2] = mont63_mul(bm, bm, m, m_inv);
145 w[3] = mont63_mul(w[2], bm, m, m_inv);
146 w[4] = mont63_mul(w[2], w[2], m, m_inv);
147 w[5] = mont63_mul(w[4], bm, m, m_inv);
148 w[6] = mont63_mul(w[3], w[3], m, m_inv);
149 w[7] = mont63_mul(w[6], bm, m, m_inv);
150 while (bit >= 2) {
151 v = mont63_mul(v, v, m, m_inv);
152 v = mont63_mul(v, v, m, m_inv);
153 v = mont63_mul(v, v, m, m_inv);
154 {
155 uint idx = (uint)(d >> (bit - 2)) & 7;
156 if (idx) v = mont63_mul(v, w[idx], m, m_inv);
157 }
158 bit -= 3;
159 }
160 for (; bit >= 0; bit--) {
161 v = mont63_mul(v, v, m, m_inv);
162 if ((d >> bit) & 1) v = mont63_mul(v, bm, m, m_inv);
163 }
164 *pv = v;
165}
166
167static void powmod2_win3_63(ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv) {
168 ulong w1[8], w2[8], v1 = bm1, v2 = bm2;
169 int bit = ebits - 2;
170 w1[1] = bm1;
171 w1[2] = mont63_mul(bm1, bm1, m, m_inv);
172 w1[3] = mont63_mul(w1[2], bm1, m, m_inv);
173 w1[4] = mont63_mul(w1[2], w1[2], m, m_inv);
174 w1[5] = mont63_mul(w1[4], bm1, m, m_inv);
175 w1[6] = mont63_mul(w1[3], w1[3], m, m_inv);
176 w1[7] = mont63_mul(w1[6], bm1, m, m_inv);
177 w2[1] = bm2;
178 w2[2] = mont63_mul(bm2, bm2, m, m_inv);
179 w2[3] = mont63_mul(w2[2], bm2, m, m_inv);
180 w2[4] = mont63_mul(w2[2], w2[2], m, m_inv);
181 w2[5] = mont63_mul(w2[4], bm2, m, m_inv);
182 w2[6] = mont63_mul(w2[3], w2[3], m, m_inv);
183 w2[7] = mont63_mul(w2[6], bm2, m, m_inv);
184 while (bit >= 2) {
185 v1 = mont63_mul(v1, v1, m, m_inv);
186 v2 = mont63_mul(v2, v2, m, m_inv);
187 v1 = mont63_mul(v1, v1, m, m_inv);
188 v2 = mont63_mul(v2, v2, m, m_inv);
189 v1 = mont63_mul(v1, v1, m, m_inv);
190 v2 = mont63_mul(v2, v2, m, m_inv);
191 {
192 uint idx = (uint)(d >> (bit - 2)) & 7;
193 if (idx) {
194 v1 = mont63_mul(v1, w1[idx], m, m_inv);
195 v2 = mont63_mul(v2, w2[idx], m, m_inv);
196 }
197 }
198 bit -= 3;
199 }
200 for (; bit >= 0; bit--) {
201 v1 = mont63_mul(v1, v1, m, m_inv);
202 v2 = mont63_mul(v2, v2, m, m_inv);
203 if ((d >> bit) & 1) {
204 v1 = mont63_mul(v1, bm1, m, m_inv);
205 v2 = mont63_mul(v2, bm2, m, m_inv);
206 }
207 }
208 *pv1 = v1;
209 *pv2 = v2;
210}
211
212static void powmod2_win3_64(ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv) {
213 ulong w1[8], w2[8], v1 = bm1, v2 = bm2;
214 int bit = ebits - 2;
215 w1[1] = bm1;
216 w1[2] = mont64_mul(bm1, bm1, m, m_inv);
217 w1[3] = mont64_mul(w1[2], bm1, m, m_inv);
218 w1[4] = mont64_mul(w1[2], w1[2], m, m_inv);
219 w1[5] = mont64_mul(w1[4], bm1, m, m_inv);
220 w1[6] = mont64_mul(w1[3], w1[3], m, m_inv);
221 w1[7] = mont64_mul(w1[6], bm1, m, m_inv);
222 w2[1] = bm2;
223 w2[2] = mont64_mul(bm2, bm2, m, m_inv);
224 w2[3] = mont64_mul(w2[2], bm2, m, m_inv);
225 w2[4] = mont64_mul(w2[2], w2[2], m, m_inv);
226 w2[5] = mont64_mul(w2[4], bm2, m, m_inv);
227 w2[6] = mont64_mul(w2[3], w2[3], m, m_inv);
228 w2[7] = mont64_mul(w2[6], bm2, m, m_inv);
229 while (bit >= 2) {
230 v1 = mont64_mul(v1, v1, m, m_inv);
231 v2 = mont64_mul(v2, v2, m, m_inv);
232 v1 = mont64_mul(v1, v1, m, m_inv);
233 v2 = mont64_mul(v2, v2, m, m_inv);
234 v1 = mont64_mul(v1, v1, m, m_inv);
235 v2 = mont64_mul(v2, v2, m, m_inv);
236 {
237 uint idx = (uint)(d >> (bit - 2)) & 7;
238 if (idx) {
239 v1 = mont64_mul(v1, w1[idx], m, m_inv);
240 v2 = mont64_mul(v2, w2[idx], m, m_inv);
241 }
242 }
243 bit -= 3;
244 }
245 for (; bit >= 0; bit--) {
246 v1 = mont64_mul(v1, v1, m, m_inv);
247 v2 = mont64_mul(v2, v2, m, m_inv);
248 if ((d >> bit) & 1) {
249 v1 = mont64_mul(v1, bm1, m, m_inv);
250 v2 = mont64_mul(v2, bm2, m, m_inv);
251 }
252 }
253 *pv1 = v1;
254 *pv2 = v2;
255}
256
258 lmmp_param_assert(n > 2);
259 if (n <= MP_UINT_MAX) {
260 if (n % 2 == 0)
261 return false;
263 } else if (n < 684630005672341) {
264 ushort bases[2];
265 bases[0] = 2;
266 bases[1] = dj_base49[((0x3AC69A35UL * n) & 0xFFFFFFFFUL) >> 21] + 3;
267 if (n % bases[0] == 0)
268 return false;
269 if (n % bases[1] == 0)
270 return false;
271
272 ulong m_inv = -lmmp_binvert_ulong_(n);
273 ulong R2 = mont63_R2(n);
274 ulong one = to_mont63(1, R2, n, m_inv);
275 ulong m_1 = to_mont63(n - 1, R2, n, m_inv);
276
277 ulong d;
278 ulong t;
279 ctz_shr_u64(d, n - 1, t);
280 int eb = lmmp_limb_bits_(d);
281
282 ulong v2 = powmod2_63(d, R2, n, m_inv);
283 if (!sprp_check63(v2, t, n, m_inv, one, m_1)) return false;
284
285 ulong v;
286 powmod_win3_63(&v, to_mont63(bases[1], R2, n, m_inv), d, eb, n, m_inv);
287 return sprp_check63(v, t, n, m_inv, one, m_1);
288 } else {
289 ushort bases[3];
290 ulong bbmask = dj_base64[((0x3AC69A35UL * n) & 0xFFFFFFFFUL) >> 18];
291 bases[0] = 2;
292 bases[1] = (bbmask & 0x8000) ? 26460 : 9375;
293 bases[2] = (bbmask & 0x7FFF) + 3;
294
295 if (n % bases[0] == 0)
296 return false;
297 if (n % bases[1] == 0)
298 return false;
299 if (n % bases[2] == 0)
300 return n == bases[2];
301
302 ulong one = 1;
303 ulong m_1 = n - 1;
304 ulong m_inv = -lmmp_binvert_ulong_(n);
305
306 ulong d;
307 ulong t;
308 ctz_shr_u64(d, n - 1, t);
309 int eb = lmmp_limb_bits_(d);
310
311 if (n <= MONT63_MAX) {
312 ulong R2 = mont63_R2(n);
313 one = to_mont63(one, R2, n, m_inv);
314 m_1 = to_mont63(m_1, R2, n, m_inv);
315
316 ulong v2 = powmod2_63(d, R2, n, m_inv);
317 if (!sprp_check63(v2, t, n, m_inv, one, m_1)) return false;
318
319 /* 双基底交错 + 3 位窗口 */
320 ulong bm1 = to_mont63(bases[1], R2, n, m_inv);
321 ulong bm2 = to_mont63(bases[2], R2, n, m_inv);
322 ulong v1, v2_;
323 powmod2_win3_63(&v1, &v2_, bm1, bm2, d, eb, n, m_inv);
324 if (!sprp_check63(v1, t, n, m_inv, one, m_1)) return false;
325 return sprp_check63(v2_, t, n, m_inv, one, m_1);
326 } else {
327 ulong R2 = mont64_R2(n);
328 one = to_mont64(one, R2, n, m_inv);
329 m_1 = to_mont64(m_1, R2, n, m_inv);
330
331 ulong v2 = powmod2_64(d, R2, n, m_inv);
332 if (!sprp_check64(v2, t, n, m_inv, one, m_1)) return false;
333
334 /* 双基底交错 + 3 位窗口 */
335 ulong bm1 = to_mont64(bases[1], R2, n, m_inv);
336 ulong bm2 = to_mont64(bases[2], R2, n, m_inv);
337 ulong v1, v2_;
338 powmod2_win3_64(&v1, &v2_, bm1, bm2, d, eb, n, m_inv);
339 if (!sprp_check64(v1, t, n, m_inv, one, m_1)) return false;
340 return sprp_check64(v2_, t, n, m_inv, one, m_1);
341 }
342 }
343}
344
346 if (n == 2)
347 return true;
348 if (n % 2 == 0 || n <= 1)
349 return false;
350 if (n <= MP_UINT_MAX) {
351 int judge = lmmp_is_prime_table_(n);
352 if (judge == 0) {
353 return false;
354 } else if (judge == 1) {
355 return true;
356 }
357 }
358 if (trial_div35711(n))
359 return false;
361}
362
363// 64位内最大的质数
364#define ULONG_PRIME_MAX 0xFFFFFFFFFFFFFFC5ull
365#define ULONG_PRIME_MIN 2
366
367static inline int trial_div16(ulong n) {
368 return trial_div35711(n)
369 || n % 13 == 0 || n % 17 == 0 || n % 19 == 0 || n % 23 == 0
370 || n % 29 == 0 || n % 31 == 0 || n % 37 == 0 || n % 41 == 0
371 || n % 43 == 0 || n % 47 == 0 || n % 53 == 0 || n % 59 == 0
372 || n % 61 == 0 || n % 67 == 0 || n % 71 == 0;
373}
374
378 return prime_short_table[idx];
379 } else if (n >= ULONG_PRIME_MAX) {
380 return MP_ULONG_MAX;
381 } else {
382 n += (n % 2 == 0) ? 1 : 2;
383 while (1) {
384 if (trial_div16(n)) {
385 n += 2;
386 } else {
388 return n;
389 } else {
390 n += 2;
391 }
392 }
393 }
394 }
395}
396
398 if (n < ULONG_PRIME_MIN) {
399 return 0;
400 } else if (n < PRIME_SHORT_TABLE_N) {
402 return prime_short_table[idx - 1];
403 } else {
404 n -= (n % 2 == 0) ? 1 : 0;
405 while (1) {
406 if (trial_div16(n)) {
407 n -= 2;
408 } else {
410 return n;
411 } else {
412 n -= 2;
413 }
414 }
415 }
416 }
417}
#define k
#define lmmp_limb_bits_
const uint16_t dj_base49[2048]
Copyright (C) 2026 HJimmyK (Jericho Knox)
const uint16_t dj_base64[16384]
bool lmmp_is_prime_uint_notrial_(uint n)
u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)
static ulong mont64_R2(ulong m)
static void powmod_win3_63(ulong *pv, ulong bm, ulong d, int ebits, ulong m, ulong m_inv)
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ulong to_mont63(ulong x, ulong R2, ulong m, ulong m_inv)
#define ULONG_PRIME_MIN
static ulong mont63_R2(ulong m)
static ulong powmod2_63(ulong d, ulong R2, ulong m, ulong m_inv)
static int sprp_check64(ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1)
static int sprp_check63(ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1)
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
static int trial_div16(ulong n)
static ulong mont_R2(ulong m)
static ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont64_reduce(u128 t, ulong m, ulong m_inv)
static void powmod2_win3_64(ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv)
static void powmod2_win3_63(ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv)
#define ULONG_PRIME_MAX
static ulong powmod2_64(ulong d, ulong R2, ulong m, ulong m_inv)
static ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv)
#define MP_UINT_MAX
#define MP_ULONG_MAX
size_t mp_bitcnt_t
定义 lmmp.h:98
#define LMMP_NOINLINE
定义 lmmp.h:216
#define lmmp_param_assert(x)
定义 lmmp.h:509
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
static uint64_t _bpow_preinv_(uint64_t m, uint64_t k, int nb, uint64_t inv)
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define clz_shl_u64(r, x, cnt)
#define bm1
#define v1
#define v2
#define t
#define n
#define w2
ulong lmmp_prev_prime_ulong_(ulong n)
小于等于n的上一个素数
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint32_t uint
定义 numth.h:38
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
uint16_t ushort
定义 numth.h:36
bool lmmp_is_prime_ulong_(ulong n)
判断素数
uint64_t ulong
定义 numth.h:39
ulong lmmp_next_prime_ulong_(ulong n)
大于n的下一个素数
#define PRIME_SHORT_TABLE_SIZE
int lmmp_is_prime_table_(uint p)
根据全局素数表判断一个数是否为素数
#define PRIME_SHORT_TABLE_N
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量
static int trial_div35711(ulong n)
校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0