LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_prime2.c 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "cases.h"
#include "prime_ref.h"
test_prime2.c 的引用(Include)关系图:

浏览该文件的源代码.

结构体

struct  prime_vector
 Copyright (C) 2026 HJimmyK (Jericho Knox) 更多...

函数

static void check_prime_2_agreement (mp_limb_t lo, mp_limb_t hi, const char *what)
 TEST_CASE ("numth/prime", is_prime_2)
 TEST_CASE ("numth/prime", is_prime_2_notrial)
void test_prime2 (void)

变量

static const struct prime_vector vec128 []

结构体说明

◆ prime_vector

struct prime_vector

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 test_prime2.c 第 33 行定义.

prime_vector 的协作图:
成员变量
bool expect
u64 hi
u64 lo

函数说明

◆ check_prime_2_agreement()

void check_prime_2_agreement ( mp_limb_t lo,
mp_limb_t hi,
const char * what )
static

在文件 test_prime2.c 第 236 行定义.

236 {
237 int full = lmmp_is_prime_2_(lo, hi);
238 int nt = lmmp_is_prime_2_notrial_(lo, hi);
239 TEST_CHECK_MSG(nt == full, what);
240}
#define lo
int lmmp_is_prime_2_notrial_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数(无试除法)
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 check_prime_2_agreement(), lmmp_is_prime_2_(), lmmp_is_prime_2_notrial_(), lo , 以及 TEST_CHECK_MSG.

被这些函数引用 check_prime_2_agreement() , 以及 TEST_CASE().

函数调用图:
这是这个函数的调用关系图:

◆ TEST_CASE() [1/2]

TEST_CASE ( "numth/prime" ,
is_prime_2  )

在文件 test_prime2.c 第 270 行定义.

