LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
prime_ref.h
浏览该文件的文档.
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#ifndef LMMP_TEST_PRIME_REF_H
24#define LMMP_TEST_PRIME_REF_H
25
26/*
27 素性检验测试共享构造(铁律合规:仅 64 位内标量参考 + 库路径组合)。
28 ref_is_prime64 为原生标量 Miller-Rabin(2^64 确定性基组,模乘经
29 lmmp_mullh_ 全积 + lmmp_mod_1_ 取余——均为独立测试套覆盖的原语),
30 属「64 位内简单参考」允许域。Proth 证书走 lmmp_powmod_ 独立梯子
31 (由 powmod 测试套独立保证),普罗斯定理:有证书 ⟺ 素数。
32*/
33
34#include "lmmp/lmmpn.h"
35#include "lmmp/numth.h"
36#include "support/test.h"
38
39// 64 位模乘:mullh 全积 + mod_1 余(div 套件独立覆盖)
40static inline u64 mulmod64(u64 a, u64 b, u64 m) {
41 mp_limb_t t[2];
42 lmmp_mullh_(a, b, t);
43 return lmmp_mod_1_(t, 2, m);
44}
45
46static inline u64 mod_pow64(u64 a, u64 e, u64 mod) {
47 u64 r = 1 % mod;
48 a %= mod;
49 while (e) {
50 if (e & 1) r = mulmod64(r, a, mod);
51 a = mulmod64(a, a, mod);
52 e >>= 1;
53 }
54 return r;
55}
56
57static inline bool ref_is_prime64(u64 n) {
58 if (n < 2) return false;
59 const u64 p_values[] = {2ull, 3ull, 5ull, 7ull, 11ull, 13ull, 17ull, 19ull, 23ull, 29ull, 31ull, 37ull};
60 for (size_t p_index = 0; p_index < ARRAY_SIZE(p_values); ++p_index) {
61 u64 p = p_values[p_index];
62 if (n == p) return true;
63 if (n % p == 0) return false;
64 }
65 u64 d = n - 1;
66 int s = 0;
67 while ((d & 1) == 0) { d >>= 1; ++s; }
68 // 对 2^64 范围内确定性的 Miller-Rabin 基组
69 const u64 a_values[] = {2ull, 325ull, 9375ull, 28178ull, 450775ull, 9780504ull, 1795265022ull};
70 for (size_t a_index = 0; a_index < ARRAY_SIZE(a_values); ++a_index) {
71 u64 a = a_values[a_index];
72 if (a % n == 0) continue;
73 u64 x = mod_pow64(a, d, n);
74 if (x == 1 || x == n - 1) continue;
75 bool composite = true;
76 for (int r = 1; r < s; ++r) {
77 x = mulmod64(x, x, n);
78 if (x == n - 1) { composite = false; break; }
79 }
80 if (composite) return false;
81 }
82 return true;
83}
84
85static inline bool ref_is_prime32(u32 n) { return ref_is_prime64(n); }
86
87// 三态期望值:素数时按 SWbound 分界返回 1(确定性)或 2(BPSW 型)
88static inline bool less_sw(u64 lo, u64 hi) {
89 return hi < 0x2be69ull || (hi == 0x2be69ull && lo < 0x51adc5b22410a5fdull);
90}
91static inline int expect2(u64 lo, u64 hi, bool prime) {
92 if (!prime) return 0;
93 return less_sw(lo, hi) ? 1 : 2;
94}
95
96/* 已证 Mersenne 素数指数(GIMPS)与 Mersenne 合数指数(素数 p 且
97 p ∈ (127,521)——该区间无 Mersenne 素数 ⟹ M_p 全为合数) */
98static const int MP_EXP[] = {521, 607, 1279, 4423};
99static const int MP_FOLD_EXP = 19937; /* 312 limb >= REDC_MERSENNE_THRESHOLD */
100static const int MC_EXP[] = {131, 137, 149, 163}; /* 全部合数;M131 最小因子 263 */
101
102/* 2^p - 1 写入 dst(p 为奇素数,p%64 != 0),返回 limb 数 */
103static inline mp_size_t mersenne_limbs(mp_ptr dst, int p) {
104 mp_size_t n = p / 64 + 1;
105 for (mp_size_t i = 0; i < n; i++) dst[i] = ~(mp_limb_t)0;
106 dst[n - 1] = ((mp_limb_t)1 << (p % 64)) - 1;
107 return n;
108}
109
110/* k*2^t + c(k <= 2^64,c ∈ {0,1})写入 dst,返回规范化 limb 数 */
111static inline mp_size_t k2t_limbs(mp_ptr dst, int t, mp_limb_t k, mp_limb_t c) {
112 mp_size_t n = (mp_size_t)t / 64 + 2;
113 lmmp_zero(dst, n + 1);
114 dst[t / 64] |= k << (t % 64);
115 if (t % 64) dst[t / 64 + 1] |= k >> (64 - t % 64);
116 if (c) dst[0] |= 1;
117 while (n > 1 && dst[n - 1] == 0) n--;
118 return n;
119}
120
121/* 随机 u64 素数(ref_is_prime64 确定性认证),顶位不低于 2^59(保证
122 三素子积 > 2^177 达 3 limb) */
123static inline u64 random_u64_prime(u64 *seed) {
124 u64 x = (xorshift64(seed) >> 4) | ((u64)1 << 59) | 1;
125 while (!ref_is_prime64(x)) x += 2;
126 return x;
127}
128
129/* 自顶去零(乘积的顶 limb 可能为零,is_prime_n_/lucas 契约要求非零) */
130static inline mp_size_t limbs_norm(const mp_limb_t* p, mp_size_t n) {
131 while (n > 1 && p[n - 1] == 0) n--;
132 return n;
133}
134
135/*
136 Proth 证书(通用 k,t <= 20000):N = k*2^t+1 为素 ⟺ 存在小奇 a 使
137 a^((N-1)/2) ≡ -1 (mod N);走 lmmp_powmod_ 通用路径(独立于被测实现)。
138 nbase 为基底表用量(默认全表至 61),求不出仅返回 false
139*/
140static inline bool proth_cert_g(uint k, int t, int nbase) {
141 static const u64 bases[] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
142 37, 41, 43, 47, 53, 59, 61};
143 const int nbases = (int)(sizeof(bases) / sizeof(bases[0]));
144 if (nbase > nbases) nbase = nbases; /* 防 bases 越界读 */
145 mp_limb_t N[512], e[512], bp[512], r[512], m1[512];
146 mp_size_t nn = k2t_limbs(N, t, k, 1);
147 mp_size_t en = k2t_limbs(e, t - 1, k, 0);
148 lmmp_copy(m1, N, nn);
149 lmmp_dec(m1);
150 for (int ai = 0; ai < nbase; ai++) {
151 lmmp_zero(bp, nn);
152 bp[0] = bases[ai];
153 lmmp_powmod_(r, bp, e, en, N, nn);
154 if (lmmp_cmp_(r, m1, nn) == 0) return true;
155 }
156 return false;
157}
158
159/*
160 Proth 证书(k=3 定长形式,n = 3*2^t+1):被测命中即证书复核
161*/
162static inline bool proth_certified(const mp_limb_t* np, mp_size_t nn, int t) {
163 mp_limb_t e[8], bp[512], r[512], m1[512];
164 mp_size_t en = k2t_limbs(e, t - 1, 3, 0); /* (n-1)/2 = 3*2^(t-1) */
165 lmmp_copy(m1, np, nn);
166 lmmp_dec(m1);
167 const u64 a_values2[] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};
168 for (size_t a_index = 0; a_index < ARRAY_SIZE(a_values2); ++a_index) {
169 u64 a = a_values2[a_index];
170 lmmp_zero(bp, nn);
171 bp[0] = a;
172 lmmp_powmod_(r, bp, e, en, np, nn);
173 if (lmmp_cmp_(r, m1, nn) == 0) return true;
174 }
175 return false;
176}
177
178#endif // LMMP_TEST_PRIME_REF_H
#define k
#define lmmp_mullh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
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)
#define lmmp_dec(p)
减1宏(预期无借位)
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
#define t
#define s
#define n
#define lo
uint32_t uint
定义 numth.h:38
void lmmp_powmod_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n)
计算任意模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
static int expect2(u64 lo, u64 hi, bool prime)
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 bool proth_cert_g(uint k, int t, int nbase)
static u64 mulmod64(u64 a, u64 b, u64 m)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static const int MP_EXP[]
static bool ref_is_prime64(u64 n)
static const int MC_EXP[]
static const int MP_FOLD_EXP
static bool less_sw(u64 lo, u64 hi)
static mp_size_t mersenne_limbs(mp_ptr dst, int p)
static bool ref_is_prime32(u32 n)
static mp_size_t k2t_limbs(mp_ptr dst, int t, mp_limb_t k, mp_limb_t c)
static u64 mod_pow64(u64 a, u64 e, u64 mod)