LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
37TEST_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;
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;
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
62TEST_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
121TEST_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
137void 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}
#define k
uint64_t mp_size_t
定义 lmmp.h:93
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
#define n
void test_proth(void)
int lmmp_is_prothprime_(uint k, mp_size_t n)
Proth 数 k*2^n+1 的素性判定(普罗斯定理)
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static bool proth_cert_g(uint k, int t, int nbase)
static bool ref_is_prime64(u64 n)
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_RUN(category, name)
定义 test.h:36