270 {
271 struct prime_case { u64 hi, lo; bool expect; const char* what; } cases[] = {
272 {0x7fffffffffffffffull, 0xffffffffffffffffull, true, "2^127-1 Mersenne"},
273 {0xffffffffffffffffull, 0xffffffffffffff61ull, true, "2^128-159 largest prime < 2^128"},
274 {0x0000000000000001ull, 0x000000000000000dull, true, "2^64+13"},
275 {0x0000000000000001ull, 0x0000000000000001ull, false, "2^64+1 Fermat"},
276 {0xffffffffffffffffull, 0xffffffffffffffffull, false, "2^128-1 (3 divides)"},
277 {0x000000000000437aull, 0xe92817f9fc85b7e5ull, false, "psi_12 SPSP(2..37)"},
278 {0x000000000000437aull, 0xe92817f9fc85b7e4ull, false, "psi_12-1 even"},
279 {0x000000000000437aull, 0xe92817f9fc85b7d1ull, true, "first prime < psi_12"},
280 {0x000000000000437aull, 0xe92817f9fc85b7fbull, true, "first prime > psi_12"},
281 {0x000000000002be69ull, 0x51adc5b22410a5fdull, false, "psi_13 = SWbound"},
282 {0x000000000002be69ull, 0x51adc5b22410a68bull, true, "first prime > SWbound"},
283 {0x0000000000000001ull, 0x0000000000000000ull, false, "2^64 even"},
284 /* D 搜索上界回归:least |D| > 201 的真素数(CRT 构造 + 扫描验证,
285 40 基底 MR 复核),旧版上界 201 会误判为合数(返回 0) */
286 {0x800000035f5a7854ull, 0x024690fc2c1cab2dull, true, "prime with least|D|=211"},
287 {0x80000023e5c609bfull, 0xa5c985498fc11b3dull, true, "prime with least|D|=227"},
288 {0x8000000be28e524cull, 0x609ffaaa3f5d4dd5ull, true, "prime with least|D|=211"},
289 };
290 for (size_t c_index = 0; c_index < ARRAY_SIZE(cases); ++c_index) {
291 const struct prime_case c = cases[c_index];
292 TEST_CHECK_MSG(lmmp_is_prime_2_(c.lo, c.hi) == expect2(c.lo, c.hi, c.expect), c.what);
293 }
294
295 /* 硬编码向量(含 65..128 bit 随机、素数、SWbound 邻域、psi_12/13) */
296 for (size_t v_index = 0; v_index < ARRAY_SIZE(vec128); ++v_index) {
297 const struct prime_vector v = vec128[v_index];
298 TEST_CHECK_MSG(lmmp_is_prime_2_(v.lo, v.hi) == expect2(v.lo, v.hi, v.expect), "vec128");
299 }
300
301 /* Proth 认证素数 65..127 bit(k*2^t+1):被测命中即证书复核(硬断言),
302 类别按 SW 分界;SW 两侧各一组(t 定、k 扫描——k=3 密度不足) */
303 {
304 int found[2] = {0, 0};
305 const int groups[2][2] = {{66, 78}, {108, 126}}; // {t_lo, t_hi}:<SW 与 >SW
306 mp_limb_t n[4]; // k2t_limbs 清零 t/64+3 个 limb(t<=127 需 4)
307 for (int g = 0; g < 2; ++g) {
308 for (int t = groups[g][0]; t <= groups[g][1] && found[g] < 2; ++t) {
309 for (uint k = 3; k < 999 && found[g] < 2; k += 2) {
310 mp_size_t nn = k2t_limbs(n, t, k, 1);
311 if (nn > 2) break; // N >= 2^128:超出 is_prime_2_ 契约域
312 int r = lmmp_is_prime_2_(n[0], n[1]);
313 if (r != 0) {
314 TEST_CHECK_MSG(proth_cert_g(k, t, 17), "proth prime certified");
315 TEST_CHECK_MSG(r == (g == 0 ? 1 : 2), "proth prime category");
316 ++found[g];
317 }
318 }
319 }
320 TEST_CHECK_MSG(found[g] >= 1, "proth prime coverage per SW side");
321 }
322 }
323
324 /* 素数乘积:两 34 bit 素数积 ~68 bit < SWbound(确定性域)→ 硬断言 ==0 */
325 {
326 u64 seed = 0x70726f74683231ull;
327 for (int i = 0; i < 20; ++i) {
328 u64 p = 0x100000000ull + (xorshift64(&seed) & 0xffffffffull);
329 p |= 1;
330 while (!ref_is_prime64(p)) p += 2;
331 u64 q = 0x100000000ull + (xorshift64(&seed) & 0xffffffffull);
332 q |= 1;
333 while (!ref_is_prime64(q)) q += 2;
334 mp_limb_t prod[2];
335 lmmp_mullh_(p, q, prod); /* ~68 bit < SW */
336 TEST_CHECK_MSG(lmmp_is_prime_2_(prod[0], prod[1]) == 0, "semiprime < SW rejected");
337 }
338 }
339
340 /* 平方数(Lucas 无 D 的防御路径不应误判) */
341 {
342 u64 p = 0x000001000000000full; // >2^40 素数
344 mp_limb_t sq[2];
345 lmmp_mullh_(p, p, sq);
346 TEST_CHECK_MSG(lmmp_is_prime_2_(sq[0], sq[1]) == 0, "square rejected");
347 /* 3*p^2(mullh 一步 + 乘小系数;p^2*3 < 2^128 恒成立) */
348 mp_limb_t sq3[3];
349 u64 hi = lmmp_mul_1_(sq3, sq, 2, 3);
350 TEST_CHECK_MSG(hi == 0, "3*square fits 2 limbs");
351 TEST_CHECK_MSG(lmmp_is_prime_2_(sq3[0], sq3[1]) == 0, "3*square rejected");
352 }
353}
#define k
#define prod
#define lmmp_mullh_
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
#define t
#define n
uint32_t uint
定义 numth.h:38
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static int expect2(u64 lo, u64 hi, bool prime)
static bool proth_cert_g(uint k, int t, int nbase)
static bool ref_is_prime64(u64 n)
static mp_size_t k2t_limbs(mp_ptr dst, int t, mp_limb_t k, mp_limb_t c)
#define TEST_CHECK(cond)
定义 test.h:37
static const struct prime_vector vec128[]
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 ARRAY_SIZE, prime_vector::expect, expect2(), prime_vector::hi, k, k2t_limbs(), lmmp_is_prime_2_(), lmmp_mul_1_(), lmmp_mullh_, lo, prime_vector::lo, n, prod, proth_cert_g(), ref_is_prime64(), t, TEST_CASE, TEST_CHECK, TEST_CHECK_MSG , 以及 vec128.

