LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_powmod.c 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "numth/powmod.h"
#include "cases.h"
#include "support/lmmp_test_utils.h"
#include <string.h>
test_powmod.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define restrict   __restrict
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static void make_odd_mod (mp_ptr m, mp_ptr b, mp_size_t n, u64 *seed)
static void mulmod_limbs (mp_ptr r, const mp_limb_t *a, const mp_limb_t *b, const mp_limb_t *m, mp_size_t n, mp_ptr t, mp_ptr q)
static u64 powmod_ref_u64 (u64 b, const u64 *ep, mp_size_t en, u64 m)
static mp_size_t sp_shape_limbs (mp_ptr dst, u64 k, int e, int form)
 TEST_CASE ("numth/powmod", mont_sp_redc_value)
 TEST_CASE ("numth/powmod", powlo_family)
 TEST_CASE ("numth/powmod", powmod_even_two_adic)
 TEST_CASE ("numth/powmod", powmod_exponent_and_product_laws)
 TEST_CASE ("numth/powmod", powmod_odd_and_dispatch)
 TEST_CASE ("numth/powmod", redc_value)
void test_powmod (void)
static int top_bits (u64 x)

宏定义说明

◆ restrict

#define restrict   __restrict

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

在文件 test_powmod.c 第 35 行定义.

被这些函数引用 __lmmp_mul_n_(), __lmmp_mullh_(), __lmmp_sqr_(), _odd_nPr_(), _odd_pow_(), fill_pattern(), ipn_lucas_i_(), ipn_mont_add_(), ipn_mont_dbl_(), ipn_mont_half_(), ipn_mont_mul_small_(), ipn_mont_neg_(), ipn_mont_sub_(), ipn_notrial_i_(), ipn_proth_i_(), ipn_sprp_1_(), ipn_sprp_base2_(), lmmp_10pow_1_(), lmmp_12pow_1_(), lmmp_14pow_1_(), lmmp_1pow_1_(), lmmp_2factorial_(), lmmp_2factorial_size_(), lmmp_2pow_1_(), lmmp_3pow_1_(), lmmp_4pow_1_(), lmmp_6pow_1_(), lmmp_8pow_1_(), lmmp_9pow_1_(), lmmp_arith_seqprod_(), lmmp_binvert_(), lmmp_binvert_3_(), lmmp_binvert_4_(), lmmp_binvert_n_dc_(), lmmp_binvert_unbalance_(), lmmp_binvert_unbalance_1_(), lmmp_binvert_unbalance_2_(), lmmp_bninv_(), lmmp_bninv_appr_newton_(), lmmp_cbrt_6_fast_(), lmmp_cbrt_divide_(), lmmp_cube_3_(), lmmp_cube_3_(), lmmp_cube_6_(), lmmp_cube_6_(), lmmp_div_(), lmmp_div_1_s_(), lmmp_div_2_s_(), lmmp_div_3_2_(), lmmp_div_basecase_(), lmmp_div_divide_(), lmmp_div_divide_n_(), lmmp_div_mulinv_(), lmmp_div_s_(), lmmp_divexact_(), lmmp_divexact_2_(), lmmp_divexact_basecase_(), lmmp_divexact_divide_(), lmmp_divexact_mu_run_(), lmmp_divexact_unbalance_(), lmmp_elem_mul_ulong_(), lmmp_extract_bits_(), lmmp_factorial_(), lmmp_factorial_size_(), lmmp_factors_mul_(), lmmp_factors_mul_ushort_(), lmmp_from_str_divide_(), lmmp_gcd_lehmer_extract_(), lmmp_huff_tree_build_(), lmmp_huff_tree_mul_(), lmmp_hyperfac_(), lmmp_hyperfac_size_(), lmmp_inv_(), lmmp_inv_basecase_(), lmmp_inv_prediv_(), lmmp_invappr_(), lmmp_invappr_newton_(), lmmp_invcbrt_newton_(), lmmp_invsqrt_newton_(), lmmp_is_strong_lucas_(), lmmp_mont_fold_hi_(), lmmp_mont_init_(), lmmp_mont_redc_(), lmmp_mont_redc_bc_(), lmmp_mont_redcify_(), lmmp_mont_sp_redc_(), lmmp_mul_(), lmmp_mul_basecase_(), lmmp_mul_fft_unbalance_(), lmmp_mul_n_(), lmmp_mul_toom22_(), lmmp_mul_toom32_(), lmmp_mul_toom33_(), lmmp_mul_toom42_(), lmmp_mul_toom42_cache_(), lmmp_mul_toom42_cache_init_(), lmmp_mul_toom42_unbalance_(), lmmp_mul_toom43_(), lmmp_mul_toom44_(), lmmp_mul_toom52_(), lmmp_mul_toom53_(), lmmp_mul_toom62_(), lmmp_mul_toom62_cache_(), lmmp_mul_toom62_cache_init_(), lmmp_mul_toom62_unbalance_(), lmmp_mul_toom6h_(), lmmp_mul_toom8h_(), lmmp_mullh_(), lmmp_mullo_(), lmmp_mullo_basecase_(), lmmp_mullo_dc_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_mullo_n_(), lmmp_mulmod_ulong_(), lmmp_multinomial_(), lmmp_multinomial_size_(), lmmp_nCr_(), lmmp_nCr_size_(), lmmp_nPr_(), lmmp_nPr_size_(), lmmp_odd_2factorial_uint_(), lmmp_odd_2factorial_ushort_(), lmmp_odd_factorial_(), lmmp_odd_factorial_uint_(), lmmp_odd_multinomial_uint_(), lmmp_odd_multinomial_ushort_(), lmmp_odd_nCr_div_(), lmmp_odd_nCr_uint_(), lmmp_odd_nCr_ushort_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_uint_(), lmmp_odd_nPr_ulong_(), lmmp_odd_nPr_ushort_(), lmmp_perfsqr_(), lmmp_pow_(), lmmp_pow_1_(), lmmp_pow_basecase_(), lmmp_pow_win2_(), lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_powmod_(), lmmp_powmod_1_(), lmmp_powmod_2_(), lmmp_powmod_odd_(), lmmp_powmod_odd_mont_(), lmmp_prime_int_table_init_(), lmmp_primefac_(), lmmp_random_(), lmmp_redc_(), lmmp_remove_(), lmmp_seed_random_(), lmmp_shlnot_(), lmmp_sqr_(), lmmp_sqr_basecase_(), lmmp_sqr_toom2_(), lmmp_sqr_toom3_(), lmmp_sqr_toom4_(), lmmp_sqr_toom6_(), lmmp_sqr_toom8_(), lmmp_sqrlo_basecase_(), lmmp_sqrlo_dc_(), lmmp_sqrlo_n_(), lmmp_sqrt_(), lmmp_sqrt_divide_(), lmmp_sqrt_newton_(), lmmp_strong_random_(), lmmp_superfac_(), lmmp_superfac_size_(), lmmp_to_str_divide_(), lmmp_trialdiv_(), lmmp_u16_pow_1_(), lmmp_u32_pow_1_(), lmmp_u4_pow_1_(), lmmp_u64_pow_1_(), lmmp_u8_pow_1_(), pcg64_le_action(), pcg64_le_seq_next() , 以及 pow_nPr_().

