LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_prime_n.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/* >128 位档素性检验:lmmp_is_strong_lucas_ / lmmp_is_prime_n_ 判定类测试
24 (不与参考逐值对拍):
25
26 素数侧(不能错判:错拒素数即失败,硬断言)
27 - 已证明 Mersenne 素数 M_p = 2^p-1(p ∈ {521,607,1279,4423};release
28 额外跑 p=19937 覆盖梅森折叠 REDC 层);
29 - Proth 定理运行时认证(证书经 lmmp_powmod_ 独立梯子)。
30 合数侧(允许概率性误判(返回"素数"合法);不允许崩溃或非法返回值)
31 - 构造性 SPRP-2:Mersenne 合数、Fermat 数、Carmichael 对抗语料;
32 - p1*p2 / p1*p2*p3 乘积(素因子均为已证素数或确定性 u64 素数)。
33 确定性拒绝侧(硬断言 ==0)
34 - 偶数;小因子乘积(因子 <= 全档最小试除上界 100;另以 70/312 limb
35 乘积覆盖 4/8 链试除腿,312 limb*9973 于 s=7 全块扫后末块命中);
36 - 素数平方:D 搜索对平方数恒 (D|n) = +1 不命中 -1,必行至
37 Dabs==17 的延迟 perfsqr(或素因子整除 D 的 gcd 出口);
38 - gcd(|D|,n) > 1:5|n 的乘积在首个 D=5 处 (5|n)=0 命中 j==0。
39*/
40
41#include "lmmp/lmmpn.h"
42#include "lmmp/numth.h"
43#include "cases.h"
44#include "prime_ref.h"
45
46/* 已证明素数:错拒即失败(不能错判)。全档位轮数差异已由小尺寸覆盖,
47 此处抽 {0,4,7}(MR-only / BPSW / 最重混合档)控制耗时 */
48TEST_CASE("numth/prime", is_prime_n_proven_primes) {
49 mp_limb_t buf[512];
50 for (size_t p_index = 0; p_index < ARRAY_SIZE(MP_EXP); ++p_index) {
51 int p = MP_EXP[p_index];
52 mp_size_t nn = mersenne_limbs(buf, p);
53 const int s_values[] = {0, 4, 7};
54 for (size_t s_index = 0; s_index < ARRAY_SIZE(s_values); ++s_index) {
55 int s = s_values[s_index];
56 TEST_CHECK_MSG(lmmp_is_prime_n_(buf, nn, s) == 2, "proven mersenne prime tiers");
57 }
58 }
59#ifdef NDEBUG
60 /* 梅森折叠 REDC 层(312 limb >= REDC_MERSENNE_THRESHOLD=309):单档 BPSW,
61 秒级成本,仅 release 执行 */
63 TEST_CHECK_MSG(lmmp_is_prime_n_(buf, nn, 4) == 2, "proven mersenne prime fold layer");
64#endif
65}
66
67/* notrial 变体:判定集合与全函数精确一致(试除仅承担合数侧廉价早拒)。
68 小因子合数在全函数走试除拒、在 notrial 走 MR 拒,结论须相同;
69 随机奇数流按档位全量对照 */
70TEST_CASE("numth/prime", is_prime_n_notrial_agree) {
71 const int STR[] = {0, 4, 7};
72 mp_limb_t p[512], t1[512];
73
74 /* 已证素数(Mersenne):notrial 与全函数同为 2 */
75 mp_size_t pn = mersenne_limbs(p, 521);
76 for (size_t s_index = 0; s_index < ARRAY_SIZE(STR); ++s_index) {
77 int s = STR[s_index];
78 TEST_CHECK_MSG(lmmp_is_prime_n_notrial_(p, pn, s) == lmmp_is_prime_n_(p, pn, s), "proven prime agree");
79 }
80
81 /* 偶数:同拒(notrial 的奇偶短路) */
82 lmmp_copy(t1, p, pn);
83 lmmp_dec(t1);
84 for (size_t s_index = 0; s_index < ARRAY_SIZE(STR); ++s_index) {
85 int s = STR[s_index];
86 TEST_CHECK_MSG(lmmp_is_prime_n_notrial_(t1, pn, s) == lmmp_is_prime_n_(t1, pn, s), "even agree");
87 }
88
89 /* 小因子 3 / 97:全函数试除拒,notrial MR 拒 */
90 const u64 f_values[] = {3ull, 97ull};
91 for (size_t f_index = 0; f_index < ARRAY_SIZE(f_values); ++f_index) {
92 u64 f = f_values[f_index];
93 mp_limb_t fb[1] = {(mp_limb_t)f};
94 lmmp_mul_(t1, p, pn, fb, 1);
95 mp_size_t fn = limbs_norm(t1, pn + 1);
96 for (size_t s_index = 0; s_index < ARRAY_SIZE(STR); ++s_index) {
97 int s = STR[s_index];
99 "small factor agree");
100 }
101 }
102
103 /* 随机奇数流(3L/8L,含素数与各类合数)全量对照 */
104 u64 seed = 0x6e6f747269616c6eull;
105 const mp_size_t n_values[] = {3, 8};
106 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
107 mp_size_t n = n_values[n_index];
108 mp_ptr a = alloc_limbs(n);
109 for (int i = 0; i < 60; ++i) {
110 for (mp_size_t j = 0; j < n; ++j) a[j] = xorshift64(&seed);
111 a[0] |= 1;
112 for (size_t s_index = 0; s_index < ARRAY_SIZE(STR); ++s_index) {
113 int s = STR[s_index];
115 "random odd agree");
116 }
117 }
118 lmmp_free(a);
119 }
120}
121
122/* 确定性拒绝:偶数 / 小因子(<= 全档最小试除上界 100)/ 素数平方(Lucas 半部) */
123TEST_CASE("numth/prime", is_prime_n_deterministic_reject) {
124 mp_limb_t p[512], t1[512], t2[1024];
125 mp_size_t pn = mersenne_limbs(p, 521);
126
127 /* 偶数:M521 - 1(奇偶位翻转,位数不变) */
128 lmmp_copy(t1, p, pn);
129 lmmp_dec(t1);
130 for (int s = 0; s <= 7; ++s)
131 TEST_CHECK_MSG(lmmp_is_prime_n_(t1, pn, s) == 0, "even rejected");
132
133 /* 小因子 3 / 97:试除必拦(全档上界 >= 100) */
134 const u64 f_values[] = {3ull, 97ull};
135 for (size_t f_index = 0; f_index < ARRAY_SIZE(f_values); ++f_index) {
136 u64 f = f_values[f_index];
137 mp_limb_t fb[1] = {(mp_limb_t)f};
138 lmmp_mul_(t1, p, pn, fb, 1);
139 mp_size_t fn = limbs_norm(t1, pn + 1);
140 for (int s = 0; s <= 7; ++s)
141 TEST_CHECK_MSG(lmmp_is_prime_n_(t1, fn, s) == 0, "small factor rejected");
142 }
143
144 /* 小因子 @ 4 链档(70 limb,尾 t=2 非对齐):M4423*3 首块即拦 */
145 {
146 mp_size_t pn4 = mersenne_limbs(p, 4423);
147 mp_limb_t fb[1] = {3ull};
148 lmmp_mul_(t1, p, pn4, fb, 1);
149 mp_size_t fn = limbs_norm(t1, pn4 + 1);
150 for (int s = 0; s <= 7; ++s)
151 TEST_CHECK_MSG(lmmp_is_prime_n_(t1, fn, s) == 0, "small factor k4 leg rejected");
152 }
153
154 /* 小因子 9973 @ 8 链档(312 limb=39*8,尾 t=0 零长度):仅 s=7(上界
155 10000)确定性拦截,全块无幸存后于末块命中——8 链试除腿全块循环覆盖 */
156 {
157 mp_size_t pn8 = mersenne_limbs(p, 19937);
158 mp_limb_t fb[1] = {9973ull};
159 lmmp_mul_(t2, p, pn8, fb, 1);
160 mp_size_t fn = limbs_norm(t2, pn8 + 1);
161 TEST_CHECK_MSG(lmmp_is_prime_n_(t2, fn, 7) == 0, "small factor k8 leg full sweep rejected");
162 }
163
164 /* 素数平方:s >= 4 的 Lucas 半部(D 搜索必行至延迟 perfsqr/gcd 出口)
165 硬断言 ==0;s <= 3 的纯 MR 轮按合数容许域处理(允许误判) */
166 const int pe_values[] = {521, 607};
167 for (size_t pe_index = 0; pe_index < ARRAY_SIZE(pe_values); ++pe_index) {
168 int pe = pe_values[pe_index];
169 mp_size_t qn = mersenne_limbs(t1, pe);
170 lmmp_sqr_(t2, t1, qn);
171 mp_size_t sn = limbs_norm(t2, 2 * qn);
172 for (int s = 0; s <= 7; ++s) {
173 int r = lmmp_is_prime_n_(t2, sn, s);
174 if (s >= 4)
175 TEST_CHECK_MSG(r == 0, "prime square rejected by lucas tiers");
176 else
177 TEST_CHECK_MSG(r == 0 || r == 2, "prime square at MR tiers (misjudge allowed)");
178 }
179 }
180}
181
182/*
183 强 Lucas 单测:素数必过(定理级,硬断言);平方数与 gcd(|D|,n)>1
184 必拒(D 搜索必经出口,硬断言);一般构造合数允许误判
185*/
186TEST_CASE("numth/prime", is_strong_lucas_n) {
187 mp_limb_t p[512], q[512], t1[1024], t2[1024];
188
189 /* 已证素数必过(Mersenne,各 D 命中深度) */
190 for (size_t e_index = 0; e_index < ARRAY_SIZE(MP_EXP); ++e_index) {
191 int e = MP_EXP[e_index];
192 mp_size_t pn = mersenne_limbs(p, e);
193 TEST_CHECK_MSG(lmmp_is_strong_lucas_(p, pn) == 1, "lucas proven prime pass");
194 }
195
196 /* 素数平方必拒 */
197 const int e_values[] = {521, 607};
198 for (size_t e_index = 0; e_index < ARRAY_SIZE(e_values); ++e_index) {
199 int e = e_values[e_index];
200 mp_size_t qn = mersenne_limbs(q, e);
201 lmmp_sqr_(t1, q, qn);
202 mp_size_t sn = limbs_norm(t1, 2 * qn);
203 TEST_CHECK_MSG(lmmp_is_strong_lucas_(t1, sn) == 0, "lucas square reject");
204 }
205
206 /* gcd(|D|,n) > 1 必拒:5|n 的乘积在首个 D=5 处 (5|n)=0 → j==0 */
207 mp_size_t pn = mersenne_limbs(p, 521);
208 const u64 f_values[] = {5ull, 15ull, 35ull};
209 for (size_t f_index = 0; f_index < ARRAY_SIZE(f_values); ++f_index) {
210 u64 f = f_values[f_index];
211 mp_limb_t fb[1] = {(mp_limb_t)f};
212 lmmp_mul_(t1, p, pn, fb, 1);
213 mp_size_t fn = limbs_norm(t1, pn + 1);
214 TEST_CHECK_MSG(lmmp_is_strong_lucas_(t1, fn) == 0, "lucas gcd-D reject");
215 }
216
217 /* 非平方含平方因子(p^2*q / p^3)与一般构造合数:允许误判(==1),
218 覆盖阶梯终点判据与返回值合法性 */
219 {
220 mp_size_t qn = mersenne_limbs(q, 521);
221 mp_size_t rn = mersenne_limbs(p, 607);
222 lmmp_sqr_(t2, q, qn); /* p^2 */
223 mp_size_t sn = limbs_norm(t2, 2 * qn);
224 lmmp_mul_(t1, t2, sn, p, rn); /* p^2 * q */
225 int r = lmmp_is_strong_lucas_(t1, limbs_norm(t1, sn + rn));
226 TEST_CHECK_MSG(r == 0 || r == 1, "lucas p^2*q (misjudge allowed)");
227 lmmp_mul_(t1, t2, sn, q, qn); /* p^3 */
228 r = lmmp_is_strong_lucas_(t1, limbs_norm(t1, sn + qn));
229 TEST_CHECK_MSG(r == 0 || r == 1, "lucas p^3 (misjudge allowed)");
230
231 mp_size_t nn = k2t_limbs(t1, 128, 1, 1); /* F7 = 2^128+1 */
232 r = lmmp_is_strong_lucas_(t1, nn);
233 TEST_CHECK_MSG(r == 0 || r == 1, "lucas F7 (misjudge allowed)");
234
235 nn = mersenne_limbs(t1, 137); /* M137(Mersenne 合数) */
236 r = lmmp_is_strong_lucas_(t1, nn);
237 TEST_CHECK_MSG(r == 0 || r == 1, "lucas mersenne composite (misjudge allowed)");
238 }
239}
240
241/*
242 构造性 SPRP-2 与 Carmichael 对抗:基 2 轮构造性放行,随机轮/Lucas 按
243 概率拒判——允许误判(返回 2 合法),仅拒绝崩溃与非法返回值。
244*/
245TEST_CASE("numth/prime", is_prime_n_constructive_spsp) {
246 const u64 n_values[] = {2047ull, 3277ull, 4033ull, 4681ull, 8321ull, 15841ull, 29341ull};
247 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
248 u64 n = n_values[n_index];
249 TEST_CHECK_MSG(lmmp_is_prime_ulong_(n) == false, "classic spsp2 rejected (ulong)");
250 TEST_CHECK_MSG(lmmp_is_prime_ulong_notrial_(n) == false, "classic spsp2 rejected (notrial)");
251 }
252
253 mp_limb_t buf[512];
254 /* Mersenne 合数(素指数 p ∈ (127,521)):2^d ≡ 1 (mod M_p) 构造性
255 通过基 2,只能由随机轮(或试除)拒判 */
256 for (size_t p_index = 0; p_index < ARRAY_SIZE(MC_EXP); ++p_index) {
257 int p = MC_EXP[p_index];
258 mp_size_t nn = mersenne_limbs(buf, p);
259 for (int s = 0; s <= 7; ++s) {
260 int r = lmmp_is_prime_n_(buf, nn, s);
261 if (p == 131 && s >= 1)
262 TEST_CHECK_MSG(r == 0, "M131 factor 263 caught by trial bound >=300");
263 else
264 TEST_CHECK_MSG(r == 0 || r == 2, "mersenne composite (misjudge allowed)");
265 }
266 }
267
268 /* Fermat 数 F7 = 2^128+1、F8 = 2^256+1(已知合数;d=1 平方链末端
269 2^(2^k) ≡ -1 构造性通过基 2) */
270 const int k_values[] = {7, 8};
271 for (size_t k_index = 0; k_index < ARRAY_SIZE(k_values); ++k_index) {
272 int k = k_values[k_index];
273 mp_size_t nn = k2t_limbs(buf, 1 << k, 1, 1);
274 for (int s = 0; s <= 7; ++s) {
275 int r = lmmp_is_prime_n_(buf, nn, s);
276 TEST_CHECK_MSG(r == 0 || r == 2, "fermat composite (misjudge allowed)");
277 }
278 }
279
280 /* Carmichael 对抗语料(Korselt 线性同余 + CRT 构造,~190.6 bit):
281 p1p2p3 全 ≡ 3 (mod 8)、v2(n-1) = 1,2^((n-1)/2) ≡ -1 (mod n) 构造性
282 通过基 2;随机基底单轮通过率 = 1/4(Monier-Rabin 最坏形态) */
283 struct carmichael_case {
284 mp_limb_t l[3];
285 const char* fac;
286 } carm[] = {
287 {{0xff15f6ff84b4f0f3ull, 0xe106b441973e19bfull, 0x0e7000000110a524ull},
288 "3458764513840342771*8070450532294133131*12682136550747923491"},
289 {{0x66fe7ee3b284e7c3ull, 0x310b7aaab318c4a5ull, 0x0e7000000164c3bfull},
290 "3458764513846452259*8070450532308388603*12682136550770324947"},
291 {{0x3805ef3326bcc70bull, 0x7928975dd02cf97dull, 0x0e700000029ee088ull},
292 "3458764513869265819*8070450532361620243*12682136550853974667"},
293 };
294 for (size_t c_index = 0; c_index < ARRAY_SIZE(carm); ++c_index) {
295 const struct carmichael_case c = carm[c_index];
296 for (int s = 0; s <= 7; ++s) {
297 int r = lmmp_is_prime_n_(c.l, 3, s);
298 TEST_CHECK_MSG(r == 0 || r == 2, "carmichael adversarial (misjudge allowed)");
299 }
300 }
301}
302
303/* p1*p2 / p1*p2*p3 乘积合数:素因子均为已证素数或确定性 u64 素数,
304 无小因子(试除不可达),允许概率性误判 */
305TEST_CASE("numth/prime", is_prime_n_product_composites) {
306 mp_limb_t a[512], b[512], t1[1024], t2[1024];
307 mp_size_t an = mersenne_limbs(a, 521); /* 9 limb */
308 mp_size_t bn = mersenne_limbs(b, 607); /* 10 limb */
309
310 /* M521 * M607(半素数,大操作数在前) */
311 lmmp_mul_(t1, b, bn, a, an);
312 mp_size_t dn = limbs_norm(t1, an + bn);
313 for (int s = 0; s <= 7; ++s) {
314 int r = lmmp_is_prime_n_(t1, dn, s);
315 TEST_CHECK_MSG(r == 0 || r == 2, "semiprime product (misjudge allowed)");
316 }
317
318 /* M521 * M607 * M1279(三素子积,抽样档位) */
319 mp_size_t cn = mersenne_limbs(b, 1279); /* 20 limb */
320 lmmp_mul_(t2, b, cn, t1, dn);
321 mp_size_t en = limbs_norm(t2, cn + dn);
322 const int s_values[] = {0, 4, 7};
323 for (size_t s_index = 0; s_index < ARRAY_SIZE(s_values); ++s_index) {
324 int s = s_values[s_index];
325 int r = lmmp_is_prime_n_(t2, en, s);
326 TEST_CHECK_MSG(r == 0 || r == 2, "triprime product (misjudge allowed)");
327 }
328
329 /* 随机 u64 素数三积(~2^190,3 limb) */
330 u64 seed = 0x6d6f726e696e67ull;
331 mp_limb_t f[3][2];
332 for (int i = 0; i < 3; i++) {
333 f[i][0] = random_u64_prime(&seed);
334 f[i][1] = 0;
335 }
336 lmmp_mul_(t1, f[0], 2, f[1], 2);
337 lmmp_mul_(t2, t1, 4, f[2], 2);
338 mp_size_t nn = (t2[3] != 0) ? 4 : 3;
339 for (int s = 0; s <= 7; ++s) {
340 int r = lmmp_is_prime_n_(t2, nn, s);
341 TEST_CHECK_MSG(r == 0 || r == 2, "u64 triple product (misjudge allowed)");
342 }
343}
344
345/*
346 v2(n-1) 跨 limb 边界:n = 3*2^t+1(v2(n-1) = t 恰为给定值),t 取
347 {127,128,129} / {191,192,193} / {255,256,257}(nn = 3/4/5)。素性经
348 Proth 证书判定:认证为素数则硬断言全档 ==2,否则按合数容许域
349*/
350TEST_CASE("numth/prime", is_prime_n_v2_boundary) {
351 mp_limb_t n[512];
352 const int t_values[] = {127, 128, 129, 191, 192, 193, 255, 256, 257};
353 for (size_t t_index = 0; t_index < ARRAY_SIZE(t_values); ++t_index) {
354 int t = t_values[t_index];
355 mp_size_t nn = k2t_limbs(n, t, 3, 1);
356 bool prime = proth_certified(n, nn, t);
357 for (int s = 0; s <= 7; ++s) {
358 int r = lmmp_is_prime_n_(n, nn, s);
359 if (prime)
360 TEST_CHECK_MSG(r == 2, "proth-certified prime at v2 boundary");
361 else
362 TEST_CHECK_MSG(r == 0 || r == 2, "v2 boundary composite (misjudge allowed)");
363 }
364 }
365}
366
367void test_prime_n(void) {
368 TEST_RUN("numth/prime", is_prime_n_proven_primes);
369 TEST_RUN("numth/prime", is_prime_n_notrial_agree);
370 TEST_RUN("numth/prime", is_prime_n_deterministic_reject);
371 TEST_RUN("numth/prime", is_strong_lucas_n);
372 TEST_RUN("numth/prime", is_prime_n_constructive_spsp);
373 TEST_RUN("numth/prime", is_prime_n_product_composites);
374 TEST_RUN("numth/prime", is_prime_n_v2_boundary);
375}
#define k
#define an
#define bn
#define lmmp_sqr_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define lmmp_dec(p)
减1宏(预期无借位)
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
#define t
#define s
#define n
void test_prime_n(void)
int lmmp_is_strong_lucas_(mp_srcptr np, mp_size_t nn)
强 Lucas-Selfridge 测试(大于 128 位)
int lmmp_is_prime_n_notrial_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(无试除法,强度分档,大于 128 位)
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
bool lmmp_is_prime_ulong_(ulong n)
判断素数
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static mp_size_t limbs_norm(const mp_limb_t *p, mp_size_t n)
static u64 random_u64_prime(u64 *seed)
static bool proth_certified(const mp_limb_t *np, mp_size_t nn, int t)
static const int MP_EXP[]
static const int MC_EXP[]
static const int MP_FOLD_EXP
static mp_size_t mersenne_limbs(mp_ptr dst, int p)
static mp_size_t k2t_limbs(mp_ptr dst, int t, mp_limb_t k, mp_limb_t c)
#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