函数调用图:

◆ TEST_CASE() [2/2]

TEST_CASE ( "numth/prime" ,
is_prime_2_notrial  )

在文件 test_prime2.c 第 242 行定义.

242 {
243 /* 边界与分档代表(含偶数拒、psi_12/13 邻域、BPSW 档素数) */
244 check_prime_2_agreement(0x0000000000000000ull, 0x0000000000000001ull, "2^64 even");
245 check_prime_2_agreement(0x000000000000000dull, 0x0000000000000001ull, "2^64+13");
246 check_prime_2_agreement(0xffffffffffffffffull, 0x7fffffffffffffffull, "2^127-1");
247 check_prime_2_agreement(0xffffffffffffff61ull, 0xffffffffffffffffull, "2^128-159");
248 check_prime_2_agreement(0x51adc5b22410a5fdull, 0x000000000002be69ull, "psi_13");
249 check_prime_2_agreement(0x51adc5b22410a68bull, 0x000000000002be69ull, "first prime > SW");
250 /* 小因子合数:3|n、5|n 与 2^64+1(17 整除),notrial 走 MR 同拒 */
251 check_prime_2_agreement(0xffffffffffffffffull, 0xffffffffffffffffull, "2^128-1 (3 divides)");
252 check_prime_2_agreement(0x0000000000000001ull, 0x0000000000000001ull, "2^64+1 Fermat");
253 check_prime_2_agreement(0x0000000000000005ull, 0x0000000000000003ull, "3*2^64+5 (5 divides)");
254 /* 随机奇数流:全量对照(确定性期望经 ref_is_prime64 不适用 128bit,
255 以两变体互证为主,位宽扫 65..128 若干代表点) */
256 u64 seed = 0x6e6f747269616c32ull;
257 const uint HB[] = {1, 3, 17, 63, 64};
258 for (size_t hb_index = 0; hb_index < ARRAY_SIZE(HB); ++hb_index) {
259 uint hb = HB[hb_index];
260 for (int i = 0; i < 200; ++i) {
261 mp_limb_t lo = xorshift64(&seed), hi = xorshift64(&seed);
262 if (hb < 64) hi &= ((mp_limb_t)-1) >> (64 - hb);
263 hi |= (mp_limb_t)1 << (hb - 1);
264 lo |= 1;
265 check_prime_2_agreement(lo, hi, "random odd agree");
266 }
267 }
268}
static void check_prime_2_agreement(mp_limb_t lo, mp_limb_t hi, const char *what)

引用了 ARRAY_SIZE, check_prime_2_agreement(), lo , 以及 TEST_CASE.

函数调用图:

◆ test_prime2()

void test_prime2 ( void )

在文件 test_prime2.c 第 355 行定义.

355 {
356 TEST_RUN("numth/prime", is_prime_2_notrial);
357 TEST_RUN("numth/prime", is_prime_2);
358}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_prime2() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_prime2().

函数调用图:
这是这个函数的调用关系图:

变量说明

◆ vec128

const struct prime_vector vec128[]
static

被这些函数引用 TEST_CASE().