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

浏览该文件的源代码.

宏定义

#define abound0   ll_trial_primes[i][2]
#define abound1   ll_trial_primes[i][3]
#define ainv0   ll_trial_primes[i][0]
#define ainv1   ll_trial_primes[i][1]
#define bbound0   ll_trial_primes[i + 1][2]
#define bbound1   ll_trial_primes[i + 1][3]
#define binv0   ll_trial_primes[i + 1][0]
#define binv1   ll_trial_primes[i + 1][1]
#define FAST_TRIAL_BOUND   (MP_ULONG_MAX - 137)

函数

static int bitlen_2 (u128 x)
static u128 factor_2adic (u128 x, slong *t)
static int is2_notrial_i_ (mp_limb_t lo, mp_limb_t hi)
static int is_square_2 (u128 n)
static int jacobi_D (uint Dabs, int Dneg, u128 n)
static int jacobi_small (ulong b, ulong A)
static int ll_le (u128 a, u128 b)
static void ll_small_2_powmod (ulong y[2], u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static int ll_small_is_prime_mr (u128 n, u128 minv, u128 d, int ebits, slong t, int nb)
static void ll_small_mul1_ (ulong *r1, ulong *r0, ulong a1, ulong a0, ulong b)
static void ll_small_powmod_2ch_ (ulong y1[2], ulong y2[2], ulong b1, ulong b2, u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_powmod_3_ (ulong y1[2], ulong y2[2], ulong y3[2], ulong b1, ulong b2, ulong b3, u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_preinv (u128 *minv, u128 n)
static void ll_small_reduce2_precise (ulong *r1, ulong *r0, ulong x1, ulong x0, ulong n1, ulong n0, ulong minv1)
static int ll_small_sprp_stage2 (ulong y1, ulong y0, slong t, ulong nm1_1, ulong nm1_0, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_sqrmod (ulong *r1, ulong *r0, ulong a1, ulong a0, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_sqrmod_sloppy (ulong *r1, ulong *r0, ulong a1, ulong a0, ulong n1, ulong n0, ulong minv1, ulong minv0)
int lmmp_is_prime_2_ (mp_limb_t lo, mp_limb_t hi)
 判断 128 位素数
int lmmp_is_prime_2_notrial_ (mp_limb_t lo, mp_limb_t hi)
 判断 128 位素数(无试除法)
static u128 mont2_dbl (u128 a, u128 n)
static int mont2_lucas_strong_ (u128 n, u128 ninv, u128 R2)
static u128 mont2_mul_2 (u128 a, u128 b, u128 n, u128 ninv)
static u128 mont2_neg (u128 a, u128 n)
static u128 mont2_powmod_2_ (u128 d, int ebits, u128 R2, u128 n, u128 ninv)
static void mont2_preinv (u128 *ninv, u128 *R2, u128 n)
static u128 mont2_redc (u128 thi, u128 tlo, u128 n, u128 ninv)
static u128 mont2_redc_mul_1 (u128 a, ulong b, u128 n, u128 ninv)
static int mont2_sprp_stage2 (u128 y, slong t, u128 one, u128 m_1, u128 n, u128 ninv)
static u128 mont2_sqr (u128 a, u128 n, u128 ninv)
static u128 mont2_sub (u128 a, u128 b, u128 n)
static u128 mont2_to_mont1 (ulong x, u128 R2, u128 n, u128 ninv)
static u128 mont2_to_mont2 (u128 a, u128 R2, u128 n, u128 ninv)
static void mul_128 (u128 a, u128 b, u128 *hi, u128 *lo)
static void sqr_128 (u128 a, u128 *hi, u128 *lo)

变量

static const ulong ll_trial_primes [32][4]
 Copyright (C) 2026 HJimmyK (Jericho Knox)

宏定义说明

◆ abound0

#define abound0   ll_trial_primes[i][2]

被这些函数引用 lmmp_is_prime_2_().

◆ abound1

#define abound1   ll_trial_primes[i][3]

被这些函数引用 lmmp_is_prime_2_().

◆ ainv0

#define ainv0   ll_trial_primes[i][0]

被这些函数引用 lmmp_is_prime_2_().

◆ ainv1

#define ainv1   ll_trial_primes[i][1]

被这些函数引用 lmmp_is_prime_2_().

◆ bbound0

#define bbound0   ll_trial_primes[i + 1][2]

被这些函数引用 lmmp_is_prime_2_().

◆ bbound1

#define bbound1   ll_trial_primes[i + 1][3]

被这些函数引用 lmmp_is_prime_2_().

◆ binv0

#define binv0   ll_trial_primes[i + 1][0]

被这些函数引用 lmmp_is_prime_2_().

◆ binv1

#define binv1   ll_trial_primes[i + 1][1]

被这些函数引用 lmmp_is_prime_2_().

◆ FAST_TRIAL_BOUND

#define FAST_TRIAL_BOUND   (MP_ULONG_MAX - 137)

在文件 is_prime_2.c 第 73 行定义.

被这些函数引用 lmmp_is_prime_2_().

函数说明

◆ bitlen_2()

int bitlen_2 ( u128 x)
inlinestatic

在文件 is_prime_2.c 第 222 行定义.

222 {
223 if (_u128high(x) != 0) return 128 - lmmp_leading_zeros_(_u128high(x));
224 return 64 - lmmp_leading_zeros_(_u128low(x));
225}
#define lmmp_leading_zeros_

引用了 bitlen_2() , 以及 lmmp_leading_zeros_.

被这些函数引用 bitlen_2(), is2_notrial_i_() , 以及 mont2_lucas_strong_().

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

◆ factor_2adic()

u128 factor_2adic ( u128 x,
slong * t )
inlinestatic

在文件 is_prime_2.c 第 228 行定义.

228 {
229 if (_u128low(x) == 0) {
230 *t = 64 + lmmp_tailing_zeros_(_u128high(x));
231 return (u128)_u128high(x) >> (*t - 64);
232 }
233 *t = lmmp_tailing_zeros_(_u128low(x));
234 return x >> *t;
235}
#define lmmp_tailing_zeros_
#define t

引用了 factor_2adic(), lmmp_tailing_zeros_ , 以及 t.

被这些函数引用 factor_2adic(), is2_notrial_i_() , 以及 mont2_lucas_strong_().

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

◆ is2_notrial_i_()

int is2_notrial_i_ ( mp_limb_t lo,
mp_limb_t hi )
static

在文件 is_prime_2.c 第 687 行定义.

687 {
688 u128 n, nm1, d;
689 slong t;
690 int ebits;
691
692 n = ((u128)hi << 64) | lo;
693 nm1 = n - 1;
694 d = factor_2adic(nm1, &t);
695 ebits = bitlen_2(d);
696
697 /* SWbound = psi_13 (Sorenson-Webster):确定性基底档走 1.5-limb
698 sloppy 算术(返回 1 = 确定素数) */
699 if (n < ((((u128)0x2be69) << 64) | 0x51adc5b22410a5fd)) {
700 ulong minv1, minv0, nm1_1, nm1_0, y[2];
701 u128 minv;
702
703 ll_small_preinv(&minv, n);
704 minv0 = _u128low(minv);
705 minv1 = _u128high(minv);
706 _sub_ddmmss(nm1_1, nm1_0, hi, lo, 0, 1);
707
708 ll_small_2_powmod(y, d, ebits, hi, lo, minv1, minv0);
709 if (!ll_small_sprp_stage2(y[1], y[0], t, nm1_1, nm1_0, hi, lo, minv1, minv0)) return 0;
710
711 /* psi_12 台阶:n < psi_12 时 12 基底(2 + {3..37})已确定 */
712 {
713 int nb = n >= ((((u128)0x437a) << 64) | 0xe92817f9fc85b7e5) ? 12 : 11;
714 return ll_small_is_prime_mr(n, minv, d, ebits, t, nb) ? 1 : 0;
715 }
716 }
717
718 /* BPSW 档(n >= psi_13,蒙域:V·V 与 Q 链全宽乘无 1.5-limb 窗口) */
719 {
720 u128 ninv, R2, one, m_1, y;
721
722 mont2_preinv(&ninv, &R2, n);
723 one = mont2_to_mont1(1, R2, n, ninv);
724 m_1 = mont2_to_mont2(nm1, R2, n, ninv);
725
726 y = mont2_powmod_2_(d, ebits, R2, n, ninv);
727 if (!mont2_sprp_stage2(y, t, one, m_1, n, ninv)) return 0;
728
729 return mont2_lucas_strong_(n, ninv, R2) ? 2 : 0;
730 }
731}
static int mont2_sprp_stage2(u128 y, slong t, u128 one, u128 m_1, u128 n, u128 ninv)
static u128 mont2_powmod_2_(u128 d, int ebits, u128 R2, u128 n, u128 ninv)
static int ll_small_sprp_stage2(ulong y1, ulong y0, slong t, ulong nm1_1, ulong nm1_0, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void mont2_preinv(u128 *ninv, u128 *R2, u128 n)
static int mont2_lucas_strong_(u128 n, u128 ninv, u128 R2)
static int bitlen_2(u128 x)
static u128 mont2_to_mont2(u128 a, u128 R2, u128 n, u128 ninv)
static void ll_small_2_powmod(ulong y[2], u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_preinv(u128 *minv, u128 n)
static u128 mont2_to_mont1(ulong x, u128 R2, u128 n, u128 ninv)
static int ll_small_is_prime_mr(u128 n, u128 minv, u128 d, int ebits, slong t, int nb)
static u128 factor_2adic(u128 x, slong *t)
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
#define n
#define lo
int64_t slong
定义 numth.h:41
uint64_t ulong
定义 numth.h:39

引用了 _sub_ddmmss, bitlen_2(), factor_2adic(), is2_notrial_i_(), ll_small_2_powmod(), ll_small_is_prime_mr(), ll_small_preinv(), ll_small_sprp_stage2(), LMMP_NOINLINE, lo, mont2_lucas_strong_(), mont2_powmod_2_(), mont2_preinv(), mont2_sprp_stage2(), mont2_to_mont1(), mont2_to_mont2(), n , 以及 t.

被这些函数引用 is2_notrial_i_(), lmmp_is_prime_2_() , 以及 lmmp_is_prime_2_notrial_().

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

◆ is_square_2()

int is_square_2 ( u128 n)
inlinestatic

在文件 is_prime_2.c 第 532 行定义.

532 {
533 ulong hi = _u128high(n), lo = _u128low(n);
534 ulong src[2], rr[2], r;
535 lmmp_debug_assert(hi != 0);
536 int nsh = lmmp_leading_zeros_(hi) / 2;
537 if (nsh) {
538 ulong limbs[2] = {lo, hi};
539 lmmp_shl_(src, limbs, 2, 2 * nsh);
540 } else {
541 src[0] = lo;
542 src[1] = hi;
543 }
544 r = lmmp_sqrt_2_(rr, src) >> nsh;
545 return (u128)r * r == n;
546}
#define lmmp_debug_assert(x)
定义 lmmp.h:498
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))

引用了 is_square_2(), lmmp_debug_assert, lmmp_leading_zeros_, lmmp_shl_(), lmmp_sqrt_2_(), lo , 以及 n.

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

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

◆ jacobi_D()

int jacobi_D ( uint Dabs,
int Dneg,
u128 n )
inlinestatic

在文件 is_prime_2.c 第 263 行定义.

263 {
264 ulong A = Dabs;
265 ulong Bm = (ulong)-1 % A + 1;
266 ulong b;
267 int sign = 1;
268 if (Bm >= A) Bm -= A; /* Bm = 2^64 mod A */
269 b = _u128high(n) % A;
270 b = (b * Bm + _u128low(n) % A) % A;
271 if ((A & 3) == 3 && (_u128low(n) & 3) == 3) sign = -sign;
272 sign *= jacobi_small(b, A);
273 if (sign == 0) return 0;
274 if (Dneg && (_u128low(n) & 3) == 3) sign = -sign;
275 return sign;
276}
#define A
static int jacobi_small(ulong b, ulong A)

引用了 A, jacobi_D(), jacobi_small() , 以及 n.

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

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

◆ jacobi_small()

int jacobi_small ( ulong b,
ulong A )
inlinestatic

在文件 is_prime_2.c 第 238 行定义.

238 {
239 int sign = 1;
240 if (b == 0) return 0;
241 for (;;) {
242 int tz = lmmp_tailing_zeros_(b);
243 b >>= tz;
244 if ((tz & 1) && ((A & 7) == 3 || (A & 7) == 5)) sign = -sign;
245 if (b == 1) return sign;
246 if (b < A) {
247 ulong s = b;
248 b = A;
249 A = s;
250 if ((b & 3) == 3 && (A & 3) == 3) sign = -sign;
251 }
252 b -= A;
253 if (b == 0) return 0;
254 }
255}
#define s

引用了 A, jacobi_small(), lmmp_tailing_zeros_ , 以及 s.

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

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

◆ ll_le()

int ll_le ( u128 a,
u128 b )
inlinestatic

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

75 {
76 return a <= b;
77}

引用了 ll_le().

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

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

◆ ll_small_2_powmod()

void ll_small_2_powmod ( ulong y[2],
u128 d,
int ebits,
ulong n1,
ulong n0,
ulong minv1,
ulong minv0 )
static

在文件 is_prime_2.c 第 380 行定义.

380 {
381 int k = ebits > 6 ? 6 : ebits;
382 int bit;
383 ulong r1 = 0, r0 = (ulong)1 << (ulong)(d >> (ebits - k));
384
385 for (bit = ebits - k - 1; bit >= 0; bit--) {
386 ll_small_sqrmod_sloppy(&r1, &r0, r1, r0, n1, n0, minv1, minv0);
387 if ((d >> bit) & 1) _add_ssaaaa(r1, r0, r1, r0, r1, r0);
388 }
389 ll_small_reduce2_precise(&y[1], &y[0], r1, r0, n1, n0, minv1);
390}
#define k
static void ll_small_reduce2_precise(ulong *r1, ulong *r0, ulong x1, ulong x0, ulong n1, ulong n0, ulong minv1)
static void ll_small_sqrmod_sloppy(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong n1, ulong n0, ulong minv1, ulong minv0)
#define _add_ssaaaa(sh, sl, ah, al, bh, bl)
#define r1
#define r0

引用了 _add_ssaaaa, k, ll_small_2_powmod(), ll_small_reduce2_precise(), ll_small_sqrmod_sloppy(), r0 , 以及 r1.

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

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

◆ ll_small_is_prime_mr()

int ll_small_is_prime_mr ( u128 n,
u128 minv,
u128 d,
int ebits,
slong t,
int nb )
static

在文件 is_prime_2.c 第 508 行定义.

508 {
509 static const uchar bases[12] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
510 ulong n1 = _u128high(n), n0 = _u128low(n);
511 ulong minv1 = _u128high(minv), minv0 = _u128low(minv);
512 ulong nm1[2], y1[2], y2[2], y3[2];
513 int j;
514
515 _sub_ddmmss(nm1[1], nm1[0], n1, n0, 0, 1);
516
517 for (j = 0; j + 3 <= nb; j += 3) {
518 ll_small_powmod_3_(y1, y2, y3, bases[j], bases[j + 1], bases[j + 2], d, ebits,
519 n1, n0, minv1, minv0);
520 if (!ll_small_sprp_stage2(y1[1], y1[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
521 if (!ll_small_sprp_stage2(y2[1], y2[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
522 if (!ll_small_sprp_stage2(y3[1], y3[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
523 }
524 if (nb == 11) {
525 ll_small_powmod_2ch_(y1, y2, bases[9], bases[10], d, ebits, n1, n0, minv1, minv0);
526 if (!ll_small_sprp_stage2(y1[1], y1[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
527 if (!ll_small_sprp_stage2(y2[1], y2[0], t, nm1[1], nm1[0], n1, n0, minv1, minv0)) return 0;
528 }
529 return 1;
530}
static void ll_small_powmod_2ch_(ulong y1[2], ulong y2[2], ulong b1, ulong b2, u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
static void ll_small_powmod_3_(ulong y1[2], ulong y2[2], ulong y3[2], ulong b1, ulong b2, ulong b3, u128 d, int ebits, ulong n1, ulong n0, ulong minv1, ulong minv0)
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34

引用了 _sub_ddmmss, ll_small_is_prime_mr(), ll_small_powmod_2ch_(), ll_small_powmod_3_(), ll_small_sprp_stage2(), n , 以及 t.

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

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

◆ ll_small_mul1_()

void ll_small_mul1_ ( ulong * r1,
ulong * r0,
ulong a1,
ulong a0,
ulong b )
inlinestatic

在文件 is_prime_2.c 第 372 行定义.

372 {
373 ulong t[2];
374
375 _umullo128x64_(a1, a0, b, t);
376 *r0 = t[0];
377 *r1 = t[1];
378}
static void _umullo128x64_(uint64_t a_high, uint64_t a_low, uint64_t b, uint64_t rr[2])
#define a0
#define a1

引用了 _umullo128x64_(), a0, a1, ll_small_mul1_(), r0, r1 , 以及 t.

被这些函数引用 ll_small_mul1_(), ll_small_powmod_2ch_() , 以及 ll_small_powmod_3_().

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

◆ ll_small_powmod_2ch_()

void ll_small_powmod_2ch_ ( ulong y1[2],
ulong y2[2],
ulong b1,
ulong b2,
u128 d,
int ebits,
ulong n1,
ulong n0,
ulong minv1,
ulong minv0 )
static

在文件 is_prime_2.c 第 464 行定义.

467 {
468 ulong xr1 = 0, xr0, yr1 = 0, yr0;
469 int bit;
470
471 if (ebits >= 3) {
472 ulong bit1 = (ulong)(d >> (ebits - 2)) & 1;
473 ulong bit2 = (ulong)(d >> (ebits - 3)) & 1;
474
475 xr0 = b1 * b1;
476 yr0 = b2 * b2;
477 if (bit1) {
478 xr0 *= b1;
479 yr0 *= b2;
480 }
481 xr0 = xr0 * xr0;
482 yr0 = yr0 * yr0;
483 if (bit2) {
484 xr0 *= b1;
485 yr0 *= b2;
486 }
487 bit = ebits - 4;
488 } else {
489 xr0 = b1;
490 yr0 = b2;
491 bit = ebits - 2;
492 }
493
494 for (; bit >= 0; bit--) {
495 ll_small_sqrmod_sloppy(&xr1, &xr0, xr1, xr0, n1, n0, minv1, minv0);
496 ll_small_sqrmod_sloppy(&yr1, &yr0, yr1, yr0, n1, n0, minv1, minv0);
497 if ((d >> bit) & 1) {
498 ll_small_mul1_(&xr1, &xr0, xr1, xr0, b1);
499 ll_small_mul1_(&yr1, &yr0, yr1, yr0, b2);
500 }
501 }
502 ll_small_reduce2_precise(&y1[1], &y1[0], xr1, xr0, n1, n0, minv1);
503 ll_small_reduce2_precise(&y2[1], &y2[0], yr1, yr0, n1, n0, minv1);
504}
static void ll_small_mul1_(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong b)
#define b1
#define b2

引用了 b1, b2, ll_small_mul1_(), ll_small_powmod_2ch_(), ll_small_reduce2_precise() , 以及 ll_small_sqrmod_sloppy().

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

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

◆ ll_small_powmod_3_()

void ll_small_powmod_3_ ( ulong y1[2],
ulong y2[2],
ulong y3[2],
ulong b1,
ulong b2,
ulong b3,
u128 d,
int ebits,
ulong n1,
ulong n0,
ulong minv1,
ulong minv0 )
static

在文件 is_prime_2.c 第 411 行定义.

415 {
416 ulong xr1 = 0, xr0, yr1 = 0, yr0, zr1 = 0, zr0;
417 int bit;
418
419 if (ebits >= 3) {
420 ulong bit1 = (ulong)(d >> (ebits - 2)) & 1;
421 ulong bit2 = (ulong)(d >> (ebits - 3)) & 1;
422
423 xr0 = b1 * b1;
424 yr0 = b2 * b2;
425 zr0 = b3 * b3;
426 if (bit1) {
427 xr0 *= b1;
428 yr0 *= b2;
429 zr0 *= b3;
430 }
431 xr0 = xr0 * xr0;
432 yr0 = yr0 * yr0;
433 zr0 = zr0 * zr0;
434 if (bit2) {
435 xr0 *= b1;
436 yr0 *= b2;
437 zr0 *= b3;
438 }
439 bit = ebits - 4;
440 } else {
441 xr0 = b1;
442 yr0 = b2;
443 zr0 = b3;
444 bit = ebits - 2;
445 }
446
447 for (; bit >= 0; bit--) {
448 ll_small_sqrmod_sloppy(&xr1, &xr0, xr1, xr0, n1, n0, minv1, minv0);
449 ll_small_sqrmod_sloppy(&yr1, &yr0, yr1, yr0, n1, n0, minv1, minv0);
450 ll_small_sqrmod_sloppy(&zr1, &zr0, zr1, zr0, n1, n0, minv1, minv0);
451 if ((d >> bit) & 1) {
452 ll_small_mul1_(&xr1, &xr0, xr1, xr0, b1);
453 ll_small_mul1_(&yr1, &yr0, yr1, yr0, b2);
454 ll_small_mul1_(&zr1, &zr0, zr1, zr0, b3);
455 }
456 }
457 ll_small_reduce2_precise(&y1[1], &y1[0], xr1, xr0, n1, n0, minv1);
458 ll_small_reduce2_precise(&y2[1], &y2[0], yr1, yr0, n1, n0, minv1);
459 ll_small_reduce2_precise(&y3[1], &y3[0], zr1, zr0, n1, n0, minv1);
460}
#define b3

引用了 b1, b2, b3, ll_small_mul1_(), ll_small_powmod_3_(), ll_small_reduce2_precise() , 以及 ll_small_sqrmod_sloppy().

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

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

◆ ll_small_preinv()

void ll_small_preinv ( u128 * minv,
u128 n )
static

在文件 is_prime_2.c 第 324 行定义.

324 {
325 ulong q[3], nn[4] = {0, 0, 0, 1}, d[2];
326
327 _u128store(d, n);
328 lmmp_div_2_(q, nn, 4, d);
329 *minv = ((u128)q[1] << 64) | q[0];
330}
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294

引用了 ll_small_preinv(), lmmp_div_2_() , 以及 n.

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

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

◆ ll_small_reduce2_precise()

void ll_small_reduce2_precise ( ulong * r1,
ulong * r0,
ulong x1,
ulong x0,
ulong n1,
ulong n0,
ulong minv1 )
inlinestatic

在文件 is_prime_2.c 第 360 行定义.

360 {
361 ulong t[2];
362
363 _umullo128x64_(n1, n0, _umul64to64hi_(x1, minv1), t);
364 _sub_ddmmss(x1, x0, x1, x0, t[1], t[0]);
365 while (x1 > n1 || (x1 == n1 && x0 >= n0))
366 _sub_ddmmss(x1, x0, x1, x0, n1, n0);
367 *r0 = x0;
368 *r1 = x1;
369}
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)

引用了 _sub_ddmmss, _umul64to64hi_(), _umullo128x64_(), ll_small_reduce2_precise(), r0, r1 , 以及 t.

被这些函数引用 ll_small_2_powmod(), ll_small_powmod_2ch_(), ll_small_powmod_3_() , 以及 ll_small_reduce2_precise().

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

◆ ll_small_sprp_stage2()

int ll_small_sprp_stage2 ( ulong y1,
ulong y0,
slong t,
ulong nm1_1,
ulong nm1_0,
ulong n1,
ulong n0,
ulong minv1,
ulong minv0 )
inlinestatic

在文件 is_prime_2.c 第 393 行定义.

396 {
397 if ((y1 == 0 && y0 == 1) || (y1 == nm1_1 && y0 == nm1_0)) return 1;
398 for (t--; t > 0; t--) {
399 ll_small_sqrmod(&y1, &y0, y1, y0, n1, n0, minv1, minv0);
400 if (y1 == nm1_1 && y0 == nm1_0) return 1;
401 }
402 return 0;
403}
static void ll_small_sqrmod(ulong *r1, ulong *r0, ulong a1, ulong a0, ulong n1, ulong n0, ulong minv1, ulong minv0)

引用了 ll_small_sprp_stage2(), ll_small_sqrmod() , 以及 t.

被这些函数引用 is2_notrial_i_(), ll_small_is_prime_mr() , 以及 ll_small_sprp_stage2().

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

◆ ll_small_sqrmod()

void ll_small_sqrmod ( ulong * r1,
ulong * r0,
ulong a1,
ulong a0,
ulong n1,
ulong n0,
ulong minv1,
ulong minv0 )
inlinestatic

在文件 is_prime_2.c 第 348 行定义.

351 {
352 ll_small_sqrmod_sloppy(r1, r0, a1, a0, n1, n0, minv1, minv0);
353 while (*r1 > n1 || (*r1 == n1 && *r0 >= n0))
354 _sub_ddmmss(*r1, *r0, *r1, *r0, n1, n0);
355}

引用了 _sub_ddmmss, a0, a1, ll_small_sqrmod(), ll_small_sqrmod_sloppy(), r0 , 以及 r1.

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

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

◆ ll_small_sqrmod_sloppy()

void ll_small_sqrmod_sloppy ( ulong * r1,
ulong * r0,
ulong a1,
ulong a0,
ulong n1,
ulong n0,
ulong minv1,
ulong minv0 )
inlinestatic

在文件 is_prime_2.c 第 333 行定义.

336 {
337 ulong s[3], q[2];
338 u128 t;
339
341 _umulhi128_sloppy_(s[2], s[1], minv1, minv0, q);
342 t = _umul128to128_(q[1], q[0], n1, n0);
343 _sub_ddmmss(*r1, *r0, s[1], s[0], _u128high(t), _u128low(t));
344}
static void _umulhi128_sloppy_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[2])
static void _usqr128to192_(uint64_t a_high, uint64_t a_low, uint64_t rr[3])
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)

引用了 _sub_ddmmss, _umul128to128_(), _umulhi128_sloppy_(), _usqr128to192_(), a0, a1, ll_small_sqrmod_sloppy(), r0, r1, s , 以及 t.

被这些函数引用 ll_small_2_powmod(), ll_small_powmod_2ch_(), ll_small_powmod_3_(), ll_small_sqrmod() , 以及 ll_small_sqrmod_sloppy().

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

◆ lmmp_is_prime_2_()

int lmmp_is_prime_2_ ( mp_limb_t lo,
mp_limb_t hi )

判断 128 位素数

参数
lo待判断数的低 64 位
hi待判断数的高 64 位
警告
hi>0
注解
在 lmmp_is_prime_2_notrial_ 前进行小素数试除。适合随机输入或一般情况。
返回
0 = 合数;1 = 素数(确定性判据);2 = 极可能是素数(强 BPSW 型非确定性判据)

在文件 is_prime_2.c 第 739 行定义.

739 {
740 lmmp_param_assert(hi > 0);
741 slong i;
742
743 if ((lo & 1) == 0) return 0;
744
745#define ainv0 ll_trial_primes[i][0]
746#define ainv1 ll_trial_primes[i][1]
747#define abound0 ll_trial_primes[i][2]
748#define abound1 ll_trial_primes[i][3]
749#define binv0 ll_trial_primes[i + 1][0]
750#define binv1 ll_trial_primes[i + 1][1]
751#define bbound0 ll_trial_primes[i + 1][2]
752#define bbound1 ll_trial_primes[i + 1][3]
753
754 if (hi < FAST_TRIAL_BOUND) {
755 for (i = 0; i < 32; i += 2) {
756 u128 a = _umul128to128_(hi, lo, ainv1, ainv0);
757 u128 b = _umul128to128_(hi, lo, binv1, binv0);
758 if ((_u128high(a) < abound1) | (_u128high(b) < bbound1)) return 0;
759 }
760 } else {
761 for (i = 0; i < 32; i += 2) {
762 u128 a = _umul128to128_(hi, lo, ainv1, ainv0);
763 u128 b = _umul128to128_(hi, lo, binv1, binv0);
764 if (ll_le(a, ((u128)abound1 << 64) | abound0) | ll_le(b, ((u128)bbound1 << 64) | bbound0))
765 return 0;
766 }
767 }
768#undef ainv0
769#undef ainv1
770#undef abound0
771#undef abound1
772#undef binv0
773#undef binv1
774#undef bbound0
775#undef bbound1
776
777 return is2_notrial_i_(lo, hi);
778}
#define bbound1
#define FAST_TRIAL_BOUND
#define binv1
static int is2_notrial_i_(mp_limb_t lo, mp_limb_t hi)
#define ainv0
#define abound1
static int ll_le(u128 a, u128 b)
#define binv0
#define ainv1
#define bbound0
#define abound0
#define lmmp_param_assert(x)
定义 lmmp.h:509

引用了 _umul128to128_(), abound0, abound1, ainv0, ainv1, bbound0, bbound1, binv0, binv1, FAST_TRIAL_BOUND, is2_notrial_i_(), ll_le(), lmmp_is_prime_2_(), lmmp_param_assert , 以及 lo.

被这些函数引用 bench_is_prime_2(), check_prime_2_agreement(), ipn_proth_i_(), lmmp_is_prime_2_(), lmmp_is_prothprime_(), lmmp_powmod_(), pool_2() , 以及 TEST_CASE().

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

◆ lmmp_is_prime_2_notrial_()

int lmmp_is_prime_2_notrial_ ( mp_limb_t lo,
mp_limb_t hi )

判断 128 位素数(无试除法)

参数
lo待判断数的低 64 位
hi待判断数的高 64 位
警告
hi>0, lo%2==1
注解
不进行试除法,对于含有明显小因子的输入不会早退。建议输入 不含小因子或强伪素数、半素数等。 B <= n < SWbound = 3317044064679887385961981(约 2^81.5)时为确定性判据(前 13 个素数基底的 Rabin-Miller, Sorenson-Webster),返回 1;更大时为 BPSW 型判据(基底 2 强伪素数 测试叠加强 Lucas-Selfridge 测试的 V 阶梯实现,Lucas 参数含 A* 脆弱区绕行((5|n)=-1 时 Q 取 1/5 的归一化形),另含 BFW vpsp 与 Q-Euler 两项强化检查,素数必然全过),学界无已知反例,返回 2。
返回
0 = 合数;1 = 素数(确定性判据);2 = 极可能是素数(强 BPSW 型非确定性判据)

在文件 is_prime_2.c 第 733 行定义.

733 {
734 lmmp_param_assert(hi > 0);
735 if ((lo & 1) == 0) return 0;
736 return is2_notrial_i_(lo, hi);
737}

引用了 is2_notrial_i_(), lmmp_is_prime_2_notrial_(), lmmp_param_assert , 以及 lo.

被这些函数引用 bench_is_prime_2_notrial(), check_prime_2_agreement(), lmmp_is_prime_2_notrial_() , 以及 lmmp_powmod_().

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

◆ mont2_dbl()

u128 mont2_dbl ( u128 a,
u128 n )
inlinestatic

在文件 is_prime_2.c 第 202 行定义.

202 {
203 u128 s = a + a;
204 if (s < a)
205 s -= n;
206 else if (s >= n)
207 s -= n;
208 return s;
209}

引用了 mont2_dbl(), n , 以及 s.

被这些函数引用 mont2_dbl(), mont2_lucas_strong_() , 以及 mont2_powmod_2_().

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

◆ mont2_lucas_strong_()

int mont2_lucas_strong_ ( u128 n,
u128 ninv,
u128 R2 )
static

在文件 is_prime_2.c 第 568 行定义.

568 {
569 u128 one, Qm, Qk, Qk1, Vk, Vk1, d, u, w, r;
570 slong s, i;
571 int j, Dneg;
572 uint Dabs, Qabs;
573
574 /* 寻找 D:非完全平方的 n 其 Jacobi 特征非平凡,序列中必存在
575 (D|n) = -1(全部为 +1 当且仅当 n 为完全平方),搜索必然终止,
576 不设上界;素数的最小 |D| 经验上 < 2*log2(n)^2 量级。完全平方数
577 是唯一不终止情形,经 17 处的延迟检测排除(平方检测走库内
578 sqrt_2_ 快速路径,放在少数次未命中之后,不进常见路径)——固定
579 小上界(如旧版 201)不可行:least |D| 随素数规模按 ~2^-k 几何
580 衰减,区间 [SWbound, 2^128) 内 least |D| > 201 的素数约 2^32 个,
581 上界会把它们误判为合数 */
582 Dabs = 5;
583 Dneg = 0;
584 for (;;) {
585 j = jacobi_D(Dabs, Dneg, n);
586 if (j == 0) return 0;
587 if (j == -1) break;
588 Dabs += 2;
589 Dneg ^= 1;
590 if (Dabs == 17 && is_square_2(n)) return 0;
591 }
592
593 /* Q = (1-D)/4,可为负;d*2^s = n+1(n 奇,n+1 偶) */
594 Qabs = Dneg ? (Dabs + 1) / 4 : (Dabs - 1) / 4;
595 d = factor_2adic(n + 1, &s);
596
597 one = mont2_to_mont1(1, R2, n, ninv);
598 if (Dabs == 5 && !Dneg) {
599 /* A* 脆弱区绕行(归一化形):首候选 D=5 命中 (5|n)=-1 时
600 Selfridge 参数 (P,Q)=(1,-1) 落 BFW 实证 Q≡±1 脆弱区(伪素数
601 过代表,且 Q-Euler 检查 Q^{(n+1)/2}=±Q 恒真空转),改用等价
602 参数化 (P',Q')=(1,1/5):V'_m = V_m/P^m 把 A* 的 (5,5) 等距
603 映射到 P=1 形(D' = 1-4Q' = 1/5,(D'|n) = (5|n) = -1 仍
604 合法),阶梯/stage2/末检全部公式零改动。q = 5^{-1} mod n
605 闭式:k*(n mod 5) = 4 (mod 5) 使 k*n+1 被 5 整除、真商 < n,
606 商经 mod 2^128 乘 5 的 2^128 幂逆恢复(2^64 ≡ 1 (mod 5)) */
607 static const uchar kt[5] = {0, 4, 2, 3, 1};
608 static const u128 inv5 =
609 (((u128)0xcccccccccccccccc) << 64) | 0xcccccccccccccccd; /* 5^{-1} mod 2^128 */
610 ulong r5 = (_u128low(n) % 5 + _u128high(n) % 5) % 5;
611 u128 q = (((u128)kt[r5]) * n + 1) * inv5;
612 Qm = mont2_to_mont2(q, R2, n, ninv);
613 } else {
614 Qm = mont2_to_mont1(Qabs, R2, n, ninv);
615 if (!Dneg) Qm = mont2_neg(Qm, n);
616 }
617
618 /* 阶梯初态 k=1:(V_1, V_2, Q^1, Q^2) = (1, 1-2Q, Q, Q^2) */
619 Vk = one;
620 Vk1 = mont2_sub(one, mont2_dbl(Qm, n), n);
621 Qk = Qm;
622 Qk1 = mont2_sqr(Qm, n, ninv);
623
624 for (i = bitlen_2(d) - 2; i >= 0; i--) {
625 if ((d >> i) & 1) {
626 u = mont2_mul_2(Vk, Vk1, n, ninv); /* V_{2k+1} 主项 */
627 w = mont2_sqr(Vk1, n, ninv); /* V_{2k+2} 主项 */
628 r = mont2_dbl(Qk1, n);
629 Vk = mont2_sub(u, Qk, n);
630 Vk1 = mont2_sub(w, r, n);
631 Qk = mont2_mul_2(Qk, Qk1, n, ninv); /* Q^{2k+1} */
632 Qk1 = mont2_sqr(Qk1, n, ninv); /* Q^{2k+2} */
633 } else {
634 u = mont2_sqr(Vk, n, ninv); /* V_{2k} 主项 */
635 w = mont2_mul_2(Vk, Vk1, n, ninv); /* V_{2k+1} 主项 */
636 r = mont2_dbl(Qk, n);
637 Vk = mont2_sub(u, r, n);
638 Vk1 = mont2_sub(w, Qk, n);
639 w = mont2_sqr(Qk, n, ninv); /* Q^{2k} */
640 Qk1 = mont2_mul_2(w, Qm, n, ninv); /* Q^{2k+1} */
641 Qk = w;
642 }
643 }
644
645 /* 判据:V_d = 0(r=0),或 U_d = 0,或 V_{d*2^r} = 0(0 < r < s)。
646 U_d = 0 经 D*U_d = 2V_{d+1} - V_d 检出(末态 Vk1 = V_{d+1})。
647 BFW 强化(Baillie-Fiori-Wagstaff 2021):命中不早退,链尾统一
648 追加 vpsp 与 Q-Euler 两检查——素数经 Frobenius(α^{n+1}=αβ=Q)
649 与 Euler 判据必然全过(vpsp@10^15 仅 5 个反例且与 spsp(2)/slpsp
650 全不相交,只拦假想的 BPSW 反例),正常完成路径零额外 REDC,
651 早退路径平均多 ~1-2 次链尾 sqr */
652 int hit = (Vk == 0) | (mont2_dbl(Vk1, n) == Vk);
653 u = mont2_sqr(Vk, n, ninv);
654 for (s--; s > 0; s--) {
655 r = mont2_dbl(Qk, n);
656 Vk = mont2_sub(u, r, n); /* V_{2d} = V_d^2 - 2Q^d(复用 u = V_d^2) */
657 Qk = mont2_sqr(Qk, n, ninv);
658 u = mont2_sqr(Vk, n, ninv);
659 if (Vk == 0) hit = 1;
660 }
661 if (!hit) return 0;
662 /* 末态 u = V_{(n+1)/2}^2,Qk = Q^{(n+1)/2}(s=1 时阶梯末态同型)。
663 vpsp:V_{n+1} = u - 2Qk ≡ 2Q;Q-Euler:Qk = Q*(Q|n) ∈ {Qm,-Qm} */
664 if (mont2_sub(u, mont2_dbl(Qk, n), n) != mont2_dbl(Qm, n)) return 0;
665 if (Qk != Qm && Qk != mont2_neg(Qm, n)) return 0;
666 return 1;
667}
static int jacobi_D(uint Dabs, int Dneg, u128 n)
static u128 mont2_dbl(u128 a, u128 n)
static int is_square_2(u128 n)
static u128 mont2_mul_2(u128 a, u128 b, u128 n, u128 ninv)
static u128 mont2_neg(u128 a, u128 n)
static u128 mont2_sub(u128 a, u128 b, u128 n)
static u128 mont2_sqr(u128 a, u128 n, u128 ninv)
#define r5
uint32_t uint
定义 numth.h:38

引用了 bitlen_2(), factor_2adic(), is_square_2(), jacobi_D(), mont2_dbl(), mont2_lucas_strong_(), mont2_mul_2(), mont2_neg(), mont2_sqr(), mont2_sub(), mont2_to_mont1(), mont2_to_mont2(), n, r5 , 以及 s.

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

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

◆ mont2_mul_2()

u128 mont2_mul_2 ( u128 a,
u128 b,
u128 n,
u128 ninv )
inlinestatic

在文件 is_prime_2.c 第 175 行定义.

175 {
176 u128 h, l;
177 mul_128(a, b, &h, &l);
178 return mont2_redc(h, l, n, ninv);
179}
static void mul_128(u128 a, u128 b, u128 *hi, u128 *lo)
static u128 mont2_redc(u128 thi, u128 tlo, u128 n, u128 ninv)

引用了 mont2_mul_2(), mont2_redc(), mul_128() , 以及 n.

被这些函数引用 lmmp_powmod_2_(), mont2_lucas_strong_(), mont2_mul_2(), mont2_mul_2() , 以及 mont2_to_mont2().

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

◆ mont2_neg()

u128 mont2_neg ( u128 a,
u128 n )
inlinestatic

在文件 is_prime_2.c 第 217 行定义.

217 {
218 return a == 0 ? a : n - a;
219}

引用了 mont2_neg() , 以及 n.

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

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

◆ mont2_powmod_2_()

u128 mont2_powmod_2_ ( u128 d,
int ebits,
u128 R2,
u128 n,
u128 ninv )
static

在文件 is_prime_2.c 第 294 行定义.

294 {
295 int k = ebits > 6 ? 6 : ebits;
296 int bit;
297 u128 v = mont2_to_mont1((ulong)1 << (ulong)(d >> (ebits - k)), R2, n, ninv);
298 for (bit = ebits - k - 1; bit >= 0; bit--) {
299 v = mont2_sqr(v, n, ninv);
300 if ((d >> bit) & 1) v = mont2_dbl(v, n);
301 }
302 return v;
303}

引用了 k, mont2_dbl(), mont2_powmod_2_(), mont2_sqr(), mont2_to_mont1() , 以及 n.

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

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

◆ mont2_preinv()

void mont2_preinv ( u128 * ninv,
u128 * R2,
u128 n )
static

在文件 is_prime_2.c 第 671 行定义.

671 {
672 ulong i2[2], q[4], nn[5] = {0, 0, 0, 0, 1};
673 ulong n2[2];
674
675 i2[0] = _u128low(n);
676 i2[1] = _u128high(n);
677 n2[0] = i2[0];
678 n2[1] = i2[1];
679 lmmp_binvert_2_(i2, i2);
680 i2[0] = -i2[0];
681 i2[1] = ~i2[1] + (i2[0] == 0);
682 lmmp_div_2_(q, nn, 5, n2);
683 *ninv = ((u128)i2[1] << 64) | i2[0];
684 *R2 = ((u128)n2[1] << 64) | n2[0];
685}
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元

引用了 lmmp_binvert_2_(), lmmp_div_2_(), mont2_preinv() , 以及 n.

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

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

◆ mont2_redc()

u128 mont2_redc ( u128 thi,
u128 tlo,
u128 n,
u128 ninv )
inlinestatic

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

124 {
125#if defined(LMMP_ASM_ARM64)
126 u128 q = tlo * ninv; /* u128 截断乘即 mod B^2 */
127 u128 qh, ql;
128 mul_128(q, n, &qh, &ql);
129 ulong t0 = _u128low(tlo), t1 = _u128high(tlo);
130 ulong p0 = _u128low(ql), p1 = _u128high(ql);
131 ulong k0 = (t0 + p0) < t0; /* lo 低 limb 进位(lo 值本身无消费者) */
132 ulong l1 = t1 + p1;
133 ulong k1 = l1 < t1;
134 l1 += k0;
135 k1 |= l1 < k0;
136 ulong h0 = _u128low(thi) + _u128low(qh);
137 ulong j0 = h0 < _u128low(qh);
138 h0 += k1;
139 j0 |= h0 < k1;
140 ulong h1 = _u128high(thi) + _u128high(qh);
141 ulong j1 = h1 < _u128high(qh);
142 h1 += j0;
143 j1 |= h1 < j0;
144 ulong n0 = _u128low(n), n1 = _u128high(n);
145 if (j1 || (h1 > n1) || (h1 == n1 && h0 >= n0)) {
146 ulong bw = h0 < n0; /* 借位跨 limb 传播 */
147 h0 -= n0;
148 h1 -= n1 + bw; /* j1 分支下回绕即真值 */
149 }
150 return ((u128)h1 << 64) | h0;
151#else
152 u128 q = tlo * ninv; /* u128 截断乘即 mod B^2 */
153 u128 qh, ql, lo, hi, c, c1, c2;
154 mul_128(q, n, &qh, &ql);
155 lo = tlo + ql;
156 c = lo < tlo;
157 hi = thi + qh;
158 c1 = hi < thi;
159 hi += c;
160 c2 = c && hi == 0;
161 if (c1 | c2)
162 hi -= n;
163 else if (hi >= n)
164 hi -= n;
165 return hi;
166#endif
167}
#define c1

引用了 c1, lo, mont2_redc(), mul_128() , 以及 n.

被这些函数引用 lmmp_powmod_2_(), mont2_mul_2(), mont2_mul_2(), mont2_redc(), mont2_redc(), mont2_redc_mul_1(), mont2_sqr() , 以及 mont2_sqr().

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

◆ mont2_redc_mul_1()

u128 mont2_redc_mul_1 ( u128 a,
ulong b,
u128 n,
u128 ninv )
inlinestatic

在文件 is_prime_2.c 第 183 行定义.

183 {
184 /* T = a*b < 2^192:h<<64 回绕丢弃的高位入 thi,低位和的进位并入 thi */
185 u128 lo = (u128)_u128low(a) * b;
186 u128 h = (u128)_u128high(a) * b;
187 u128 tlo = lo + (h << 64);
188 return mont2_redc((h >> 64) + (tlo < lo), tlo, n, ninv);
189}

引用了 lo, mont2_redc(), mont2_redc_mul_1() , 以及 n.

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

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

◆ mont2_sprp_stage2()

int mont2_sprp_stage2 ( u128 y,
slong t,
u128 one,
u128 m_1,
u128 n,
u128 ninv )
inlinestatic

在文件 is_prime_2.c 第 280 行定义.

280 {
281 if (y == one || y == m_1) return 1;
282 for (t--; t > 0; t--) {
283 y = mont2_sqr(y, n, ninv);
284 if (y == m_1) return 1;
285 }
286 return 0;
287}

引用了 mont2_sprp_stage2(), mont2_sqr(), n , 以及 t.

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

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

◆ mont2_sqr()

u128 mont2_sqr ( u128 a,
u128 n,
u128 ninv )
inlinestatic

在文件 is_prime_2.c 第 169 行定义.

169 {
170 u128 h, l;
171 sqr_128(a, &h, &l);
172 return mont2_redc(h, l, n, ninv);
173}
static void sqr_128(u128 a, u128 *hi, u128 *lo)

引用了 mont2_redc(), mont2_sqr(), n , 以及 sqr_128().

被这些函数引用 lmmp_powmod_2_(), mont2_lucas_strong_(), mont2_powmod_2_(), mont2_sprp_stage2(), mont2_sqr() , 以及 mont2_sqr().

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

◆ mont2_sub()

u128 mont2_sub ( u128 a,
u128 b,
u128 n )
inlinestatic

在文件 is_prime_2.c 第 211 行定义.

211 {
212 u128 r = a - b;
213 if (a < b) r += n;
214 return r;
215}

引用了 mont2_sub() , 以及 n.

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

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

◆ mont2_to_mont1()

u128 mont2_to_mont1 ( ulong x,
u128 R2,
u128 n,
u128 ninv )
inlinestatic

在文件 is_prime_2.c 第 192 行定义.

192 {
193 return mont2_redc_mul_1(R2, x, n, ninv);
194}
static u128 mont2_redc_mul_1(u128 a, ulong b, u128 n, u128 ninv)

引用了 mont2_redc_mul_1(), mont2_to_mont1() , 以及 n.

被这些函数引用 is2_notrial_i_(), mont2_lucas_strong_(), mont2_powmod_2_() , 以及 mont2_to_mont1().

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

◆ mont2_to_mont2()

u128 mont2_to_mont2 ( u128 a,
u128 R2,
u128 n,
u128 ninv )
inlinestatic

在文件 is_prime_2.c 第 196 行定义.

196 {
197 return mont2_mul_2(a, R2, n, ninv);
198}

引用了 mont2_mul_2(), mont2_to_mont2() , 以及 n.

被这些函数引用 is2_notrial_i_(), mont2_lucas_strong_() , 以及 mont2_to_mont2().

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

◆ mul_128()

void mul_128 ( u128 a,
u128 b,
u128 * hi,
u128 * lo )
inlinestatic

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

79 {
80#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
81 ulong a0 = _u128low(a), a1 = _u128high(a);
82 ulong b0 = _u128low(b), b1 = _u128high(b);
83 u128 p00 = (u128)a0 * b0;
84 u128 p01 = (u128)a0 * b1;
85 u128 p10 = (u128)a1 * b0;
86 u128 p11 = (u128)a1 * b1;
87 u128 mid = p01 + p10;
88 u128 cm = mid < p01; /* 129 位交叉和进位,属 hi 的第 64 位 */
89 u128 l = (mid << 64) + p00;
90 u128 cl = l < p00; /* 进位属 hi 的第 0 位 */
91 *lo = l;
92 *hi = p11 + (mid >> 64) + cl + (cm << 64);
93#else
94 ulong u[4];
95 _umul128to256_(_u128high(a), _u128low(a), _u128high(b), _u128low(b), u);
96 *lo = ((u128)u[1] << 64) | u[0];
97 *hi = ((u128)u[3] << 64) | u[2];
98#endif
99}
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
#define b0

引用了 _umul128to256_(), a0, a1, b0, b1, lo , 以及 mul_128().

被这些函数引用 mont2_mul_2(), mont2_mul_2(), mont2_redc(), mont2_redc(), mul_128() , 以及 mul_128().

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

◆ sqr_128()

void sqr_128 ( u128 a,
u128 * hi,
u128 * lo )
inlinestatic

在文件 is_prime_2.c 第 102 行定义.

102 {
103#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
104 ulong a0 = _u128low(a), a1 = _u128high(a);
105 u128 p0 = (u128)a0 * a0;
106 u128 m = (u128)a0 * a1; /* 交叉积,加倍后 129 位 */
107 u128 p1 = (u128)a1 * a1;
108 u128 ml = m << 1;
109 u128 mh = m >> 127; /* 加倍进位(0/1),属 hi 的第 64 位 */
110 u128 l = (ml << 64) + p0;
111 u128 cl = l < p0;
112 *lo = l;
113 *hi = p1 + (ml >> 64) + cl + (mh << 64);
114#else
115 ulong u[4];
116 _usqr128to256_(_u128high(a), _u128low(a), u);
117 *lo = ((u128)u[1] << 64) | u[0];
118 *hi = ((u128)u[3] << 64) | u[2];
119#endif
120}
static void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4])

引用了 _usqr128to256_(), a0, a1, lo , 以及 sqr_128().

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

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

变量说明

◆ ll_trial_primes

const ulong ll_trial_primes[32][4]
static

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_2.c 第 35 行定义.