函数说明

◆ make_odd_mod()

void make_odd_mod ( mp_ptr m,
mp_ptr b,
mp_size_t n,
u64 * seed )
static

在文件 test_powmod.c 第 65 行定义.

65 {
66 random_limbs(m, n, seed);
67 m[0] |= 1;
68 mp_ptr raw = alloc_limbs(n), q = alloc_limbs(n);
69 random_limbs(raw, n, seed);
70 raw[n - 1] >>= 1; // raw < 2^(64n-1),一步归约后必 < m
71 if (raw[n - 1] == 0) raw[n - 1] = 1;
72 lmmp_div_(q, b, raw, n, m, n);
73 lmmp_free(raw);
74 lmmp_free(q);
75}
mp_limb_t * mp_ptr
定义 lmmp.h:96
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
#define n

引用了 lmmp_div_(), lmmp_free(), make_odd_mod() , 以及 n.

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

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

◆ mulmod_limbs()

void mulmod_limbs ( mp_ptr r,
const mp_limb_t * a,
const mp_limb_t * b,
const mp_limb_t * m,
mp_size_t n,
mp_ptr t,
mp_ptr q )
static

在文件 test_powmod.c 第 78 行定义.

79 {
80 lmmp_mul_(t, a, n, b, n);
81 lmmp_div_(q, r, t, 2 * n, m, n);
82}
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
#define t

引用了 lmmp_div_(), lmmp_mul_(), mulmod_limbs(), n , 以及 t.

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

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

◆ powmod_ref_u64()

u64 powmod_ref_u64 ( u64 b,
const u64 * ep,
mp_size_t en,
u64 m )
static

在文件 test_powmod.c 第 44 行定义.

44 {
45 u64 r = 1 % m;
46 b %= m;
47 mp_limb_t t[2];
48 for (mp_size_t i = en; i-- > 0;) {
49 for (int bit = 63; bit >= 0; --bit) {
50 lmmp_mullh_(r, r, t);
51 r = lmmp_mod_1_(t, 2, m);
52 if ((ep[i] >> bit) & 1) {
53 lmmp_mullh_(r, b, t);
54 r = lmmp_mod_1_(t, 2, m);
55 }
56 }
57 }
58 return r;
59}
#define lmmp_mullh_
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
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_, powmod_ref_u64() , 以及 t.

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

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

◆ sp_shape_limbs()

mp_size_t sp_shape_limbs ( mp_ptr dst,
u64 k,
int e,
int form )
static

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

85 {
86 size_t cap = (size_t)e / 64 + 3;
87 lmmp_zero(dst, cap);
88 int s = e % 64;
89 dst[e / 64] = s ? (k << s) : k;
90 if (s) dst[e / 64 + 1] = k >> (64 - s);
91 if (form > 0) dst[0] += 1;
92 else lmmp_dec(dst);
93 return norm_len(dst, (mp_size_t)cap);
94}
#define k
#define lmmp_zero(dst, n)
定义 lmmp.h:476
#define lmmp_dec(p)
减1宏(预期无借位)
#define s

引用了 k, lmmp_dec, lmmp_zero, s , 以及 sp_shape_limbs().

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

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

◆ TEST_CASE() [1/6]

TEST_CASE ( "numth/powmod" ,
mont_sp_redc_value  )

在文件 test_powmod.c 第 470 行定义.

