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

浏览该文件的源代码.

宏定义

#define MONT63_MAX   ((ulong)(0x7fffffffffffffff))
 Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ULONG_PRIME_MAX   0xFFFFFFFFFFFFFFC5ull
#define ULONG_PRIME_MIN   2

函数

bool lmmp_is_prime_ulong_ (ulong n)
 判断素数
bool lmmp_is_prime_ulong_notrial_ (ulong n)
 判断素数(无试除法,单 limb 档)
ulong lmmp_next_prime_ulong_ (ulong n)
 大于n的下一个素数
ulong lmmp_prev_prime_ulong_ (ulong n)
 小于等于n的上一个素数
static ulong mont63_mul (ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont63_R2 (ulong m)
static ulong mont63_reduce (u128 t, ulong m, ulong m_inv)
static ulong mont64_mul (ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont64_R2 (ulong m)
static ulong mont64_reduce (u128 t, ulong m, ulong m_inv)
static ulong mont_R2 (ulong m)
static ulong powmod2_63 (ulong d, ulong R2, ulong m, ulong m_inv)
static ulong powmod2_64 (ulong d, ulong R2, ulong m, ulong m_inv)
static void powmod2_win3_63 (ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv)
static void powmod2_win3_64 (ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv)
static void powmod_win3_63 (ulong *pv, ulong bm, ulong d, int ebits, ulong m, ulong m_inv)
static int sprp_check63 (ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1)
static int sprp_check64 (ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1)
static ulong to_mont63 (ulong x, ulong R2, ulong m, ulong m_inv)
static ulong to_mont64 (ulong x, ulong R2, ulong m, ulong m_inv)
static int trial_div16 (ulong n)

宏定义说明

◆ MONT63_MAX

#define MONT63_MAX   ((ulong)(0x7fffffffffffffff))

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_ulong.c 第 36 行定义.

被这些函数引用 lmmp_is_prime_ulong_notrial_(), lmmp_mod_4chunk_1_(), lmmp_mod_8chunk_1_() , 以及 lmmp_powmod_ulong_odd_().

◆ ULONG_PRIME_MAX

#define ULONG_PRIME_MAX   0xFFFFFFFFFFFFFFC5ull

在文件 is_prime_ulong.c 第 364 行定义.

被这些函数引用 lmmp_next_prime_ulong_().

◆ ULONG_PRIME_MIN

#define ULONG_PRIME_MIN   2

在文件 is_prime_ulong.c 第 365 行定义.

被这些函数引用 lmmp_prev_prime_ulong_().

函数说明

◆ lmmp_is_prime_ulong_()

bool lmmp_is_prime_ulong_ ( ulong n)

判断素数

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

在文件 is_prime_ulong.c 第 345 行定义.

345 {
346 if (n == 2)
347 return true;
348 if (n % 2 == 0 || n <= 1)
349 return false;
350 if (n <= MP_UINT_MAX) {
351 int judge = lmmp_is_prime_table_(n);
352 if (judge == 0) {
353 return false;
354 } else if (judge == 1) {
355 return true;
356 }
357 }
358 if (trial_div35711(n))
359 return false;
361}
#define MP_UINT_MAX
#define n
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
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_ulong_(), lmmp_is_prime_ulong_notrial_(), MP_UINT_MAX, n , 以及 trial_div35711().

被这些函数引用 bench_is_prime_ulong(), lmmp_is_prime_ulong_(), lmmp_is_prothprime_(), lmmp_powmod_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_is_prime_ulong_notrial_()

bool lmmp_is_prime_ulong_notrial_ ( ulong n)

判断素数(无试除法,单 limb 档)

参数
n待判断的数(建议为极有可能为素数的数)
注解
不进行试除法过滤,适用于判断已被小素数试除法过滤的数或强伪素数
警告
n>2
返回
若 n 为素数,返回 true,否则返回 false

在文件 is_prime_ulong.c 第 257 行定义.

257 {
258 lmmp_param_assert(n > 2);
259 if (n <= MP_UINT_MAX) {
260 if (n % 2 == 0)
261 return false;
263 } else if (n < 684630005672341) {
264 ushort bases[2];
265 bases[0] = 2;
266 bases[1] = dj_base49[((0x3AC69A35UL * n) & 0xFFFFFFFFUL) >> 21] + 3;
267 if (n % bases[0] == 0)
268 return false;
269 if (n % bases[1] == 0)
270 return false;
271
272 ulong m_inv = -lmmp_binvert_ulong_(n);
273 ulong R2 = mont63_R2(n);
274 ulong one = to_mont63(1, R2, n, m_inv);
275 ulong m_1 = to_mont63(n - 1, R2, n, m_inv);
276
277 ulong d;
278 ulong t;
279 ctz_shr_u64(d, n - 1, t);
280 int eb = lmmp_limb_bits_(d);
281
282 ulong v2 = powmod2_63(d, R2, n, m_inv);
283 if (!sprp_check63(v2, t, n, m_inv, one, m_1)) return false;
284
285 ulong v;
286 powmod_win3_63(&v, to_mont63(bases[1], R2, n, m_inv), d, eb, n, m_inv);
287 return sprp_check63(v, t, n, m_inv, one, m_1);
288 } else {
289 ushort bases[3];
290 ulong bbmask = dj_base64[((0x3AC69A35UL * n) & 0xFFFFFFFFUL) >> 18];
291 bases[0] = 2;
292 bases[1] = (bbmask & 0x8000) ? 26460 : 9375;
293 bases[2] = (bbmask & 0x7FFF) + 3;
294
295 if (n % bases[0] == 0)
296 return false;
297 if (n % bases[1] == 0)
298 return false;
299 if (n % bases[2] == 0)
300 return n == bases[2];
301
302 ulong one = 1;
303 ulong m_1 = n - 1;
304 ulong m_inv = -lmmp_binvert_ulong_(n);
305
306 ulong d;
307 ulong t;
308 ctz_shr_u64(d, n - 1, t);
309 int eb = lmmp_limb_bits_(d);
310
311 if (n <= MONT63_MAX) {
312 ulong R2 = mont63_R2(n);
313 one = to_mont63(one, R2, n, m_inv);
314 m_1 = to_mont63(m_1, R2, n, m_inv);
315
316 ulong v2 = powmod2_63(d, R2, n, m_inv);
317 if (!sprp_check63(v2, t, n, m_inv, one, m_1)) return false;
318
319 /* 双基底交错 + 3 位窗口 */
320 ulong bm1 = to_mont63(bases[1], R2, n, m_inv);
321 ulong bm2 = to_mont63(bases[2], R2, n, m_inv);
322 ulong v1, v2_;
323 powmod2_win3_63(&v1, &v2_, bm1, bm2, d, eb, n, m_inv);
324 if (!sprp_check63(v1, t, n, m_inv, one, m_1)) return false;
325 return sprp_check63(v2_, t, n, m_inv, one, m_1);
326 } else {
327 ulong R2 = mont64_R2(n);
328 one = to_mont64(one, R2, n, m_inv);
329 m_1 = to_mont64(m_1, R2, n, m_inv);
330
331 ulong v2 = powmod2_64(d, R2, n, m_inv);
332 if (!sprp_check64(v2, t, n, m_inv, one, m_1)) return false;
333
334 /* 双基底交错 + 3 位窗口 */
335 ulong bm1 = to_mont64(bases[1], R2, n, m_inv);
336 ulong bm2 = to_mont64(bases[2], R2, n, m_inv);
337 ulong v1, v2_;
338 powmod2_win3_64(&v1, &v2_, bm1, bm2, d, eb, n, m_inv);
339 if (!sprp_check64(v1, t, n, m_inv, one, m_1)) return false;
340 return sprp_check64(v2_, t, n, m_inv, one, m_1);
341 }
342 }
343}
#define lmmp_limb_bits_
const uint16_t dj_base49[2048]
Copyright (C) 2026 HJimmyK (Jericho Knox)
const uint16_t dj_base64[16384]
bool lmmp_is_prime_uint_notrial_(uint n)
u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
static ulong mont64_R2(ulong m)
static void powmod_win3_63(ulong *pv, ulong bm, ulong d, int ebits, ulong m, ulong m_inv)
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ulong to_mont63(ulong x, ulong R2, ulong m, ulong m_inv)
static ulong mont63_R2(ulong m)
static ulong powmod2_63(ulong d, ulong R2, ulong m, ulong m_inv)
static int sprp_check64(ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1)
static int sprp_check63(ulong v, ulong t, ulong m, ulong m_inv, ulong one, ulong m_1)
static void powmod2_win3_64(ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv)
static void powmod2_win3_63(ulong *pv1, ulong *pv2, ulong bm1, ulong bm2, ulong d, int ebits, ulong m, ulong m_inv)
static ulong powmod2_64(ulong d, ulong R2, ulong m, ulong m_inv)
static ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv)
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define bm1
#define v1
#define v2
#define t
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint32_t uint
定义 numth.h:38
uint16_t ushort
定义 numth.h:36
uint64_t ulong
定义 numth.h:39

引用了 bm1, ctz_shr_u64, dj_base49, dj_base64, lmmp_binvert_ulong_(), lmmp_is_prime_uint_notrial_(), lmmp_is_prime_ulong_notrial_(), lmmp_limb_bits_, LMMP_NOINLINE, lmmp_param_assert, MONT63_MAX, mont63_R2(), mont64_R2(), MP_UINT_MAX, n, powmod2_63(), powmod2_64(), powmod2_win3_63(), powmod2_win3_64(), powmod_win3_63(), sprp_check63(), sprp_check64(), t, to_mont63(), to_mont64(), v1 , 以及 v2.

被这些函数引用 bench_is_prime_ulong_notrial(), lmmp_is_prime_ulong_(), lmmp_is_prime_ulong_notrial_(), lmmp_next_prime_ulong_(), lmmp_powmod_(), lmmp_prev_prime_ulong_(), TEST_CASE(), TEST_CASE() , 以及 TEST_CASE().

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

◆ lmmp_next_prime_ulong_()

ulong lmmp_next_prime_ulong_ ( ulong n)

大于n的下一个素数

参数
n起始点(不含)
警告
如果 n 大于等于ulong可表示最大的质数,则返回ulong_max
返回
大于n的下一个素数

在文件 is_prime_ulong.c 第 375 行定义.

375 {
378 return prime_short_table[idx];
379 } else if (n >= ULONG_PRIME_MAX) {
380 return MP_ULONG_MAX;
381 } else {
382 n += (n % 2 == 0) ? 1 : 2;
383 while (1) {
384 if (trial_div16(n)) {
385 n += 2;
386 } else {
388 return n;
389 } else {
390 n += 2;
391 }
392 }
393 }
394 }
395}
static int trial_div16(ulong n)
#define ULONG_PRIME_MAX
#define MP_ULONG_MAX
#define PRIME_SHORT_TABLE_SIZE
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量

