LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime_uint.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/numth.h"
28#include "mparam.h"
29#include "numth/is_prime.h"
30
31
32static inline ulong urem32_preinv(ulong t, ulong n, ulong dinv) {
33 ulong q = _umul64to64hi_(t, dinv);
34 ulong r = t - q * n;
35 if (r >= n) r += n;
36 return r;
37}
38
39static void powmod2b_u32(uint b, uint d, int ebits, uint n, ulong dinv, uint* py2, uint* pyb) {
40 ulong xb = b;
41 if (xb >= n)
42 xb = urem32_preinv(xb, n, dinv);
43
44 if (ebits <= 6) {
45 ulong x2 = urem32_preinv((ulong)1 << d, n, dinv);
46 for (int k = ebits - 2; k >= 0; k--) {
47 xb = urem32_preinv(xb * xb, n, dinv);
48 if ((d >> k) & 1)
49 xb = urem32_preinv(xb * b, n, dinv);
50 }
51 *py2 = (uint)x2;
52 *pyb = (uint)xb;
53 return;
54 }
55
56 ulong x2 = urem32_preinv((ulong)1 << (d >> (ebits - 6)), n, dinv);
57 for (int k = ebits - 2; k >= ebits - 6; k--) {
58 xb = urem32_preinv(xb * xb, n, dinv);
59 if ((d >> k) & 1)
60 xb = urem32_preinv(xb * b, n, dinv);
61 }
62 if (n < (1u << 31)) {
63 for (int k = ebits - 7; k >= 0; k--) {
64 x2 = urem32_preinv(x2 * x2, n, dinv);
65 x2 <<= (d >> k) & 1;
66 xb = urem32_preinv(xb * xb, n, dinv);
67 if ((d >> k) & 1)
68 xb = urem32_preinv(xb * b, n, dinv);
69 }
70 if (x2 >= n) x2 -= n;
71 } else {
72 for (int k = ebits - 7; k >= 0; k--) {
73 x2 = urem32_preinv(x2 * x2, n, dinv);
74 x2 <<= (d >> k) & 1;
75 if (x2 >= n) x2 -= n;
76 xb = urem32_preinv(xb * xb, n, dinv);
77 if ((d >> k) & 1)
78 xb = urem32_preinv(xb * b, n, dinv);
79 }
80 }
81 *py2 = (uint)x2;
82 *pyb = (uint)xb;
83}
84
85static int sprp_check_u32(uint y, ulong t, uint n, ulong dinv) {
86 if (y == 1 || y == n - 1)
87 return 1;
88 for (t--; t > 0; t--) {
89 ulong v = y;
90 v = urem32_preinv(v * v, n, dinv);
91 y = (uint)v;
92 if (y == n - 1) return 1;
93 if (y == 1) return 0;
94 }
95 return 0;
96}
97
100 lmmp_param_assert(n % 2 == 1);
101
102 uint base = dj_base49[((0x3AC69A35UL * n) & 0xFFFFFFFFUL) >> 21] + 3;
103 if (n % base == 0 || base % n == 0) {
104 if (n > base)
105 return false;
106 for (uint p = 3; p * p <= n; p += 2)
107 if (n % p == 0) return false;
108 return true;
109 }
110
111 ulong dinv = MP_ULONG_MAX / n + 1;
112 ulong d;
113 ulong t;
114 ctz_shr_u64(d, n - 1, t);
115 int ebits = lmmp_limb_bits_(d);
116
117 uint y2, yb;
118 powmod2b_u32(base, (uint)d, ebits, n, dinv, &y2, &yb);
119 if (!sprp_check_u32(y2, t, n, dinv))
120 return false;
121 return sprp_check_u32(yb, t, n, dinv);
122}
123
125 if (n == 2)
126 return true;
127 if (n % 2 == 0 || n <= 1)
128 return false;
129 int judge = lmmp_is_prime_table_(n);
130 if (judge == 0) {
131 return false;
132 } else if (judge == 1) {
133 return true;
134 }
135
136 if (trial_div35711(n))
137 return false;
138
140}
#define k
#define lmmp_limb_bits_
const uint16_t dj_base49[2048]
Copyright (C) 2026 HJimmyK (Jericho Knox)
bool lmmp_is_prime_uint_notrial_(uint n)
u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
static int sprp_check_u32(uint y, ulong t, uint n, ulong dinv)
static void powmod2b_u32(uint b, uint d, int ebits, uint n, ulong dinv, uint *py2, uint *pyb)
static ulong urem32_preinv(ulong t, ulong n, ulong dinv)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MP_ULONG_MAX
#define LMMP_NOINLINE
定义 lmmp.h:216
#define lmmp_param_assert(x)
定义 lmmp.h:509
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
#define n
uint32_t uint
定义 numth.h:38
bool lmmp_is_prime_uint_(uint n)
判断素数
uint64_t ulong
定义 numth.h:39
int lmmp_is_prime_table_(uint p)
根据全局素数表判断一个数是否为素数
static int trial_div35711(ulong n)
校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0