LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
test_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
/* 标量档素性(u32/u64)与 next/prev prime 验证:ref_is_prime64 为
24
2^64 确定性 Miller-Rabin 标量参考(64 位内简单参考允许域),
25
双向硬断言(不能错判)。128 位档见 test_numth_prime2.cpp,
26
>128 位档见 test_numth_prime_n.cpp / test_numth_proth.cpp。 */
27
28
#include "
lmmp/lmmpn.h
"
29
#include "
lmmp/numth.h
"
30
#include "
cases.h
"
31
#include "
prime_ref.h
"
32
33
/*
34
u32 档三免内核(is_prime_uint.c)定向测试:
35
惰性剩余两档界(n<2^31 零条件减 / n>=2^31 每步条件减)、短表界、
36
d 退化(n-1=2^t,ebits=1)、notrial 直调小素数(含 n==hash 基底路径)。
37
*/
38
TEST_CASE
(
"numth/prime"
, is_prime_uint_ulong_notrial) {
39
u64
seed = 0xfeed0912eadc23aeull;
40
for
(
u32
n
= 0;
n
< 10000; ++
n
) {
41
bool
expect =
ref_is_prime32
(
n
);
42
TEST_CHECK_MSG
(
lmmp_is_prime_uint_
(
n
) == expect,
"is_prime_uint small"
);
43
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(
n
) == expect,
"is_prime_ulong small"
);
44
}
45
46
for
(
int
i = 0; i < 2000; ++i) {
47
u64
n
= xorshift64(&seed);
48
bool
expect =
ref_is_prime64
(
n
);
49
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(
n
) == expect,
"is_prime_ulong random"
);
50
if
(
n
> 2)
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_notrial_
(
n
) == expect,
"is_prime_notrial random"
);
51
}
52
}
53
54
TEST_CASE
(
"numth/prime"
, is_prime_u32_tiers) {
55
u64
seed = 0xc0ffee123456789ull;
56
57
/* 2^31 档界两侧稠密扫描 */
58
for
(
u32
n
= 0x7ffffc00u;
n
<= 0x80000400u;
n
+= 2) {
59
u32
m =
n
| 1;
60
bool
expect =
ref_is_prime32
(m);
61
TEST_CHECK_MSG
(
lmmp_is_prime_uint_
(m) == expect,
"is_prime_uint 2^31 tier"
);
62
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(m) == expect,
"is_prime_ulong 2^31 tier"
);
63
}
64
65
/* u32 顶部(n>=2^31 档上端;计数式循环避免 u32 回绕死循环) */
66
for
(
u32
j = 0; j < 128; ++j) {
67
u32
m = 0xffffff01u + 2 * j;
68
bool
expect =
ref_is_prime32
(m);
69
TEST_CHECK_MSG
(
lmmp_is_prime_uint_
(m) == expect,
"is_prime_uint top tier"
);
70
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(m) == expect,
"is_prime_ulong top tier"
);
71
}
72
73
/* 短表界与 next_prime 拐角 */
74
for
(
u32
n
= 65400;
n
<= 65700; ++
n
) {
75
bool
expect =
ref_is_prime32
(
n
);
76
TEST_CHECK_MSG
(
lmmp_is_prime_uint_
(
n
) == expect,
"is_prime_uint short-table edge"
);
77
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(
n
) == expect,
"is_prime_ulong short-table edge"
);
78
}
79
80
/* d 退化:n-1 = 2^t(ebits=1),含 Fermat 素数 3/5/17/257/65537 与合数 2^31+1 */
81
for
(
u32
t
= 1;
t
<= 31; ++
t
) {
82
u32
m = (1u <<
t
) + 1;
83
bool
expect =
ref_is_prime32
(m);
84
TEST_CHECK_MSG
(
lmmp_is_prime_uint_
(m) == expect,
"is_prime_uint d=1"
);
85
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(m) == expect,
"is_prime_ulong d=1"
);
86
}
87
88
/* notrial 直调小奇数(覆盖 n==hash 基底、b>=n 起步路径;契约域 n>2 奇) */
89
for
(
u32
m = 3; m <= 3001; m += 2) {
90
bool
expect =
ref_is_prime32
(m);
91
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_notrial_
(m) == expect,
"notrial small direct"
);
92
}
93
94
/* 随机 u32 大样本 + 档界邻域加密 */
95
for
(
int
i = 0; i < 20000; ++i) {
96
u32
m = (
u32
)(xorshift64(&seed) >> (i % 2 ? 32 : 0));
97
if
(i % 3 == 0) m = 0x7fffffffu - (m & 0xffffu);
98
if
(i % 3 == 1) m = 0xffffffffu - (m & 0xffffu);
99
m |= 1;
100
if
(m < 3) m = 3;
101
bool
expect =
ref_is_prime32
(m);
102
TEST_CHECK_MSG
(
lmmp_is_prime_uint_
(m) == expect,
"is_prime_uint random u32"
);
103
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_
(m) == expect,
"is_prime_ulong random u32"
);
104
TEST_CHECK_MSG
(
lmmp_is_prime_ulong_notrial_
(m) == expect,
"notrial random u32"
);
105
}
106
107
/* next_prime u32 区段拐角:返回值与间隔无素数 */
108
const
u32
starts[] = {65521, 65522, 0x7ffffff0u, 0xfffff000u};
109
for
(
size_t
s_index = 0; s_index <
ARRAY_SIZE
(starts); ++s_index) {
110
u32
s
= starts[s_index];
111
u32
p = (
u32
)
lmmp_next_prime_ulong_
(
s
);
112
TEST_CHECK_MSG
(p >
s
&&
ref_is_prime32
(p),
"next_prime u32 corner hit"
);
113
for
(
u32
m = (
s
+ 1) | 1; m < p; m += 2)
114
TEST_CHECK_MSG
(!
ref_is_prime32
(m),
"next_prime u32 corner gap"
);
115
}
116
}
117
118
TEST_CASE
(
"numth/prime"
, next_prev_prime) {
119
// 小范围穷举
120
for
(
ulong
n
= 0;
n
< 1200; ++
n
) {
121
ulong
next =
lmmp_next_prime_ulong_
(
n
);
122
if
(
n
< 2) {
123
TEST_CHECK_EQ
(next, 2u);
124
}
else
{
125
bool
found =
false
;
126
for
(
ulong
k
=
n
+ 1;
k
< 100000; ++
k
) {
127
if
(
ref_is_prime64
(
k
)) {
TEST_CHECK_EQ
(next,
k
); found =
true
;
break
; }
128
}
129
TEST_CHECK
(found);
130
}
131
ulong
p =
lmmp_prev_prime_ulong_
(
n
);
132
if
(
n
< 2)
TEST_CHECK_EQ
(p, 0u);
133
else
{
134
bool
found =
false
;
135
for
(
ulong
k
=
n
;; --
k
) {
136
if
(
ref_is_prime64
(
k
)) {
TEST_CHECK_EQ
(p,
k
); found =
true
;
break
; }
137
}
138
TEST_CHECK
(found);
139
}
140
}
141
142
// 随机 64 位附近
143
u64
seed = 0x230bc3ae812873c0ull;
144
for
(
int
i = 0; i < 60; ++i) {
145
ulong
n
= xorshift64(&seed) | 1;
146
if
(
n
< 2)
n
= 2;
147
ulong
next =
lmmp_next_prime_ulong_
(
n
);
148
TEST_CHECK_MSG
(next >
n
,
"next_prime > n"
);
149
TEST_CHECK_MSG
(
ref_is_prime64
(next),
"next_prime is prime"
);
150
if
(next >
n
+ 1) {
151
for
(
ulong
k
=
n
+ 1;
k
< next; ++
k
)
TEST_CHECK_MSG
(!
ref_is_prime64
(
k
),
"next_prime no gap prime"
);
152
}
153
ulong
p =
lmmp_prev_prime_ulong_
(
n
);
154
TEST_CHECK_MSG
(p > 0,
"prev_prime nonzero for n >= 2"
);
155
if
(p > 0) {
156
TEST_CHECK_MSG
(
ref_is_prime64
(p),
"prev_prime is prime"
);
157
TEST_CHECK_MSG
(p <=
n
,
"prev_prime <= n"
);
158
for
(
ulong
k
= p + 1;
k
<=
n
; ++
k
)
TEST_CHECK_MSG
(!
ref_is_prime64
(
k
),
"prev_prime no gap prime"
);
159
}
160
}
161
}
162
163
TEST_CASE
(
"numth/prime"
, mulmod_powmod) {
164
u64
seed = 0x2cbea9127ca8019full;
165
for
(
int
i = 0; i < 400; ++i) {
166
ulong
mod = xorshift64(&seed) | 3;
// 避免过小且保证奇
167
ulong
a = xorshift64(&seed) % mod;
168
ulong
b = xorshift64(&seed) % mod;
169
ulong
q = 0;
170
ulong
r =
lmmp_mulmod_ulong_
(a, b, mod, &q);
171
/* q*mod + r == a*b(mullh 独立重建全积与商积) */
172
mp_limb_t
prod
[2], qm[2];
173
lmmp_mullh_
(a, b,
prod
);
174
lmmp_mullh_
(q, mod, qm);
175
mp_limb_t
lo
= qm[0] + r;
176
mp_limb_t
cy =
lo
< qm[0] ? 1 : 0;
177
mp_limb_t
hi = qm[1] + cy;
178
TEST_CHECK_MSG
(hi ==
prod
[1] &&
lo
==
prod
[0],
"mulmod relation"
);
179
TEST_CHECK_MSG
(r < mod,
"mulmod rem bound"
);
180
}
181
182
for
(
int
i = 0; i < 300; ++i) {
183
u32
mod = (
u32
)(xorshift64(&seed) | 3);
184
u32
base = (
u32
)(xorshift64(&seed) % mod);
185
ulong
exp = xorshift64(&seed) & 0xffff;
186
u32
r =
lmmp_powmod_uint_odd_
(base, exp, mod);
187
TEST_CHECK_EQ
(r, (
u32
)
mod_pow64
(base, exp, mod));
188
}
189
190
for
(
int
i = 0; i < 300; ++i) {
191
ulong
mod = xorshift64(&seed) | 3;
192
ulong
base = xorshift64(&seed) % mod;
193
ulong
exp = xorshift64(&seed) & 0xffff;
194
ulong
r =
lmmp_powmod_ulong_odd_
(base, exp, mod);
195
TEST_CHECK_EQ
(r,
mod_pow64
(base, exp, mod));
196
}
197
}
198
199
void
test_prime_uint
(
void
) {
200
TEST_RUN
(
"numth/prime"
, is_prime_uint_ulong_notrial);
201
TEST_RUN
(
"numth/prime"
, is_prime_u32_tiers);
202
TEST_RUN
(
"numth/prime"
, next_prev_prime);
203
TEST_RUN
(
"numth/prime"
, mulmod_powmod);
204
}
k
#define k
prod
#define prod
lmmp_mullh_
#define lmmp_mullh_
定义
inlines.h:166
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
u32
uint u32
定义
lmmp_test_utils.h:34
u64
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
lmmp_test_utils.h:33
lmmpn.h
t
#define t
s
#define s
n
#define n
lo
#define lo
cases.h
test_prime_uint
void test_prime_uint(void)
定义
test_prime_uint.c:199
numth.h
lmmp_powmod_uint_odd_
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
定义
powmod_ulong.c:94
lmmp_prev_prime_ulong_
ulong lmmp_prev_prime_ulong_(ulong n)
小于等于n的上一个素数
定义
is_prime_ulong.c:397
lmmp_is_prime_uint_
bool lmmp_is_prime_uint_(uint n)
判断素数
定义
is_prime_uint.c:124
lmmp_powmod_ulong_odd_
ulong lmmp_powmod_ulong_odd_(ulong base, ulong exp, ulong mod)
计算 base^exp 对 mod 取模
定义
powmod_ulong.c:118
lmmp_mulmod_ulong_
ulong lmmp_mulmod_ulong_(ulong a, ulong b, ulong mod, ulongp q)
计算两个无符号整数的乘积,对mod取模,商放入 q 中
lmmp_is_prime_ulong_notrial_
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
定义
is_prime_ulong.c:257
lmmp_is_prime_ulong_
bool lmmp_is_prime_ulong_(ulong n)
判断素数
定义
is_prime_ulong.c:345
ulong
uint64_t ulong
定义
numth.h:39
lmmp_next_prime_ulong_
ulong lmmp_next_prime_ulong_(ulong n)
大于n的下一个素数
定义
is_prime_ulong.c:375
ARRAY_SIZE
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
perf.h:40
prime_ref.h
ref_is_prime64
static bool ref_is_prime64(u64 n)
定义
prime_ref.h:57
ref_is_prime32
static bool ref_is_prime32(u32 n)
定义
prime_ref.h:85
mod_pow64
static u64 mod_pow64(u64 a, u64 e, u64 mod)
定义
prime_ref.h:46
TEST_CHECK
#define TEST_CHECK(cond)
定义
test.h:37
TEST_CHECK_MSG
#define TEST_CHECK_MSG(cond, msg)
定义
test.h:38
TEST_CASE
#define TEST_CASE(category, name)
定义
test.h:35
TEST_CHECK_EQ
#define TEST_CHECK_EQ(a, b)
定义
test.h:39
TEST_RUN
#define TEST_RUN(category, name)
定义
test.h:36
src
lmmp
numth
test
test_prime_uint.c
生成于
, 为 LMMP使用
1.18.0