引用了 lmmp_is_prime_ulong_notrial_(), lmmp_next_prime_ulong_(), lmmp_prime_cnt16_(), MP_ULONG_MAX, n, prime_short_table, PRIME_SHORT_TABLE_SIZE, trial_div16() , 以及 ULONG_PRIME_MAX.

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

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

◆ lmmp_prev_prime_ulong_()

ulong lmmp_prev_prime_ulong_ ( ulong n)

小于等于n的上一个素数

参数
n起始点(含)
警告
如果 n 小于2,则返回 0
返回
小于等于n的上一个素数,如果n恰好为素数,则返回 n

在文件 is_prime_ulong.c 第 397 行定义.

397 {
398 if (n < ULONG_PRIME_MIN) {
399 return 0;
400 } else if (n < PRIME_SHORT_TABLE_N) {
402 return prime_short_table[idx - 1];
403 } else {
404 n -= (n % 2 == 0) ? 1 : 0;
405 while (1) {
406 if (trial_div16(n)) {
407 n -= 2;
408 } else {
410 return n;
411 } else {
412 n -= 2;
413 }
414 }
415 }
416 }
417}
#define ULONG_PRIME_MIN
#define PRIME_SHORT_TABLE_N

引用了 lmmp_is_prime_ulong_notrial_(), lmmp_prev_prime_ulong_(), lmmp_prime_cnt16_(), n, prime_short_table, PRIME_SHORT_TABLE_N, trial_div16() , 以及 ULONG_PRIME_MIN.

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

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

