LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime_uint.c 文件参考
#include "impl/inlines.h"
#include "impl/longlong.h"
#include "impl/prime_table.h"
#include "impl/trialdiv.h"
#include "lmmp/numth.h"
#include "mparam.h"
#include "numth/is_prime.h"
is_prime_uint.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

bool lmmp_is_prime_uint_ (uint n)
 判断素数
bool lmmp_is_prime_uint_notrial_ (uint n)
 u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
static void powmod2b_u32 (uint b, uint d, int ebits, uint n, ulong dinv, uint *py2, uint *pyb)
static int sprp_check_u32 (uint y, ulong t, uint n, ulong dinv)
static ulong urem32_preinv (ulong t, ulong n, ulong dinv)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数说明

◆ lmmp_is_prime_uint_()

bool lmmp_is_prime_uint_ ( uint n)

判断素数

参数
n待判断的数
返回
若 n 为素数,返回 true,否则返回 false

在文件 is_prime_uint.c 第 124 行定义.

124 {
125 if (n == 2)
126 return true;
127 if (n % 2 == 0 || n <= 1)
128 return false;
129 int judge = lmmp_is_prime_table_(n);
130 if (judge == 0) {
131 return false;
132 } else if (judge == 1) {
133 return true;
134 }
135
136 if (trial_div35711(n))
137 return false;
138
140}
bool lmmp_is_prime_uint_notrial_(uint n)
u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
#define n
int lmmp_is_prime_table_(uint p)
根据全局素数表判断一个数是否为素数
static int trial_div35711(ulong n)
校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0

引用了 lmmp_is_prime_table_(), lmmp_is_prime_uint_(), lmmp_is_prime_uint_notrial_(), n , 以及 trial_div35711().

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

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

◆ lmmp_is_prime_uint_notrial_()

bool lmmp_is_prime_uint_notrial_ ( uint n)

u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)

参数
n待判断的数
警告
n>2, n%2==1
注解
建议调用前已过 3,5,7,11 试除(内部不试除); 供 lmmp_is_prime_uint_ 与 lmmp_is_prime_ulong_notrial_ 的 n≤2^32-1 档共享; 判定集合与 mont63 双链旧实现精确一致(同基底同强 MR 语义)
返回
若 n 为素数,返回 true,否则返回 false

在文件 is_prime_uint.c 第 98 行定义.

98 {
100 lmmp_param_assert(n % 2 == 1);
101
102 uint base = dj_base49[((0x3AC69A35UL * n) & 0xFFFFFFFFUL) >> 21] + 3;
103 if (n % base == 0 || base % n == 0) {
104 if (n > base)
105 return false;
106 for (uint p = 3; p * p <= n; p += 2)
107 if (n % p == 0) return false;
108 return true;
109 }
110
111 ulong dinv = MP_ULONG_MAX / n + 1;
112 ulong d;
113 ulong t;
114 ctz_shr_u64(d, n - 1, t);
115 int ebits = lmmp_limb_bits_(d);
116
117 uint y2, yb;
118 powmod2b_u32(base, (uint)d, ebits, n, dinv, &y2, &yb);
119 if (!sprp_check_u32(y2, t, n, dinv))
120 return false;
121 return sprp_check_u32(yb, t, n, dinv);
122}
#define lmmp_limb_bits_
const uint16_t dj_base49[2048]
Copyright (C) 2026 HJimmyK (Jericho Knox)
static int sprp_check_u32(uint y, ulong t, uint n, ulong dinv)
static void powmod2b_u32(uint b, uint d, int ebits, uint n, ulong dinv, uint *py2, uint *pyb)
#define MP_ULONG_MAX
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t
uint32_t uint
定义 numth.h:38
uint64_t ulong
定义 numth.h:39

引用了 ctz_shr_u64, dj_base49, lmmp_is_prime_uint_notrial_(), lmmp_limb_bits_, LMMP_NOINLINE, lmmp_param_assert, MP_ULONG_MAX, n, powmod2b_u32(), sprp_check_u32() , 以及 t.

被这些函数引用 lmmp_is_prime_uint_(), lmmp_is_prime_uint_notrial_() , 以及 lmmp_is_prime_ulong_notrial_().

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

◆ powmod2b_u32()

void powmod2b_u32 ( uint b,
uint d,
int ebits,
uint n,
ulong dinv,
uint * py2,
uint * pyb )
static

在文件 is_prime_uint.c 第 39 行定义.

39 {
40 ulong xb = b;
41 if (xb >= n)
42 xb = urem32_preinv(xb, n, dinv);
43
44 if (ebits <= 6) {
45 ulong x2 = urem32_preinv((ulong)1 << d, n, dinv);
46 for (int k = ebits - 2; k >= 0; k--) {
47 xb = urem32_preinv(xb * xb, n, dinv);
48 if ((d >> k) & 1)
49 xb = urem32_preinv(xb * b, n, dinv);
50 }
51 *py2 = (uint)x2;
52 *pyb = (uint)xb;
53 return;
54 }
55
56 ulong x2 = urem32_preinv((ulong)1 << (d >> (ebits - 6)), n, dinv);
57 for (int k = ebits - 2; k >= ebits - 6; k--) {
58 xb = urem32_preinv(xb * xb, n, dinv);
59 if ((d >> k) & 1)
60 xb = urem32_preinv(xb * b, n, dinv);
61 }
62 if (n < (1u << 31)) {
63 for (int k = ebits - 7; k >= 0; k--) {
64 x2 = urem32_preinv(x2 * x2, n, dinv);
65 x2 <<= (d >> k) & 1;
66 xb = urem32_preinv(xb * xb, n, dinv);
67 if ((d >> k) & 1)
68 xb = urem32_preinv(xb * b, n, dinv);
69 }
70 if (x2 >= n) x2 -= n;
71 } else {
72 for (int k = ebits - 7; k >= 0; k--) {
73 x2 = urem32_preinv(x2 * x2, n, dinv);
74 x2 <<= (d >> k) & 1;
75 if (x2 >= n) x2 -= n;
76 xb = urem32_preinv(xb * xb, n, dinv);
77 if ((d >> k) & 1)
78 xb = urem32_preinv(xb * b, n, dinv);
79 }
80 }
81 *py2 = (uint)x2;
82 *pyb = (uint)xb;
83}
#define k
static ulong urem32_preinv(ulong t, ulong n, ulong dinv)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 k, n, powmod2b_u32() , 以及 urem32_preinv().

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

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

◆ sprp_check_u32()

int sprp_check_u32 ( uint y,
ulong t,
uint n,
ulong dinv )
static

在文件 is_prime_uint.c 第 85 行定义.

85 {
86 if (y == 1 || y == n - 1)
87 return 1;
88 for (t--; t > 0; t--) {
89 ulong v = y;
90 v = urem32_preinv(v * v, n, dinv);
91 y = (uint)v;
92 if (y == n - 1) return 1;
93 if (y == 1) return 0;
94 }
95 return 0;
96}

引用了 n, sprp_check_u32(), t , 以及 urem32_preinv().

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

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

◆ urem32_preinv()

ulong urem32_preinv ( ulong t,
ulong n,
ulong dinv )
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

在文件 is_prime_uint.c 第 32 行定义.

32 {
33 ulong q = _umul64to64hi_(t, dinv);
34 ulong r = t - q * n;
35 if (r >= n) r += n;
36 return r;
37}
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)

引用了 _umul64to64hi_(), n, t , 以及 urem32_preinv().

被这些函数引用 powmod2b_u32(), sprp_check_u32() , 以及 urem32_preinv().

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