LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
32
static
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
39
static
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
85
static
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
98
LMMP_NOINLINE
bool
lmmp_is_prime_uint_notrial_
(
uint
n
) {
99
lmmp_param_assert
(
n
> 2);
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
124
bool
lmmp_is_prime_uint_
(
uint
n
) {
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
139
return
lmmp_is_prime_uint_notrial_
(
n
);
140
}
k
#define k
inlines.h
lmmp_limb_bits_
#define lmmp_limb_bits_
定义
inlines.h:164
is_prime.h
dj_base49
const uint16_t dj_base49[2048]
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
is_prime_table.c:29
lmmp_is_prime_uint_notrial_
bool lmmp_is_prime_uint_notrial_(uint n)
u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
定义
is_prime_uint.c:98
sprp_check_u32
static int sprp_check_u32(uint y, ulong t, uint n, ulong dinv)
定义
is_prime_uint.c:85
powmod2b_u32
static void powmod2b_u32(uint b, uint d, int ebits, uint n, ulong dinv, uint *py2, uint *pyb)
定义
is_prime_uint.c:39
urem32_preinv
static ulong urem32_preinv(ulong t, ulong n, ulong dinv)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
is_prime_uint.c:32
MP_ULONG_MAX
#define MP_ULONG_MAX
定义
mparam.h:29
LMMP_NOINLINE
#define LMMP_NOINLINE
定义
lmmp.h:216
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
longlong.h
_umul64to64hi_
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
定义
longlong.h:150
ctz_shr_u64
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
longlong.h:55
t
#define t
n
#define n
numth.h
uint
uint32_t uint
定义
numth.h:38
lmmp_is_prime_uint_
bool lmmp_is_prime_uint_(uint n)
判断素数
定义
is_prime_uint.c:124
ulong
uint64_t ulong
定义
numth.h:39
prime_table.h
lmmp_is_prime_table_
int lmmp_is_prime_table_(uint p)
根据全局素数表判断一个数是否为素数
定义
prime_sieve.c:264
trialdiv.h
trial_div35711
static int trial_div35711(ulong n)
校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0
定义
trialdiv.h:83
src
lmmp
numth
is_prime_uint.c
生成于
, 为 LMMP使用
1.18.0