LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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#include "prime_pool.h"
24
25/* ---- Proth 形状:N = k*2^t + 1(k<=2^32) ---- */
26
28 mp_size_t n = (mp_size_t)t / 64 + 2;
29 lmmp_zero(dst, n + 1);
30 uint sh = t % 64;
31 dst[t / 64] |= (mp_limb_t)k << sh;
32 if (sh != 0) dst[t / 64 + 1] |= (mp_limb_t)k >> (64 - sh);
33 dst[0] |= 1;
34 while (n > 1 && dst[n - 1] == 0) n--;
35 return n;
36}
37
38typedef struct {
39 mp_ptr a; /* cnt * stride,元素为 k*2^t+1 */
40 uint ks[8]; /* 各元素的 k */
41 mp_size_t nn[8]; /* 各元素规范化 limb 数 */
43 int cnt;
44} ProthPool;
45
46/* want_prime:Proth 素数池(被测函数搜索);否则试除幸存合数池 */
47static ProthPool pool_proth(uint t, int cnt, bool want_prime) {
48 ProthPool p;
49 p.stride = (mp_size_t)t / 64 + 3;
50 p.cnt = cnt;
51 p.a = alloc_limbs((size_t)p.stride * cnt);
52 uint k = 3;
53 for (int i = 0; i < cnt; i++) {
54 for (;;) {
55 mp_size_t nn = proth_limbs(p.a + p.stride * i, k, t);
56 bool ok = want_prime ? lmmp_is_prothprime_(k, (mp_size_t)t)
57 : !small_factor_q(p.a + p.stride * i, nn);
58 if (ok) break;
59 k += 2;
60 }
61 p.ks[i] = k;
62 p.nn[i] = proth_limbs(p.a + p.stride * i, k, t);
63 k += 2;
64 }
65 return p;
66}
67
68static double bench_is_prothprime(uint t, bool prime_pool, const bench_options *o) {
69 if (t < 1) t = 1; /* is_prothprime_ 契约 n>0 */
70 ProthPool p = pool_proth(t, 8, prime_pool);
71 size_t idx = 0;
72 double us;
73 BENCH_MEASURE(us, o, bench_sink += (mp_limb_t)lmmp_is_prothprime_(p.ks[idx++ % p.cnt], t););
74 lmmp_free(p.a);
75 return us;
76}
77
78static double bench_is_prime_n_proth(uint t, int strength, bool prime_pool, const bench_options *o) {
79 if (t < 1) t = 1; /* 同 bench_is_prothprime:契约 n>0 */
80 ProthPool p = pool_proth(t, 8, prime_pool);
81 size_t idx = 0;
82 double us;
83 BENCH_MEASURE(us, o,
84 bench_sink += (mp_limb_t)lmmp_is_prime_n_(p.a + p.stride * (idx % p.cnt),
85 p.nn[idx % p.cnt], strength);
86 idx++;
87 );
88 lmmp_free(p.a);
89 return us;
90}
91
92/*
93 Proth 形状:lmmp_is_prothprime_ 单梯子定理判决 vs lmmp_is_prime_n_
94 通用分档(同池对照)。素数池 = 分档全轮完整执行的最坏情形(Proth
95 路径的收益所在);合数池 = 试除幸存者,两路径都支付完整梯子,
96 用于确认 Proth 路径在合数侧无回归。素数池构造昂贵,仅取 <=16 limb。
97*/
98static void run_proth(void) {
99 const uint TS[] = {480, 992};
100 for (size_t i = 0; i < ARRAY_SIZE(TS); ++i) {
101 uint t = TS[i];
102 char buf[64];
103 snprintf(buf, sizeof(buf), "is_prothprime prime(t=%u)", t);
104 report(buf, bench_is_prothprime(t, true, &bench_default), 0);
105 snprintf(buf, sizeof(buf), "is_prime_n s4 proth-prime(t=%u)", t);
106 report(buf, bench_is_prime_n_proth(t, 4, true, &bench_default), 0);
107 }
108 const uint TC[] = {2016, 4032};
109 for (size_t i = 0; i < ARRAY_SIZE(TC); ++i) {
110 uint t = TC[i];
111 char buf[64];
112 snprintf(buf, sizeof(buf), "is_prothprime composite(t=%u)", t);
113 report(buf, bench_is_prothprime(t, false, &bench_default), 0);
114 snprintf(buf, sizeof(buf), "is_prime_n s4 proth-composite(t=%u)", t);
115 report(buf, bench_is_prime_n_proth(t, 4, false, &bench_default), 0);
116 }
117}
118
119int main(void) {
120 setvbuf(stdout, NULL, _IONBF, 0);
122 puts("[numth/prime/proth]");
123 run_proth();
125 return 0;
126}
#define k
int main(void)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 main.c:26
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
void lmmp_global_init(void)
全局初始化函数(线程局部的)
uint64_t mp_limb_t
定义 lmmp.h:92
void lmmp_global_deinit(void)
全局释放函数(线程局部的)
#define t
#define n
uint32_t uint
定义 numth.h:38
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
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
#define BENCH_MEASURE(result, options,...)
定义 perf.h:93
static ProthPool pool_proth(uint t, int cnt, bool want_prime)
定义 proth.c:47
static mp_size_t proth_limbs(mp_ptr dst, uint k, uint t)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 proth.c:27
static double bench_is_prime_n_proth(uint t, int strength, bool prime_pool, const bench_options *o)
定义 proth.c:78
mp_size_t stride
定义 proth.c:42
static void run_proth(void)
定义 proth.c:98
static double bench_is_prothprime(uint t, bool prime_pool, const bench_options *o)
定义 proth.c:68
mp_ptr a
定义 proth.c:39
mp_size_t nn[8]
定义 proth.c:41
uint ks[8]
定义 proth.c:40