470 {
471 u64 seed = 0x5ec0fefe1e55aa21ull;
472 struct modulus_case { u64 k; int e; int form; } shapes[] = {
473 {1, 64, 1}, {3, 64, 1}, {3, 65, 1}, {0xffffffffull, 127, 1},
474 {0xdeadbeefcafebull, 127, 1}, {0x123456789abcull, 129, 1},
475 {3, 300, 1}, {1, 1024, 1}, {3, 19969, 1},
476 {1, 127, -1}, {3, 64, -1}, {0xdeadbeefcafebull, 127, -1},
477 {0x123456789abcull, 191, -1}, {3, 300, -1}, {1, 19937, -1},
478 };
479 for (size_t sh_index = 0; sh_index < ARRAY_SIZE(shapes); ++sh_index) {
480 const struct modulus_case sh = shapes[sh_index];
481 size_t cap = (size_t)sh.e / 64 + 3;
482 mp_ptr m = alloc_limbs(cap), r = alloc_limbs(cap), t = alloc_limbs(2 * cap);
483 mp_size_t n = sp_shape_limbs(m, sh.k, sh.e, sh.form);
484
486 int form = lmmp_mont_sp_init_(&mc, m, n);
487 TEST_CHECK_MSG(form == sh.form, "sp probe form");
488
489 int samples = n > 100 ? 2 : 4;
490 for (int it = 0; it < samples; ++it) {
491 random_limbs(t, 2 * (size_t)n, &seed);
492 /* 顶半压制到 < m:顶 limb 掩码到 m 位长内,仍越则整体减 m */
493 u64 tb = (u64)top_bits(m[n - 1]);
494 t[2 * (size_t)n - 1] &= (tb == 64) ? ~(u64)0 : (((u64)1 << tb) - 1);
495 if (lmmp_cmp_(t + n, m, n) >= 0) (void)lmmp_sub_n_(t + n, t + n, m, n);
496
497 lmmp_mont_sp_redc_(r, t, &mc);
498 TEST_CHECK_MSG(lmmp_cmp_(r, m, n) < 0, "sp redc < m");
499 // r*B^n ≡ t (mod m):经库除法双侧取余精确比对(t < m*B^n 已构造)
500 {
501 mp_ptr P = alloc_limbs(2 * n), q = alloc_limbs(n + 2), rm = alloc_limbs(n),
502 rt = alloc_limbs(n);
503 lmmp_zero(P, 2 * n);
504 memcpy(P + n, r, (size_t)n * 8); // P = r*B^n
505 lmmp_div_(q, rm, P, 2 * n, m, n);
506 lmmp_div_(q, rt, t, 2 * n, m, n);
507 TEST_CHECK_MSG(mpn_eq(rm, n, rt, n), "sp redc congruence");
508 lmmp_free(P); lmmp_free(q); lmmp_free(rm); lmmp_free(rt);
509 }
510 }
512 }
513
514 /* 探测否定侧 */
516 {
517 mp_ptr m = alloc_limbs(4);
518 mp_size_t n = sp_shape_limbs(m, 3, 100, 1);
519 m[0] += 2; /* 稠密:m[0] = 3,中间零带被 +2 破坏以外形也不再 ±1 */
520 TEST_CHECK_MSG(lmmp_mont_sp_init_(&mc, m, n) == 0, "sp probe dense");
521 lmmp_free(m);
522 }
523 {
524 mp_ptr m = alloc_limbs(2); /* B^2−1 全 B−1(= B^n−1 整密,无簇) */
525 m[0] = ~(u64)0;
526 m[1] = ~(u64)0;
527 TEST_CHECK_MSG(lmmp_mont_sp_init_(&mc, m, 2) == 0, "sp probe all-ones");
528 lmmp_free(m);
529 }
530 {
531 mp_ptr m = alloc_limbs(5); /* 3 limb 簇:m = 1 + K·B^2,K 三 limb */
532 lmmp_zero(m, 5);
533 m[0] = 1;
534 m[2] = 0x13579bdf2468ace0ull;
535 m[3] = ~(u64)0;
536 m[4] = 1;
537 TEST_CHECK_MSG(lmmp_mont_sp_init_(&mc, m, 5) == 0, "sp probe 3-limb cluster");
538 lmmp_free(m);
539 }
540}
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
static int top_bits(u64 x)
static mp_size_t sp_shape_limbs(mp_ptr dst, u64 k, int e, int form)

引用了 ARRAY_SIZE, k, lmmp_cmp_(), lmmp_div_(), lmmp_free(), lmmp_sub_n_(), lmmp_zero, n, sp_shape_limbs(), t, TEST_CASE, TEST_CHECK_MSG , 以及 top_bits().

函数调用图:

◆ TEST_CASE() [2/6]

TEST_CASE ( "numth/powmod" ,
powlo_family  )

在文件 test_powmod.c 第 304 行定义.

