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];
71 const int STR[] = {0, 4, 7};
76 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(STR); ++s_index) {
84 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(STR); ++s_index) {
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];
96 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(STR); ++s_index) {
99 "small factor agree");
104 u64 seed = 0x6e6f747269616c6eull;
106 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
109 for (
int i = 0; i < 60; ++i) {
110 for (
mp_size_t j = 0; j <
n; ++j) a[j] = xorshift64(&seed);
112 for (
size_t s_index = 0; s_index <
ARRAY_SIZE(STR); ++s_index) {
113 int s = STR[s_index];
123TEST_CASE(
"numth/prime", is_prime_n_deterministic_reject) {
130 for (
int s = 0;
s <= 7; ++
s)
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];
140 for (
int s = 0;
s <= 7; ++
s)
150 for (
int s = 0;
s <= 7; ++
s)
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];
172 for (
int s = 0;
s <= 7; ++
s) {
177 TEST_CHECK_MSG(r == 0 || r == 2,
"prime square at MR tiers (misjudge allowed)");
187 mp_limb_t p[512], q[512], t1[1024], t2[1024];
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];
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];
226 TEST_CHECK_MSG(r == 0 || r == 1,
"lucas p^2*q (misjudge allowed)");
237 TEST_CHECK_MSG(r == 0 || r == 1,
"lucas mersenne composite (misjudge allowed)");
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];
259 for (
int s = 0;
s <= 7; ++
s) {
261 if (p == 131 &&
s >= 1)
262 TEST_CHECK_MSG(r == 0,
"M131 factor 263 caught by trial bound >=300");
264 TEST_CHECK_MSG(r == 0 || r == 2,
"mersenne composite (misjudge allowed)");
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];
274 for (
int s = 0;
s <= 7; ++
s) {
276 TEST_CHECK_MSG(r == 0 || r == 2,
"fermat composite (misjudge allowed)");
283 struct carmichael_case {
287 {{0xff15f6ff84b4f0f3ull, 0xe106b441973e19bfull, 0x0e7000000110a524ull},
288 "3458764513840342771*8070450532294133131*12682136550747923491"},
289 {{0x66fe7ee3b284e7c3ull, 0x310b7aaab318c4a5ull, 0x0e7000000164c3bfull},
290 "3458764513846452259*8070450532308388603*12682136550770324947"},
291 {{0x3805ef3326bcc70bull, 0x7928975dd02cf97dull, 0x0e700000029ee088ull},
292 "3458764513869265819*8070450532361620243*12682136550853974667"},
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) {
298 TEST_CHECK_MSG(r == 0 || r == 2,
"carmichael adversarial (misjudge allowed)");
305TEST_CASE(
"numth/prime", is_prime_n_product_composites) {
306 mp_limb_t a[512], b[512], t1[1024], t2[1024];
313 for (
int s = 0;
s <= 7; ++
s) {
315 TEST_CHECK_MSG(r == 0 || r == 2,
"semiprime product (misjudge allowed)");
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];
326 TEST_CHECK_MSG(r == 0 || r == 2,
"triprime product (misjudge allowed)");
330 u64 seed = 0x6d6f726e696e67ull;
332 for (
int i = 0; i < 3; i++) {
339 for (
int s = 0;
s <= 7; ++
s) {
341 TEST_CHECK_MSG(r == 0 || r == 2,
"u64 triple product (misjudge allowed)");
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];
357 for (
int s = 0;
s <= 7; ++
s) {
362 TEST_CHECK_MSG(r == 0 || r == 2,
"v2 boundary composite (misjudge allowed)");
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);
#define lmmp_copy(dst, src, n)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
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]
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)
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)
#define TEST_CASE(category, name)
#define TEST_RUN(category, name)