23#ifndef LMMP_TEST_PRIME_REF_H
24#define LMMP_TEST_PRIME_REF_H
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;
67 while ((d & 1) == 0) { d >>= 1; ++
s; }
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;
74 if (x == 1 || x ==
n - 1)
continue;
75 bool composite =
true;
76 for (
int r = 1; r <
s; ++r) {
78 if (x ==
n - 1) { composite =
false;
break; }
80 if (composite)
return false;
89 return hi < 0x2be69ull || (hi == 0x2be69ull &&
lo < 0x51adc5b22410a5fdull);
98static const int MP_EXP[] = {521, 607, 1279, 4423};
100static const int MC_EXP[] = {131, 137, 149, 163};
114 dst[
t / 64] |=
k << (
t % 64);
115 if (
t % 64) dst[
t / 64 + 1] |=
k >> (64 -
t % 64);
117 while (
n > 1 && dst[
n - 1] == 0)
n--;
124 u64 x = (xorshift64(seed) >> 4) | ((
u64)1 << 59) | 1;
131 while (
n > 1 && p[
n - 1] == 0)
n--;
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;
145 mp_limb_t N[512], e[512], bp[512], r[512], m1[512];
150 for (
int ai = 0; ai < nbase; ai++) {
154 if (
lmmp_cmp_(r, m1, nn) == 0)
return true;
163 mp_limb_t e[8], bp[512], r[512], m1[512];
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];
173 if (
lmmp_cmp_(r, m1, nn) == 0)
return true;
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
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)
单精度数取余
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
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)
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)