LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
proth.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 "
prime_pool.h
"
24
25
/* ---- Proth 形状:N = k*2^t + 1(k<=2^32) ---- */
26
27
static
mp_size_t
proth_limbs
(
mp_ptr
dst,
uint
k
,
uint
t
) {
28
mp_size_t
n
= (
mp_size_t
)
t
/ 64 + 2;
29
lmmp_zero
(dst,
n
+ 1);
30
uint
sh =
t
% 64;
31
dst[
t
/ 64] |= (
mp_limb_t
)
k
<< sh;
32
if
(sh != 0) dst[
t
/ 64 + 1] |= (
mp_limb_t
)
k
>> (64 - sh);
33
dst[0] |= 1;
34
while
(
n
> 1 && dst[
n
- 1] == 0)
n
--;
35
return
n
;
36
}
37
38
typedef
struct
{
39
mp_ptr
a
;
/* cnt * stride,元素为 k*2^t+1 */
40
uint
ks
[8];
/* 各元素的 k */
41
mp_size_t
nn
[8];
/* 各元素规范化 limb 数 */
42
mp_size_t
stride
;
43
int
cnt
;
44
}
ProthPool
;
45
46
/* want_prime:Proth 素数池(被测函数搜索);否则试除幸存合数池 */
47
static
ProthPool
pool_proth
(
uint
t
,
int
cnt,
bool
want_prime) {
48
ProthPool
p;
49
p.
stride
= (
mp_size_t
)
t
/ 64 + 3;
50
p.
cnt
= cnt;
51
p.
a
= alloc_limbs((
size_t
)p.
stride
* cnt);
52
uint
k
= 3;
53
for
(
int
i = 0; i < cnt; i++) {
54
for
(;;) {
55
mp_size_t
nn =
proth_limbs
(p.
a
+ p.
stride
* i,
k
,
t
);
56
bool
ok = want_prime ?
lmmp_is_prothprime_
(
k
, (
mp_size_t
)
t
)
57
: !small_factor_q(p.
a
+ p.
stride
* i, nn);
58
if
(ok)
break
;
59
k
+= 2;
60
}
61
p.
ks
[i] =
k
;
62
p.
nn
[i] =
proth_limbs
(p.
a
+ p.
stride
* i,
k
,
t
);
63
k
+= 2;
64
}
65
return
p;
66
}
67
68
static
double
bench_is_prothprime
(
uint
t
,
bool
prime_pool,
const
bench_options
*o) {
69
if
(
t
< 1)
t
= 1;
/* is_prothprime_ 契约 n>0 */
70
ProthPool
p =
pool_proth
(
t
, 8, prime_pool);
71
size_t
idx = 0;
72
double
us;
73
BENCH_MEASURE
(us, o, bench_sink += (
mp_limb_t
)
lmmp_is_prothprime_
(p.
ks
[idx++ % p.
cnt
],
t
););
74
lmmp_free
(p.
a
);
75
return
us;
76
}
77
78
static
double
bench_is_prime_n_proth
(
uint
t
,
int
strength,
bool
prime_pool,
const
bench_options
*o) {
79
if
(
t
< 1)
t
= 1;
/* 同 bench_is_prothprime:契约 n>0 */
80
ProthPool
p =
pool_proth
(
t
, 8, prime_pool);
81
size_t
idx = 0;
82
double
us;
83
BENCH_MEASURE
(us, o,
84
bench_sink += (
mp_limb_t
)
lmmp_is_prime_n_
(p.
a
+ p.
stride
* (idx % p.
cnt
),
85
p.
nn
[idx % p.
cnt
], strength);
86
idx++;
87
);
88
lmmp_free
(p.
a
);
89
return
us;
90
}
91
92
/*
93
Proth 形状:lmmp_is_prothprime_ 单梯子定理判决 vs lmmp_is_prime_n_
94
通用分档(同池对照)。素数池 = 分档全轮完整执行的最坏情形(Proth
95
路径的收益所在);合数池 = 试除幸存者,两路径都支付完整梯子,
96
用于确认 Proth 路径在合数侧无回归。素数池构造昂贵,仅取 <=16 limb。
97
*/
98
static
void
run_proth
(
void
) {
99
const
uint
TS[] = {480, 992};
100
for
(
size_t
i = 0; i <
ARRAY_SIZE
(TS); ++i) {
101
uint
t
= TS[i];
102
char
buf[64];
103
snprintf(buf,
sizeof
(buf),
"is_prothprime prime(t=%u)"
,
t
);
104
report(buf,
bench_is_prothprime
(
t
,
true
, &bench_default), 0);
105
snprintf(buf,
sizeof
(buf),
"is_prime_n s4 proth-prime(t=%u)"
,
t
);
106
report(buf,
bench_is_prime_n_proth
(
t
, 4,
true
, &bench_default), 0);
107
}
108
const
uint
TC[] = {2016, 4032};
109
for
(
size_t
i = 0; i <
ARRAY_SIZE
(TC); ++i) {
110
uint
t
= TC[i];
111
char
buf[64];
112
snprintf(buf,
sizeof
(buf),
"is_prothprime composite(t=%u)"
,
t
);
113
report(buf,
bench_is_prothprime
(
t
,
false
, &bench_default), 0);
114
snprintf(buf,
sizeof
(buf),
"is_prime_n s4 proth-composite(t=%u)"
,
t
);
115
report(buf,
bench_is_prime_n_proth
(
t
, 4,
false
, &bench_default), 0);
116
}
117
}
118
119
int
main
(
void
) {
120
setvbuf(stdout, NULL, _IONBF, 0);
121
lmmp_global_init
();
122
puts(
"[numth/prime/proth]"
);
123
run_proth
();
124
lmmp_global_deinit
();
125
return
0;
126
}
k
#define k
main
int main(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
main.c:26
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
lmmp_zero
#define lmmp_zero(dst, n)
定义
lmmp.h:476
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
lmmp_free
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
定义
memory.c:437
lmmp_global_init
void lmmp_global_init(void)
全局初始化函数(线程局部的)
定义
global.c:58
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmp_global_deinit
void lmmp_global_deinit(void)
全局释放函数(线程局部的)
定义
global.c:65
t
#define t
n
#define n
uint
uint32_t uint
定义
numth.h:38
lmmp_is_prime_n_
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
定义
is_prime_n.c:646
lmmp_is_prothprime_
int lmmp_is_prothprime_(uint k, mp_size_t n)
Proth 数 k*2^n+1 的素性判定(普罗斯定理)
定义
is_prime_n.c:768
ARRAY_SIZE
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
perf.h:40
BENCH_MEASURE
#define BENCH_MEASURE(result, options,...)
定义
perf.h:93
bench_options
定义
perf.h:44
prime_pool.h
pool_proth
static ProthPool pool_proth(uint t, int cnt, bool want_prime)
定义
proth.c:47
proth_limbs
static mp_size_t proth_limbs(mp_ptr dst, uint k, uint t)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
proth.c:27
bench_is_prime_n_proth
static double bench_is_prime_n_proth(uint t, int strength, bool prime_pool, const bench_options *o)
定义
proth.c:78
ProthPool::stride
mp_size_t stride
定义
proth.c:42
run_proth
static void run_proth(void)
定义
proth.c:98
bench_is_prothprime
static double bench_is_prothprime(uint t, bool prime_pool, const bench_options *o)
定义
proth.c:68
ProthPool::a
mp_ptr a
定义
proth.c:39
ProthPool::nn
mp_size_t nn[8]
定义
proth.c:41
ProthPool::cnt
int cnt
定义
proth.c:43
ProthPool::ks
uint ks[8]
定义
proth.c:40
ProthPool
定义
proth.c:38
src
lmmp
numth
perf
proth.c
生成于
, 为 LMMP使用
1.18.0