◆ mont63_mul()

ulong mont63_mul ( ulong a,
ulong b,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 83 行定义.

83 {
84 return mont63_reduce((u128)a * b, m, m_inv);
85}
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)

引用了 mont63_mul() , 以及 mont63_reduce().

被这些函数引用 lmmp_mod_4chunk_1_(), lmmp_mod_8chunk_1_(), lmmp_powmod_ulong_odd_(), mont63_mul(), mont63_mul(), mont63_mul(), powmod2_63(), powmod2_win3_63(), powmod_win3_63() , 以及 sprp_check63().

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

◆ mont63_R2()

ulong mont63_R2 ( ulong m)
inlinestatic

在文件 is_prime_ulong.c 第 75 行定义.

75 {
76 return mont_R2(m);
77}
static ulong mont_R2(ulong m)

引用了 mont63_R2() , 以及 mont_R2().

被这些函数引用 lmmp_is_prime_ulong_notrial_(), lmmp_powmod_ulong_odd_(), mont63_R2() , 以及 mont63_R2().

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

◆ mont63_reduce()

ulong mont63_reduce ( u128 t,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 67 行定义.

67 {
68 // m < 2^63 时 k*m + t < 2^127,无 129 位溢出
69 ulong k = _u128low(t) * m_inv;
70 u128 sum = (u128)k * m + t;
71 ulong hi = _u128high(sum);
72 return hi >= m ? hi - m : hi;
73}
#define k

引用了 k, mont63_reduce() , 以及 t.

被这些函数引用 from_mont63(), mont63_mul(), mont63_mul(), mont63_mul(), mont63_reduce(), mont63_reduce(), mont63_reduce(), to_mont63() , 以及 to_mont63().

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

◆ mont64_mul()

ulong mont64_mul ( ulong a,
ulong b,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 63 行定义.

63 {
64 return mont64_reduce((u128)a * b, m, m_inv);
65}
static ulong mont64_reduce(u128 t, ulong m, ulong m_inv)

引用了 mont64_mul() , 以及 mont64_reduce().

被这些函数引用 lmmp_powmod_ulong_odd_(), mont64_mul(), mont64_mul(), powmod2_64(), powmod2_win3_64() , 以及 sprp_check64().

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

◆ mont64_R2()

ulong mont64_R2 ( ulong m)
inlinestatic

在文件 is_prime_ulong.c 第 55 行定义.

55 {
56 return mont_R2(m);
57}

引用了 mont64_R2() , 以及 mont_R2().

被这些函数引用 lmmp_is_prime_ulong_notrial_(), lmmp_powmod_ulong_odd_(), mont64_R2() , 以及 mont64_R2().

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

◆ mont64_reduce()

ulong mont64_reduce ( u128 t,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 38 行定义.

38 {
39 // sum = k*m + t < 2^129,第 129 位 c 由 128 位回绕捕获
40 ulong k = _u128low(t) * m_inv;
41 u128 km = (u128)k * m;
42 u128 sum = km + t;
43 uint c = sum < km;
44 ulong hi = _u128high(sum);
45 if (c) return hi - m; // 2^128 + hi - m 的低 128 位高位即结果
46 return hi >= m ? hi - m : hi;
47}

引用了 k, mont64_reduce() , 以及 t.

被这些函数引用 from_mont64(), mont64_mul(), mont64_mul(), mont64_reduce(), mont64_reduce(), to_mont64() , 以及 to_mont64().

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

◆ mont_R2()

ulong mont_R2 ( ulong m)
inlinestatic

在文件 is_prime_ulong.c 第 49 行定义.

49 {
50 mp_bitcnt_t shift = 0;
51 clz_shl_u64(m, m, shift);
52 return _bpow_preinv_(m, shift, 2, lmmp_inv_1_(m));
53}
size_t mp_bitcnt_t
定义 lmmp.h:98
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
static uint64_t _bpow_preinv_(uint64_t m, uint64_t k, int nb, uint64_t inv)
#define clz_shl_u64(r, x, cnt)

引用了 _bpow_preinv_(), clz_shl_u64, lmmp_inv_1_() , 以及 mont_R2().

被这些函数引用 mont63_R2(), mont63_R2(), mont64_R2(), mont64_R2(), mont_R2() , 以及 mont_R2().

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

◆ powmod2_63()

ulong powmod2_63 ( ulong d,
ulong R2,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 116 行定义.

116 {
117 ulong v = to_mont63(1, R2, m, m_inv);
118 ulong base = to_mont63(2, R2, m, m_inv);
119 while (1) {
120 if (d & 1) v = mont63_mul(v, base, m, m_inv);
121 d >>= 1;
122 if (d == 0) break;
123 base = mont63_mul(base, base, m, m_inv);
124 }
125 return v;
126}
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)

引用了 mont63_mul(), powmod2_63() , 以及 to_mont63().

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

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

◆ powmod2_64()

ulong powmod2_64 ( ulong d,
ulong R2,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 128 行定义.

128 {
129 ulong v = to_mont64(1, R2, m, m_inv);
130 ulong base = to_mont64(2, R2, m, m_inv);
131 while (1) {
132 if (d & 1) v = mont64_mul(v, base, m, m_inv);
133 d >>= 1;
134 if (d == 0) break;
135 base = mont64_mul(base, base, m, m_inv);
136 }
137 return v;
138}
static ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv)

引用了 mont64_mul(), powmod2_64() , 以及 to_mont64().

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

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

◆ powmod2_win3_63()

void powmod2_win3_63 ( ulong * pv1,
ulong * pv2,
ulong bm1,
ulong bm2,
ulong d,
int ebits,
ulong m,
ulong m_inv )
static

在文件 is_prime_ulong.c 第 167 行定义.

167 {
168 ulong w1[8], w2[8], v1 = bm1, v2 = bm2;
169 int bit = ebits - 2;
170 w1[1] = bm1;
171 w1[2] = mont63_mul(bm1, bm1, m, m_inv);
172 w1[3] = mont63_mul(w1[2], bm1, m, m_inv);
173 w1[4] = mont63_mul(w1[2], w1[2], m, m_inv);
174 w1[5] = mont63_mul(w1[4], bm1, m, m_inv);
175 w1[6] = mont63_mul(w1[3], w1[3], m, m_inv);
176 w1[7] = mont63_mul(w1[6], bm1, m, m_inv);
177 w2[1] = bm2;
178 w2[2] = mont63_mul(bm2, bm2, m, m_inv);
179 w2[3] = mont63_mul(w2[2], bm2, m, m_inv);
180 w2[4] = mont63_mul(w2[2], w2[2], m, m_inv);
181 w2[5] = mont63_mul(w2[4], bm2, m, m_inv);
182 w2[6] = mont63_mul(w2[3], w2[3], m, m_inv);
183 w2[7] = mont63_mul(w2[6], bm2, m, m_inv);
184 while (bit >= 2) {
185 v1 = mont63_mul(v1, v1, m, m_inv);
186 v2 = mont63_mul(v2, v2, m, m_inv);
187 v1 = mont63_mul(v1, v1, m, m_inv);
188 v2 = mont63_mul(v2, v2, m, m_inv);
189 v1 = mont63_mul(v1, v1, m, m_inv);
190 v2 = mont63_mul(v2, v2, m, m_inv);
191 {
192 uint idx = (uint)(d >> (bit - 2)) & 7;
193 if (idx) {
194 v1 = mont63_mul(v1, w1[idx], m, m_inv);
195 v2 = mont63_mul(v2, w2[idx], m, m_inv);
196 }
197 }
198 bit -= 3;
199 }
200 for (; bit >= 0; bit--) {
201 v1 = mont63_mul(v1, v1, m, m_inv);
202 v2 = mont63_mul(v2, v2, m, m_inv);
203 if ((d >> bit) & 1) {
204 v1 = mont63_mul(v1, bm1, m, m_inv);
205 v2 = mont63_mul(v2, bm2, m, m_inv);
206 }
207 }
208 *pv1 = v1;
209 *pv2 = v2;
210}
#define w2

引用了 bm1, mont63_mul(), powmod2_win3_63(), v1, v2 , 以及 w2.

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

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

◆ powmod2_win3_64()

void powmod2_win3_64 ( ulong * pv1,
ulong * pv2,
ulong bm1,
ulong bm2,
ulong d,
int ebits,
ulong m,
ulong m_inv )
static

在文件 is_prime_ulong.c 第 212 行定义.

212 {
213 ulong w1[8], w2[8], v1 = bm1, v2 = bm2;
214 int bit = ebits - 2;
215 w1[1] = bm1;
216 w1[2] = mont64_mul(bm1, bm1, m, m_inv);
217 w1[3] = mont64_mul(w1[2], bm1, m, m_inv);
218 w1[4] = mont64_mul(w1[2], w1[2], m, m_inv);
219 w1[5] = mont64_mul(w1[4], bm1, m, m_inv);
220 w1[6] = mont64_mul(w1[3], w1[3], m, m_inv);
221 w1[7] = mont64_mul(w1[6], bm1, m, m_inv);
222 w2[1] = bm2;
223 w2[2] = mont64_mul(bm2, bm2, m, m_inv);
224 w2[3] = mont64_mul(w2[2], bm2, m, m_inv);
225 w2[4] = mont64_mul(w2[2], w2[2], m, m_inv);
226 w2[5] = mont64_mul(w2[4], bm2, m, m_inv);
227 w2[6] = mont64_mul(w2[3], w2[3], m, m_inv);
228 w2[7] = mont64_mul(w2[6], bm2, m, m_inv);
229 while (bit >= 2) {
230 v1 = mont64_mul(v1, v1, m, m_inv);
231 v2 = mont64_mul(v2, v2, m, m_inv);
232 v1 = mont64_mul(v1, v1, m, m_inv);
233 v2 = mont64_mul(v2, v2, m, m_inv);
234 v1 = mont64_mul(v1, v1, m, m_inv);
235 v2 = mont64_mul(v2, v2, m, m_inv);
236 {
237 uint idx = (uint)(d >> (bit - 2)) & 7;
238 if (idx) {
239 v1 = mont64_mul(v1, w1[idx], m, m_inv);
240 v2 = mont64_mul(v2, w2[idx], m, m_inv);
241 }
242 }
243 bit -= 3;
244 }
245 for (; bit >= 0; bit--) {
246 v1 = mont64_mul(v1, v1, m, m_inv);
247 v2 = mont64_mul(v2, v2, m, m_inv);
248 if ((d >> bit) & 1) {
249 v1 = mont64_mul(v1, bm1, m, m_inv);
250 v2 = mont64_mul(v2, bm2, m, m_inv);
251 }
252 }
253 *pv1 = v1;
254 *pv2 = v2;
255}

引用了 bm1, mont64_mul(), powmod2_win3_64(), v1, v2 , 以及 w2.

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

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

◆ powmod_win3_63()

void powmod_win3_63 ( ulong * pv,
ulong bm,
ulong d,
int ebits,
ulong m,
ulong m_inv )
static

在文件 is_prime_ulong.c 第 140 行定义.

140 {
141 ulong w[8], v = bm;
142 int bit = ebits - 2;
143 w[1] = bm;
144 w[2] = mont63_mul(bm, bm, m, m_inv);
145 w[3] = mont63_mul(w[2], bm, m, m_inv);
146 w[4] = mont63_mul(w[2], w[2], m, m_inv);
147 w[5] = mont63_mul(w[4], bm, m, m_inv);
148 w[6] = mont63_mul(w[3], w[3], m, m_inv);
149 w[7] = mont63_mul(w[6], bm, m, m_inv);
150 while (bit >= 2) {
151 v = mont63_mul(v, v, m, m_inv);
152 v = mont63_mul(v, v, m, m_inv);
153 v = mont63_mul(v, v, m, m_inv);
154 {
155 uint idx = (uint)(d >> (bit - 2)) & 7;
156 if (idx) v = mont63_mul(v, w[idx], m, m_inv);
157 }
158 bit -= 3;
159 }
160 for (; bit >= 0; bit--) {
161 v = mont63_mul(v, v, m, m_inv);
162 if ((d >> bit) & 1) v = mont63_mul(v, bm, m, m_inv);
163 }
164 *pv = v;
165}

引用了 mont63_mul() , 以及 powmod_win3_63().

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

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

◆ sprp_check63()

int sprp_check63 ( ulong v,
ulong t,
ulong m,
ulong m_inv,
ulong one,
ulong m_1 )
inlinestatic

在文件 is_prime_ulong.c 第 91 行定义.

91 {
92 if (v == one || v == m_1) return 1;
93 for (t--; t > 0; t--) {
94 v = mont63_mul(v, v, m, m_inv);
95 if (v == m_1) return 1;
96 if (v == one) return 0;
97 }
98 return 0;
99}

引用了 mont63_mul(), sprp_check63() , 以及 t.

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

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

◆ sprp_check64()

int sprp_check64 ( ulong v,
ulong t,
ulong m,
ulong m_inv,
ulong one,
ulong m_1 )
inlinestatic

在文件 is_prime_ulong.c 第 101 行定义.

101 {
102 if (v == one || v == m_1) return 1;
103 for (t--; t > 0; t--) {
104 v = mont64_mul(v, v, m, m_inv);
105 if (v == m_1) return 1;
106 if (v == one) return 0;
107 }
108 return 0;
109}

引用了 mont64_mul(), sprp_check64() , 以及 t.

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

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

◆ to_mont63()

ulong to_mont63 ( ulong x,
ulong R2,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 79 行定义.

79 {
80 return mont63_reduce((u128)x * R2, m, m_inv);
81}

引用了 mont63_reduce() , 以及 to_mont63().

被这些函数引用 lmmp_is_prime_ulong_notrial_(), lmmp_powmod_ulong_odd_(), powmod2_63(), to_mont63() , 以及 to_mont63().

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

◆ to_mont64()

ulong to_mont64 ( ulong x,
ulong R2,
ulong m,
ulong m_inv )
inlinestatic

在文件 is_prime_ulong.c 第 59 行定义.

59 {
60 return mont64_reduce((u128)x * R2, m, m_inv);
61}

引用了 mont64_reduce() , 以及 to_mont64().

被这些函数引用 lmmp_is_prime_ulong_notrial_(), lmmp_powmod_ulong_odd_(), powmod2_64(), to_mont64() , 以及 to_mont64().

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

◆ trial_div16()

int trial_div16 ( ulong n)
inlinestatic

在文件 is_prime_ulong.c 第 367 行定义.

367 {
368 return trial_div35711(n)
369 || n % 13 == 0 || n % 17 == 0 || n % 19 == 0 || n % 23 == 0
370 || n % 29 == 0 || n % 31 == 0 || n % 37 == 0 || n % 41 == 0
371 || n % 43 == 0 || n % 47 == 0 || n % 53 == 0 || n % 59 == 0
372 || n % 61 == 0 || n % 67 == 0 || n % 71 == 0;
373}

引用了 n, trial_div16() , 以及 trial_div35711().

被这些函数引用 lmmp_next_prime_ulong_(), lmmp_prev_prime_ulong_() , 以及 trial_div16().

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