304 {
305 u64 seed = 0x1b873593f00dbeebull;
306 // powlo vs powmod_(B^n):b^e mod B^n 的两条独立算法(截断梯子 vs 偶模数 CRT)
307 const mp_size_t n_values[] = {1, 2, 3, 5, 17};
308 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
309 mp_size_t n = n_values[n_index];
310 for (int iter = 0; iter < 3; ++iter) {
311 mp_ptr b = alloc_limbs(n), ep = alloc_limbs(3), dst = alloc_limbs(n),
312 dst2 = alloc_limbs(n + 1), bn = alloc_limbs(n + 1), bp = alloc_limbs(n + 1);
313 random_limbs(b, n, &seed);
314 lmmp_zero(bn, n + 1);
315 bn[n] = 1; // 模数 B^n(n+1 limb,顶 limb=1)
316 for (mp_size_t i = 0; i < 3; ++i) ep[i] = xorshift64(&seed);
317 ep[2] |= (u64)1 << 63;
318 lmmp_zero(bp, n + 1);
319 memcpy(bp, b, (size_t)n * 8); // b < B^n
320 ulong es[5] = {1, 2, 5, 0xdeadbeef, ep[0]}; // 同上:mp_limb_t 与 ull 异型
321 for (size_t e_index = 0; e_index < ARRAY_SIZE(es); ++e_index) {
322 ulong e = es[e_index];
323 mp_limb_t e1[1] = {e};
324 lmmp_powlo_(dst, b, n, e1, 1);
325 lmmp_powmod_(dst2, bp, e1, 1, bn, n + 1);
326 TEST_CHECK_MSG(memcmp(dst, dst2, (size_t)n * 8) == 0, "powlo == powmod(B^n)");
327 }
328 lmmp_powlo_(dst, b, n, ep, 3);
329 lmmp_powmod_(dst2, bp, ep, 3, bn, n + 1);
330 TEST_CHECK_MSG(memcmp(dst, dst2, (size_t)n * 8) == 0, "powlo 3-limb exp == powmod");
331 // 特化与分派一致
332 if (n == 1) {
333 mp_ptr d1 = alloc_limbs(1);
334 lmmp_powlo_1_(d1, b, ep, 3);
335 TEST_CHECK_MSG(d1[0] == dst[0], "powlo_1_ == powlo_");
336 lmmp_free(d1);
337 }
338 if (n == 2) {
339 mp_ptr d2 = alloc_limbs(2);
340 lmmp_powlo_2_(d2, b, ep, 3);
341 TEST_CHECK_MSG(memcmp(d2, dst, 16) == 0, "powlo_2_ == powlo_");
342 lmmp_free(d2);
343 }
344 // 截断恒等式:powlo(b,e1+e2) == low_n(powlo(b,e1)*powlo(b,e2))
345 u64 e1 = ep[0] >> 1, e2 = ep[0] - e1;
346 mp_limb_t ea[1] = {e1}, eb[1] = {e2};
347 mp_ptr p1 = alloc_limbs(n), p2 = alloc_limbs(n), prod = alloc_limbs(2 * n), dm = alloc_limbs(n);
348 lmmp_powlo_(p1, b, n, ea, 1);
349 lmmp_powlo_(p2, b, n, eb, 1);
350 lmmp_powlo_(dm, b, n, ep, 1);
351 lmmp_mul_(prod, p1, n, p2, n);
352 TEST_CHECK_MSG(memcmp(dm, prod, (size_t)n * 8) == 0, "powlo truncation law");
353 // e=1 快路径 == b
354 mp_limb_t e1limb[1] = {1};
355 lmmp_powlo_(dm, b, n, e1limb, 1);
356 TEST_CHECK_MSG(memcmp(dm, b, (size_t)n * 8) == 0, "powlo e=1 == b");
358 lmmp_free(b); lmmp_free(ep); lmmp_free(dst); lmmp_free(dst2); lmmp_free(bn);
359 lmmp_free(bp);
360 }
361 }
362}
#define prod
#define bn
void lmmp_powlo_(mp_ptr dst, mp_srcptr bp, mp_size_t n, mp_srcptr ep, mp_size_t en)
计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
void lmmp_powlo_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
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]
uint64_t ulong
定义 numth.h:39
void lmmp_powlo_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)

引用了 ARRAY_SIZE, bn, lmmp_free(), lmmp_mul_(), lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_powmod_(), lmmp_zero, n, prod, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [3/6]

TEST_CASE ( "numth/powmod" ,
powmod_even_two_adic  )

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

