LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
test_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
/* ============ lmmp_is_prothprime_:普罗斯定理单梯子确定性判决 ============
24
25
- 小域(N < 2^64):ref_is_prime64 穷举 + 随机,双向硬断言;
26
- 驱动域(N >= 2^64):proth_cert_g 证书器走 lmmp_powmod_ 通用梯子,
27
与被测路径实现独立;
28
- 构造合数(硬断言 false):Fermat 数、奇指数代数分解、
29
小因子 Jacobi=0 出口。
30
*/
31
32
#include "
lmmp/lmmpn.h
"
33
#include "
lmmp/numth.h
"
34
#include "
cases.h
"
35
#include "
prime_ref.h
"
36
37
TEST_CASE
(
"numth/proth"
, is_prothprime_small) {
38
u64
seed = 0x70726f7468313233ull;
/* "proth123" */
39
/* 穷举:奇 k ∈ [1,399] × n ∈ [1,20](契约域 k>0 奇、n>0) */
40
for
(
u32
k
= 1;
k
< 400;
k
+= 2) {
41
for
(
u32
n
= 1;
n
<= 20; ++
n
) {
42
u64
N = ((
u64
)
k
<<
n
) + 1;
43
TEST_CHECK_MSG
(
lmmp_is_prothprime_
(
k
, (
mp_size_t
)
n
) == (
ref_is_prime64
(N) ? 1 : 0),
44
"proth small exhaustive"
);
45
}
46
}
47
/* 随机:全域 32 位奇 k × n ∈ [1,32](N < 2^64 不溢出) */
48
for
(
int
i = 0; i < 800; ++i) {
49
u32
k
= (
u32
)xorshift64(&seed) | 1;
50
u32
n
= 1 + (
u32
)(xorshift64(&seed) % 32);
51
u64
N = ((
u64
)
k
<<
n
) + 1;
52
TEST_CHECK_MSG
(
lmmp_is_prothprime_
(
k
, (
mp_size_t
)
n
) == (
ref_is_prime64
(N) ? 1 : 0),
53
"proth small random"
);
54
}
55
/* 跨 64 位边界:ne+bitlen(kk)=64 走 ulong 档 */
56
TEST_CHECK_MSG
(
lmmp_is_prothprime_
(1, 63) == (
ref_is_prime64
((1ull << 63) + 1) ? 1 : 0),
57
"proth ulong boundary 2^63+1"
);
58
TEST_CHECK_MSG
(
lmmp_is_prothprime_
(3, 62) == (
ref_is_prime64
((3ull << 62) + 1) ? 1 : 0),
59
"proth ulong boundary 3*2^62+1"
);
60
}
61
62
TEST_CASE
(
"numth/proth"
, is_prothprime_driver) {
63
u64
seed = 0x6b33706137686975ull;
64
/* 中尺寸双向对拍:t=33/34 顶值 k 使 nn=2(双 limb 蒙域),65 起恒
65
驱动域;k=3 分量保证 Jacobi=+1 跳过路径 */
66
const
int
t_values[] = {33, 34, 40, 65, 100, 150};
67
for
(
size_t
t_index = 0; t_index <
ARRAY_SIZE
(t_values); ++t_index) {
68
int
t
= t_values[t_index];
69
for
(
int
i = 0; i < 12; ++i) {
70
u32
k
;
71
if
(i < 3)
k
= 3;
72
else
if
(i < 6)
k
= 0xffffffffu;
73
else
k
= (
u32
)(xorshift64(&seed) | 1);
74
int
lm =
lmmp_is_prothprime_
(
k
,
t
);
75
bool
ce =
proth_cert_g
(
k
,
t
, 17);
76
if
(
t
>= 64)
/* 定理驱动域:精确 0/1(契约 k 奇 ⟹ ne = t) */
77
TEST_CHECK_MSG
(lm == (ce ? 1 : 0),
"proth driver exact (ne>=64)"
);
78
else
/* 双 limb/ulong 段:素数非零,合数 0(BPSW 误判 2 容许) */
79
TEST_CHECK_MSG
(ce ? lm != 0 : (lm == 0 || lm == 2),
80
"proth two-limb tri-state (ne<64)"
);
81
}
82
}
83
84
/* 大尺寸:被测预筛(单梯子),命中即证书复核;抽样合数反向验证
85
(证书有 ⟹ 被测必 true,硬断言)。found 硬断言仅限密度充裕档 */
86
struct
proth_case {
int
t
;
int
cap;
bool
hard; } bigs[] = {
87
{200, 400,
true
}, {384, 200,
false
}, {521, 150,
false
},
88
{1000, 100,
false
}, {2048, 60,
false
},
89
};
90
/* 固定正例锚点(证书已知素):被测恒返回 0 的回归在抽样合数分支
91
(k&63==3)大概率无素例可撞、found 硬断言又只保 t=200 档 */
92
TEST_CHECK_MSG
(
lmmp_is_prothprime_
(233, 521) == 1,
"proth anchor 233*2^521+1 prime"
);
93
TEST_CHECK_MSG
(
proth_cert_g
(233, 521, 17),
"proth anchor 233*2^521+1 certified"
);
94
TEST_CHECK_MSG
(
lmmp_is_prothprime_
(13, 1000) == 1,
"proth anchor 13*2^1000+1 prime"
);
95
TEST_CHECK_MSG
(
proth_cert_g
(13, 1000, 17),
"proth anchor 13*2^1000+1 certified"
);
96
for
(
size_t
b_index = 0; b_index <
ARRAY_SIZE
(bigs); ++b_index) {
97
const
struct
proth_case b = bigs[b_index];
98
int
found = 0;
99
for
(
u32
k
= 3; (int)
k
< 2 * b.cap;
k
+= 2) {
100
if
(
lmmp_is_prothprime_
(
k
, b.t)) {
101
TEST_CHECK_MSG
(
proth_cert_g
(
k
, b.t, 17),
"proth big prime certified"
);
102
found++;
103
}
else
if
((
k
& 63) == 3) {
104
TEST_CHECK_MSG
(!
proth_cert_g
(
k
, b.t, 17),
"proth big composite consistent"
);
105
}
106
}
107
if
(b.hard)
TEST_CHECK_MSG
(found >= 1,
"proth big prime found"
);
108
}
109
110
#ifdef NDEBUG
111
/* 梅森折叠 REDC 档(nn=313 >= REDC_MERSENNE_THRESHOLD=309):单例,
112
秒级成本,仅 release 执行。合数时以单基短证书反向验证 */
113
bool
lm =
lmmp_is_prothprime_
(3, 19969) != 0;
114
if
(lm)
115
TEST_CHECK_MSG
(
proth_cert_g
(3, 19969, 17),
"proth fold prime certified"
);
116
else
117
TEST_CHECK_MSG
(!
proth_cert_g
(3, 19969, 1),
"proth fold composite consistent"
);
118
#endif
119
}
120
121
TEST_CASE
(
"numth/proth"
, is_prothprime_constructed) {
122
/* Fermat 合数(k=1,已证 F6..F9 均合):nn 覆盖 2/3/5/9 limb */
123
const
int
t_values[] = {64, 128, 256, 512};
124
for
(
size_t
t_index = 0; t_index <
ARRAY_SIZE
(t_values); ++t_index) {
125
int
t
= t_values[t_index];
126
TEST_CHECK_MSG
(!
lmmp_is_prothprime_
(1,
t
),
"fermat composite"
);
127
}
128
129
/* 奇指数代数分解:2^odd ≡ -1 (mod 3) ⟹ 3 | 2^189+1 */
130
TEST_CHECK_MSG
(!
lmmp_is_prothprime_
(1, 189),
"algebraic factor 3"
);
131
132
/* 小因子 Jacobi=0 出口:t 偶 ⟹ 2^t ≡ 1 (mod 3),k ≡ 2 (mod 3) 即
133
3 | k*2^t+1,首个 a=3 即命中 gcd 出口 */
134
TEST_CHECK_MSG
(!
lmmp_is_prothprime_
(5, 100),
"jacobi-zero factor 3"
);
135
}
136
137
void
test_proth
(
void
) {
138
TEST_RUN
(
"numth/proth"
, is_prothprime_small);
139
TEST_RUN
(
"numth/proth"
, is_prothprime_driver);
140
TEST_RUN
(
"numth/proth"
, is_prothprime_constructed);
141
}
k
#define k
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
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
n
#define n
cases.h
test_proth
void test_proth(void)
定义
test_proth.c:137
numth.h
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
prime_ref.h
proth_cert_g
static bool proth_cert_g(uint k, int t, int nbase)
定义
prime_ref.h:140
ref_is_prime64
static bool ref_is_prime64(u64 n)
定义
prime_ref.h:57
TEST_CHECK_MSG
#define TEST_CHECK_MSG(cond, msg)
定义
test.h:38
TEST_CASE
#define TEST_CASE(category, name)
定义
test.h:35
TEST_RUN
#define TEST_RUN(category, name)
定义
test.h:36
src
lmmp
numth
test
test_proth.c
生成于
, 为 LMMP使用
1.18.0