LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
prime_ref.h 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "support/test.h"
#include "support/lmmp_test_utils.h"
prime_ref.h 的引用(Include)关系图:
此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

函数

static int expect2 (u64 lo, u64 hi, bool prime)
static mp_size_t k2t_limbs (mp_ptr dst, int t, mp_limb_t k, mp_limb_t c)
static bool less_sw (u64 lo, u64 hi)
static mp_size_t limbs_norm (const mp_limb_t *p, mp_size_t n)
static mp_size_t mersenne_limbs (mp_ptr dst, int p)
static u64 mod_pow64 (u64 a, u64 e, u64 mod)
static u64 mulmod64 (u64 a, u64 b, u64 m)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
static bool proth_cert_g (uint k, int t, int nbase)
static bool proth_certified (const mp_limb_t *np, mp_size_t nn, int t)
static u64 random_u64_prime (u64 *seed)
static bool ref_is_prime32 (u32 n)
static bool ref_is_prime64 (u64 n)

变量

static const int MC_EXP [] = {131, 137, 149, 163}
static const int MP_EXP [] = {521, 607, 1279, 4423}
static const int MP_FOLD_EXP = 19937

函数说明

◆ expect2()

int expect2 ( u64 lo,
u64 hi,
bool prime )
inlinestatic

在文件 prime_ref.h 第 91 行定义.

91 {
92 if (!prime) return 0;
93 return less_sw(lo, hi) ? 1 : 2;
94}
#define lo
static bool less_sw(u64 lo, u64 hi)

引用了 expect2(), less_sw() , 以及 lo.

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

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

◆ k2t_limbs()

mp_size_t k2t_limbs ( mp_ptr dst,
int t,
mp_limb_t k,
mp_limb_t c )
inlinestatic

在文件 prime_ref.h 第 111 行定义.

111 {
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}
#define k
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#define t
#define n

引用了 k, k2t_limbs(), lmmp_zero, n , 以及 t.

被这些函数引用 k2t_limbs(), proth_cert_g(), proth_certified(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ less_sw()

bool less_sw ( u64 lo,
u64 hi )
inlinestatic

在文件 prime_ref.h 第 88 行定义.

88 {
89 return hi < 0x2be69ull || (hi == 0x2be69ull && lo < 0x51adc5b22410a5fdull);
90}

引用了 less_sw() , 以及 lo.

被这些函数引用 expect2() , 以及 less_sw().

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

◆ limbs_norm()

mp_size_t limbs_norm ( const mp_limb_t * p,
mp_size_t n )
inlinestatic

在文件 prime_ref.h 第 130 行定义.

130 {
131 while (n > 1 && p[n - 1] == 0) n--;
132 return n;
133}

引用了 limbs_norm() , 以及 n.

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

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

◆ mersenne_limbs()

mp_size_t mersenne_limbs ( mp_ptr dst,
int p )
inlinestatic

在文件 prime_ref.h 第 103 行定义.

103 {
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}
uint64_t mp_limb_t
定义 lmmp.h:92

引用了 mersenne_limbs() , 以及 n.

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

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

◆ mod_pow64()

u64 mod_pow64 ( u64 a,
u64 e,
u64 mod )
inlinestatic

在文件 prime_ref.h 第 46 行定义.

46 {
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}
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
static u64 mulmod64(u64 a, u64 b, u64 m)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 mod_pow64() , 以及 mulmod64().

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

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

◆ mulmod64()

u64 mulmod64 ( u64 a,
u64 b,
u64 m )
inlinestatic

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

在文件 prime_ref.h 第 40 行定义.

40 {
41 mp_limb_t t[2];
42 lmmp_mullh_(a, b, t);
43 return lmmp_mod_1_(t, 2, m);
44}
#define lmmp_mullh_
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38

引用了 lmmp_mod_1_(), lmmp_mullh_, mulmod64() , 以及 t.

被这些函数引用 mod_pow64(), mulmod64() , 以及 ref_is_prime64().

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

◆ proth_cert_g()

bool proth_cert_g ( uint k,
int t,
int nbase )
inlinestatic

在文件 prime_ref.h 第 140 行定义.

140 {
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}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_dec(p)
减1宏(预期无借位)
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
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]
static mp_size_t k2t_limbs(mp_ptr dst, int t, mp_limb_t k, mp_limb_t c)

引用了 k, k2t_limbs(), lmmp_cmp_(), lmmp_copy, lmmp_dec, lmmp_powmod_(), lmmp_zero, proth_cert_g() , 以及 t.

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

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

◆ proth_certified()

bool proth_certified ( const mp_limb_t * np,
mp_size_t nn,
int t )
inlinestatic

在文件 prime_ref.h 第 162 行定义.

162 {
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}
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40

引用了 ARRAY_SIZE, k2t_limbs(), lmmp_cmp_(), lmmp_copy, lmmp_dec, lmmp_powmod_(), lmmp_zero, proth_certified() , 以及 t.

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

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

◆ random_u64_prime()

u64 random_u64_prime ( u64 * seed)
inlinestatic

在文件 prime_ref.h 第 123 行定义.

123 {
124 u64 x = (xorshift64(seed) >> 4) | ((u64)1 << 59) | 1;
125 while (!ref_is_prime64(x)) x += 2;
126 return x;
127}
static bool ref_is_prime64(u64 n)

引用了 random_u64_prime() , 以及 ref_is_prime64().

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

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

◆ ref_is_prime32()

bool ref_is_prime32 ( u32 n)
inlinestatic

在文件 prime_ref.h 第 85 行定义.

85{ return ref_is_prime64(n); }

引用了 n, ref_is_prime32() , 以及 ref_is_prime64().

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

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

◆ ref_is_prime64()

bool ref_is_prime64 ( u64 n)
inlinestatic

在文件 prime_ref.h 第 57 行定义.

57 {
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}
#define s
static u64 mod_pow64(u64 a, u64 e, u64 mod)

引用了 ARRAY_SIZE, mod_pow64(), mulmod64(), n, ref_is_prime64() , 以及 s.

被这些函数引用 random_u64_prime(), ref_is_prime32(), ref_is_prime64(), TEST_CASE(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

变量说明

◆ MC_EXP

const int MC_EXP[] = {131, 137, 149, 163}
static

在文件 prime_ref.h 第 100 行定义.

被这些函数引用 TEST_CASE().

◆ MP_EXP

const int MP_EXP[] = {521, 607, 1279, 4423}
static

在文件 prime_ref.h 第 98 行定义.

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

◆ MP_FOLD_EXP

const int MP_FOLD_EXP = 19937
static

在文件 prime_ref.h 第 99 行定义.

被这些函数引用 TEST_CASE().