364 {
365 // 偶模数 m = odd << k:(-1)^e / e=1 / b=0 角点 + 指数律 + 奇分派一致 + CRT 重建
366 u64 seed = 0x243f6a8885a308d3ull;
367 const size_t cap = 12;
368 size_t ks[] = {1, 2, 63, 64, 65, 128, 129, 384, 511, 512};
369 for (size_t k_index = 0; k_index < ARRAY_SIZE(ks); ++k_index) {
370 size_t k = ks[k_index];
371 u64 odds[3] = {1, 3, xorshift64(&seed) | 1};
372 for (size_t odd_index = 0; odd_index < ARRAY_SIZE(odds); ++odd_index) {
373 u64 odd = odds[odd_index];
374 // m = odd << k:跨 limb 由 limb 定位承载,limb 内由 shl 位移承载
375 mp_size_t nb = k / 64 + 2;
376 if (nb > cap) continue;
377 mp_ptr m = alloc_limbs(cap), b = alloc_limbs(cap), dst = alloc_limbs(cap);
378 lmmp_zero(m, cap);
379 int kb = (int)(k % 64);
380 m[k / 64] = kb ? (odd << kb) : odd;
381 if (kb) m[k / 64 + 1] = odd >> (64 - kb);
382 mp_size_t n = norm_len(m, cap);
383 // 归约基 b < m:随机后除
384 u64 s5 = seed ^ (u64)k * 0x9e3779b97f4a7c15ull ^ odd;
385 random_limbs(b, n, &s5);
386 b[n - 1] >>= 1;
387 if (b[n - 1] == 0) b[n - 1] = 1;
388 mp_ptr q = alloc_limbs(cap);
389 lmmp_div_(q, b, b, n, m, n);
390 lmmp_free(q);
391 // b=0 → 0;e=1 → b;b=m-1:奇 e → m-1、偶 e → 1
392 mp_ptr z = alloc_limbs(cap);
393 lmmp_zero(z, n);
394 mp_limb_t e2[1] = {2}, eodd[1] = {0x51ed270b9a3c8f11ull}, e1[1] = {1};
395 lmmp_powmod_(dst, z, eodd, 1, m, n);
396 bool zk = norm_len(dst, n) == 0;
397 TEST_CHECK_MSG(zk, "even-mod b=0");
398 lmmp_powmod_(dst, b, e1, 1, m, n);
399 TEST_CHECK_MSG(memcmp(dst, b, (size_t)n * 8) == 0, "even-mod e=1 == b");
400 mp_ptr mm1 = alloc_limbs(cap);
401 lmmp_copy(mm1, m, n);
402 sub_small_inplace(mm1, n, 1);
403 lmmp_powmod_(dst, mm1, eodd, 1, m, n);
404 TEST_CHECK_MSG(memcmp(dst, mm1, (size_t)n * 8) == 0, "(-1)^odd == m-1");
405 lmmp_powmod_(dst, mm1, e2, 1, m, n);
406 TEST_CHECK_MSG(dst[0] == 1 && norm_len(dst, n) == 1, "(-1)^2 == 1");
407 // 指数律(b^e1 * b^e2 == b^(e1+e2))
408 {
409 u64 ea = eodd[0] >> 3, eb = eodd[0] - ea;
410 mp_limb_t epa[1] = {ea}, epb[1] = {eb}, eps[1] = {eodd[0]};
411 mp_ptr r1 = alloc_limbs(cap), r2 = alloc_limbs(cap), t = alloc_limbs(2 * cap),
412 qq = alloc_limbs(2 * cap);
413 lmmp_powmod_(r1, b, epa, 1, m, n);
414 lmmp_powmod_(r2, b, epb, 1, m, n);
415 lmmp_powmod_(dst, b, eps, 1, m, n);
416 lmmp_mul_(t, r1, n, r2, n);
417 lmmp_div_(qq, r1, t, 2 * n, m, n);
418 TEST_CHECK_MSG(memcmp(dst, r1, (size_t)n * 8) == 0, "even-mod exponent law");
420 }
421 // CRT 同余组验证:dst mod 2^k == b^e mod 2^k 且 dst mod odd == b^e mod odd
422 // (odd==1 时退化为纯 2^k 模数,跳过)
423 if (odd > 1) {
424 mp_limb_t odb[1] = {odd};
425 // r2 = b^e mod odd
426 mp_ptr bmod = alloc_limbs(cap), r2 = alloc_limbs(cap);
427 lmmp_div_(NULL, bmod, b, n, odb, 1);
428 lmmp_powmod_(r2, bmod, eodd, 1, odb, 1);
429 lmmp_powmod_(dst, b, eodd, 1, m, n);
430 mp_ptr p2k = alloc_limbs(cap), b2 = alloc_limbs(cap), r1 = alloc_limbs(cap),
431 d2 = alloc_limbs(cap);
432 lmmp_zero(p2k, cap);
433 p2k[k / 64] |= (u64)1 << (k % 64);
434 mp_size_t np = norm_len(p2k, cap);
435 lmmp_div_(NULL, b2, b, n, p2k, np);
436 lmmp_powmod_(r1, b2, eodd, 1, p2k, np);
437 lmmp_div_(NULL, d2, dst, n, p2k, np);
438 TEST_CHECK_MSG(mpn_eq(d2, np, r1, np), "CRT: result mod 2^k");
439 lmmp_div_(NULL, d2, dst, n, odb, 1);
440 TEST_CHECK_MSG(d2[0] == r2[0], "CRT: result mod odd");
442 lmmp_free(bmod); lmmp_free(r2);
443 }
444 lmmp_free(m); lmmp_free(b); lmmp_free(dst); lmmp_free(z); lmmp_free(mm1);
445 }
446 }
447 // 奇模数经 powmod_ 分派与 powmod_odd_ 同值
448 {
449 u64 s2 = 0xa4093822299f31d0ull;
450 const mp_size_t n_values[] = {1, 5, 17};
451 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
452 mp_size_t n = n_values[n_index];
453 mp_ptr m = alloc_limbs(n), b = alloc_limbs(n), d1 = alloc_limbs(n), d2 = alloc_limbs(n);
454 make_odd_mod(m, b, n, &s2);
455 mp_limb_t ep[1] = {0x9e3779b9ull};
456 lmmp_powmod_(d1, b, ep, 1, m, n);
457 lmmp_powmod_odd_(d2, b, ep, 1, m, n);
458 TEST_CHECK_MSG(memcmp(d1, d2, (size_t)n * 8) == 0, "odd dispatch match");
459 lmmp_free(m); lmmp_free(b); lmmp_free(d1); lmmp_free(d2);
460 }
461 }
462}
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define r2
#define r1
#define b2
void lmmp_powmod_odd_(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 void make_odd_mod(mp_ptr m, mp_ptr b, mp_size_t n, u64 *seed)

引用了 ARRAY_SIZE, b2, k, lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_mul_(), lmmp_powmod_(), lmmp_powmod_odd_(), lmmp_zero, make_odd_mod(), n, r1, r2, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [4/6]

TEST_CASE ( "numth/powmod" ,
powmod_exponent_and_product_laws  )

在文件 test_powmod.c 第 267 行定义.

267 {
268 // 指数律 b^(e1+e2) == b^e1 * b^e2 (mod m) 与乘法性 (a*c)^e == a^e * c^e (mod m)
269 u64 seed = 0x13198a2e03707344ull;
270 const mp_size_t n_values[] = {1, 2, 3, 5, 17, 33, 70};
271 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
272 mp_size_t n = n_values[n_index];
273 for (int iter = 0; iter < 4; ++iter) {
274 mp_ptr m = alloc_limbs(n), b = alloc_limbs(n), c = alloc_limbs(n);
275 make_odd_mod(m, b, n, &seed);
276 make_odd_mod(m, c, n, &seed);
277 mp_ptr t = alloc_limbs(2 * n + 2), q = alloc_limbs(2 * n + 2), r1 = alloc_limbs(n),
278 r2 = alloc_limbs(n), r12 = alloc_limbs(n), dst = alloc_limbs(n);
279 // 指数律:e1+e2(64 位内),积经库乘 + 库除归约
280 u64 e1 = xorshift64(&seed) >> (1 + iter % 32), e2 = xorshift64(&seed) >> (1 + iter % 16);
281 mp_limb_t ep1[1] = {e1}, ep2[1] = {e2}, ep12[1] = {e1 + e2};
282 lmmp_powmod_odd_(r1, b, ep1, 1, m, n);
283 lmmp_powmod_odd_(r2, b, ep2, 1, m, n);
284 lmmp_powmod_odd_(dst, b, ep12, 1, m, n);
285 mulmod_limbs(r12, r1, r2, m, n, t, q);
286 TEST_CHECK_MSG(memcmp(dst, r12, (size_t)n * 8) == 0, "b^(e1+e2) == b^e1*b^e2");
287 // 乘法性:(b*c mod m)^e == b^e * c^e (mod m)
288 u64 e = 0x9e3779b97f4a7c15ull;
289 mp_limb_t ep[1] = {e};
290 mp_ptr bc = alloc_limbs(n);
291 mulmod_limbs(bc, b, c, m, n, t, q);
292 lmmp_powmod_odd_(r1, bc, ep, 1, m, n);
293 lmmp_powmod_odd_(r2, b, ep, 1, m, n);
294 lmmp_powmod_odd_(dst, c, ep, 1, m, n);
295 mulmod_limbs(r12, r2, dst, m, n, t, q);
296 TEST_CHECK_MSG(memcmp(r1, r12, (size_t)n * 8) == 0, "(bc)^e == b^e*c^e");
297 lmmp_free(m); lmmp_free(b); lmmp_free(c); lmmp_free(bc);
299 lmmp_free(dst);
300 }
301 }
302}
static void mulmod_limbs(mp_ptr r, const mp_limb_t *a, const mp_limb_t *b, const mp_limb_t *m, mp_size_t n, mp_ptr t, mp_ptr q)

引用了 ARRAY_SIZE, lmmp_free(), lmmp_powmod_odd_(), make_odd_mod(), mulmod_limbs(), n, r1, r2, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [5/6]

TEST_CASE ( "numth/powmod" ,
powmod_odd_and_dispatch  )

在文件 test_powmod.c 第 148 行定义.

148 {
149 u64 seed = 0x1234567890abcdefull;
150 const mp_size_t n_values[] = {1, 2, 3, 4, 7, 12, 33, 70};
151 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
152 mp_size_t n = n_values[n_index];
153 for (int iter = 0; iter < 3; ++iter) {
154 mp_ptr m = alloc_limbs(n), b = alloc_limbs(n);
155 make_odd_mod(m, b, n, &seed);
156 mp_ptr dst = alloc_limbs(n), dst2 = alloc_limbs(n), dst3 = alloc_limbs(n);
157 // 指数集:短/边界/单双三 limb
158 struct exponent_case { mp_size_t en; u64 w[3]; } exps[] = {
159 {1, {1, 0, 0}}, {1, {2, 0, 0}}, {1, {3, 0, 0}},
160 {1, {17, 0, 0}}, {1, {64, 0, 0}}, {1, {0xdeadbeefull, 0, 0}},
161 {1, {0xffffffffffffffffull, 0, 0}},
162 {2, {0x9e3779b97f4a7c15ull, 0x1234, 0}},
163 {3, {0, 0, 1}}, // e=B^2:偶底数短路形态
164 };
165 for (size_t ex_index = 0; ex_index < ARRAY_SIZE(exps); ++ex_index) {
166 const struct exponent_case ex = exps[ex_index];
167 mp_ptr ep = alloc_limbs(ex.en);
168 memcpy(ep, ex.w, (size_t)ex.en * 8);
169 lmmp_powmod_odd_(dst, b, ep, ex.en, m, n);
170 TEST_CHECK_MSG(mpn_cmp(dst, n, m, n) < 0, "powmod_odd in range");
171 // n==1:u64 简单参考(mullh+mod_1,指数全 limb)
172 if (n == 1) {
173 u64 want = powmod_ref_u64(b[0], ep, ex.en, m[0]);
174 TEST_CHECK_MSG(dst[0] == want, "powmod_odd vs u64 reference");
175 }
176 // 入口一致:powmod_ 分派(奇模数走 odd 路径)
177 lmmp_powmod_(dst2, b, ep, ex.en, m, n);
178 TEST_CHECK_MSG(memcmp(dst, dst2, (size_t)n * 8) == 0, "powmod_ dispatch == odd");
179 // n==1/2 特化入口一致
180 if (n == 1) {
181 lmmp_powmod_1_(dst3, b, ep, ex.en, m[0]);
182 TEST_CHECK_MSG(dst[0] == dst3[0], "powmod_1_ == odd");
183 }
184 if (n == 2) {
185 lmmp_powmod_2_(dst3, b, ep, ex.en, m);
186 TEST_CHECK_MSG(memcmp(dst, dst3, 16) == 0, "powmod_2_ == odd");
187 }
188 lmmp_free(ep);
189 }
190 lmmp_free(m); lmmp_free(b); lmmp_free(dst); lmmp_free(dst2); lmmp_free(dst3);
191 }
192 }
193
194 // 费马小定理:素模 p ∈ MOD_P,b^(p-1) == 1;b^p == b(固定 b)
195 for (int i = 0; i < MOD_P_CNT; ++i) {
196 u32 p = MOD_P[i];
197 u64 bbs[4] = {2, 3, 12345, (u64)p - 1}; // 显式数组:Linux 下 u64 与 ull 字面量异型
198 for (size_t bb_index = 0; bb_index < ARRAY_SIZE(bbs); ++bb_index) {
199 u64 bb = bbs[bb_index];
200 u64 b = bb % p;
201 if (b == 0) continue;
202 mp_limb_t mp[1] = {p}, bp[1] = {b}, ep[1] = {p - 1}, dst[1];
203 lmmp_powmod_odd_(dst, bp, ep, 1, mp, 1);
204 TEST_CHECK_MSG(dst[0] == 1, "fermat b^(p-1) == 1");
205 ep[0] = p;
206 lmmp_powmod_odd_(dst, bp, ep, 1, mp, 1);
207 TEST_CHECK_MSG(dst[0] == b, "fermat b^p == b");
208 }
209 }
210
211 // 角点:m = B^n-1(全 1 折叠拼接二义点)、b=0、b=m-1、e=1
212 const mp_size_t n_values2[] = {2, 5, 17};
213 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values2); ++n_index) {
214 mp_size_t n = n_values2[n_index];
215 mp_ptr m = alloc_limbs(n), b = alloc_limbs(n), dst = alloc_limbs(n), ep = alloc_limbs(2);
216 for (mp_size_t i = 0; i < n; ++i) m[i] = ~(u64)0;
217 ep[0] = 0x24f1a7e3c5590b8dull;
218 ep[1] = 1;
219 lmmp_zero(b, n);
220 lmmp_powmod_odd_(dst, b, ep, 2, m, n);
221 bool zero_ok = true;
222 for (mp_size_t i = 0; i < n; ++i) zero_ok = zero_ok && dst[i] == 0;
223 TEST_CHECK_MSG(zero_ok, "powmod b=0");
224 // b = m-1:(-1)^e,e 奇(ep 顶 limb=1 ⟹ 奇)→ m-1;e=2 → 1
225 for (mp_size_t i = 0; i < n; ++i) b[i] = ~(u64)0;
226 b[0] -= 1;
227 lmmp_powmod_odd_(dst, b, ep, 2, m, n);
228 bool m1_ok = true;
229 for (mp_size_t i = 0; i < n; ++i) m1_ok = m1_ok && dst[i] == b[i];
230 TEST_CHECK_MSG(m1_ok, "powmod (-1)^odd == m-1");
231 ep[0] = 2;
232 lmmp_powmod_odd_(dst, b, ep, 1, m, n);
233 bool one_ok = dst[0] == 1;
234 for (mp_size_t i = 1; i < n; ++i) one_ok = one_ok && dst[i] == 0;
235 TEST_CHECK_MSG(one_ok, "powmod (-1)^2 == 1");
236 // e=1 拷贝快路径
237 u64 s3 = seed ^ (u64)n;
238 random_limbs(b, n, &s3);
239 lmmp_div_(NULL, b, b, n, m, n); // b mod m(原地余数)
240 ep[0] = 1;
241 lmmp_powmod_odd_(dst, b, ep, 1, m, n);
242 TEST_CHECK_MSG(memcmp(dst, b, (size_t)n * 8) == 0, "powmod e=1 == b");
243 lmmp_free(m); lmmp_free(b); lmmp_free(dst); lmmp_free(ep);
244 }
245
246 // 梅森折叠主路径(n >= REDC_MERSENNE_THRESHOLD):指数律(积经库乘+库除归约)
247 const mp_size_t n_values3[] = {402, 405};
248 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values3); ++n_index) {
249 mp_size_t n = n_values3[n_index];
250 mp_ptr m = alloc_limbs(n), b = alloc_limbs(n), dst = alloc_limbs(n), r1 = alloc_limbs(n),
251 r2 = alloc_limbs(n), r12 = alloc_limbs(n), t = alloc_limbs(2 * n), q = alloc_limbs(2 * n);
252 make_odd_mod(m, b, n, &seed);
253 u64 e1 = 0x9e3779b9ull >> 1, e2 = 0x9e3779b9ull - e1;
254 mp_limb_t ep1[1] = {e1}, ep2[1] = {e2}, ep12[1] = {e1 + e2};
255 lmmp_powmod_odd_(r1, b, ep1, 1, m, n);
256 lmmp_powmod_odd_(r2, b, ep2, 1, m, n);
257 lmmp_powmod_odd_(dst, b, ep12, 1, m, n);
258 TEST_CHECK_MSG(mpn_cmp(dst, n, m, n) < 0, "fold result in range");
259 lmmp_mul_(t, r1, n, r2, n);
260 lmmp_div_(q, r12, t, 2 * n, m, n);
261 TEST_CHECK_MSG(memcmp(dst, r12, (size_t)n * 8) == 0, "fold exponent law");
263 lmmp_free(r12); lmmp_free(t); lmmp_free(q);
264 }
265}
void lmmp_powmod_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_limb_t mod)
计算奇模数模幂 [dst,1] = [bp,1]^[ep,en] % mod
void lmmp_powmod_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mod)
计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2]
static u64 powmod_ref_u64(u64 b, const u64 *ep, mp_size_t en, u64 m)

引用了 ARRAY_SIZE, lmmp_div_(), lmmp_free(), lmmp_mul_(), lmmp_powmod_(), lmmp_powmod_1_(), lmmp_powmod_2_(), lmmp_powmod_odd_(), lmmp_zero, make_odd_mod(), n, powmod_ref_u64(), r1, r2, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [6/6]

TEST_CASE ( "numth/powmod" ,
redc_value  )

在文件 test_powmod.c 第 96 行定义.

96 {
97 u64 seed = 0x9e3779b97f4a7c15ull;
98 // 覆盖 REDC 两条路径:小尺寸全积取高半、>= REDC_MERSENNE_THRESHOLD 的梅森折叠
99 const mp_size_t n_values[] = {1, 2, 3, 5, 9, 17, 33, 50, 402};
100 for (size_t n_index = 0; n_index < ARRAY_SIZE(n_values); ++n_index) {
101 mp_size_t n = n_values[n_index];
102 for (int iter = 0; iter < 3; ++iter) {
103 mp_ptr m = alloc_limbs(n), a = alloc_limbs(n), b = alloc_limbs(n);
104 make_odd_mod(m, a, n, &seed);
105 make_odd_mod(m, b, n, &seed);
106 mp_ptr t = alloc_limbs(2 * n), dst = alloc_limbs(n + 1), ninv = alloc_limbs(n);
107 lmmp_mul_(t, a, n, b, n);
108 lmmp_binvert_(ninv, m, n, n);
109 // ninv = -m^(-1) mod B^n(两补码取负;逆元为奇不会越顶)
110 u64 carry = 1;
111 for (mp_size_t i = 0; i < n; ++i) {
112 u64 x = ~ninv[i];
113 u64 s = x + carry;
114 carry = (s == 0) ? 1u : 0u;
115 ninv[i] = s;
116 }
117 mp_limb_t cy = lmmp_redc_(dst, t, ninv, m, n);
118 TEST_CHECK_MSG(cy <= 1, "redc carry range");
119 // u = dst + cy*B^n;u < 2m
120 mp_ptr u = alloc_limbs(n + 1);
121 lmmp_zero(u, n + 1);
122 memcpy(u, dst, (size_t)n * 8);
123 if (cy) u[n] = 1;
124 // 2m = m+m(库加)
125 mp_ptr twom2 = alloc_limbs(n + 1);
126 lmmp_zero(twom2, n + 1);
127 lmmp_copy(twom2, m, n);
128 lmmp_add_n_(twom2, twom2, twom2, n + 1);
129 TEST_CHECK_MSG(mpn_cmp(u, n + 1, twom2, n + 1) < 0, "redc < 2m");
130 // u*B^n ≡ t (mod m):同余仅对模 m 成立,经库除法(Knuth D,独立
131 // 路径)双侧取余精确比对:(u*B^n) mod m == (a*b) mod m
132 {
133 mp_ptr P = alloc_limbs(2 * n + 2), q2 = alloc_limbs(n + 2), rm = alloc_limbs(n),
134 rt = alloc_limbs(n);
135 lmmp_zero(P, 2 * n + 2);
136 memcpy(P + n, u, (size_t)(n + 1) * 8); // P = u*B^n(≤ 2n+1 limbs)
137 lmmp_div_(q2, rm, P, 2 * n + 1, m, n);
138 lmmp_div_(q2, rt, t, 2 * n, m, n);
139 TEST_CHECK_MSG(mpn_eq(rm, n, rt, n), "redc (u*B^n) mod m == t mod m");
140 lmmp_free(P); lmmp_free(q2); lmmp_free(rm); lmmp_free(rt);
141 }
143 lmmp_free(ninv); lmmp_free(twom2); lmmp_free(u);
144 }
145 }
146}
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
mp_limb_t lmmp_redc_(mp_ptr dst, mp_srcptr tp, mp_srcptr ninv, mp_srcptr mp, mp_size_t n)
Montgomery 归约(REDC):计算 ([tp,2n] + q*[mp,n]) / B^n,其中 q = [tp,n] * [ninv,n] mod B^n,即结果为 [tp,...
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元

引用了 ARRAY_SIZE, lmmp_add_n_(), lmmp_binvert_(), lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_mul_(), lmmp_redc_(), lmmp_zero, make_odd_mod(), n, s, t, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_powmod()

void test_powmod ( void )

在文件 test_powmod.c 第 542 行定义.

542 {
543 TEST_RUN("numth/powmod", redc_value);
544 TEST_RUN("numth/powmod", powmod_odd_and_dispatch);
545 TEST_RUN("numth/powmod", powmod_exponent_and_product_laws);
546 TEST_RUN("numth/powmod", powlo_family);
547 TEST_RUN("numth/powmod", powmod_even_two_adic);
548 TEST_RUN("numth/powmod", mont_sp_redc_value);
549}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_powmod() , 以及 TEST_RUN.

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

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

◆ top_bits()

int top_bits ( u64 x)
static

在文件 test_powmod.c 第 62 行定义.

62{ return 64 - __builtin_clzll(x); }

引用了 top_bits().

函数调用图: