35#define restrict __restrict
49 for (
int bit = 63; bit >= 0; --bit) {
52 if ((ep[i] >> bit) & 1) {
66 random_limbs(m,
n, seed);
68 mp_ptr raw = alloc_limbs(
n), q = alloc_limbs(
n);
69 random_limbs(raw,
n, seed);
71 if (raw[
n - 1] == 0) raw[
n - 1] = 1;
86 size_t cap = (size_t)e / 64 + 3;
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;
97 u64 seed = 0x9e3779b97f4a7c15ull;
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) {
102 for (
int iter = 0; iter < 3; ++iter) {
103 mp_ptr m = alloc_limbs(
n), a = alloc_limbs(
n), b = alloc_limbs(
n);
106 mp_ptr t = alloc_limbs(2 *
n), dst = alloc_limbs(
n + 1), ninv = alloc_limbs(
n);
114 carry = (
s == 0) ? 1u : 0u;
122 memcpy(u, dst, (
size_t)
n * 8);
125 mp_ptr twom2 = alloc_limbs(
n + 1);
133 mp_ptr P = alloc_limbs(2 *
n + 2), q2 = alloc_limbs(
n + 2), rm = alloc_limbs(
n),
136 memcpy(P +
n, u, (
size_t)(
n + 1) * 8);
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) {
153 for (
int iter = 0; iter < 3; ++iter) {
154 mp_ptr m = alloc_limbs(
n), b = alloc_limbs(
n);
156 mp_ptr dst = alloc_limbs(
n), dst2 = alloc_limbs(
n), dst3 = alloc_limbs(
n);
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}},
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);
178 TEST_CHECK_MSG(memcmp(dst, dst2, (
size_t)
n * 8) == 0,
"powmod_ dispatch == odd");
195 for (
int i = 0; i < MOD_P_CNT; ++i) {
197 u64 bbs[4] = {2, 3, 12345, (
u64)p - 1};
198 for (
size_t bb_index = 0; bb_index <
ARRAY_SIZE(bbs); ++bb_index) {
199 u64 bb = bbs[bb_index];
201 if (b == 0)
continue;
202 mp_limb_t mp[1] = {p}, bp[1] = {b}, ep[1] = {p - 1}, dst[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) {
215 mp_ptr m = alloc_limbs(
n), b = alloc_limbs(
n), dst = alloc_limbs(
n), ep = alloc_limbs(2);
217 ep[0] = 0x24f1a7e3c5590b8dull;
222 for (
mp_size_t i = 0; i <
n; ++i) zero_ok = zero_ok && dst[i] == 0;
229 for (
mp_size_t i = 0; i <
n; ++i) m1_ok = m1_ok && dst[i] == b[i];
233 bool one_ok = dst[0] == 1;
234 for (
mp_size_t i = 1; i <
n; ++i) one_ok = one_ok && dst[i] == 0;
238 random_limbs(b,
n, &s3);
247 const mp_size_t n_values3[] = {402, 405};
248 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(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);
253 u64 e1 = 0x9e3779b9ull >> 1, e2 = 0x9e3779b9ull - e1;
254 mp_limb_t ep1[1] = {e1}, ep2[1] = {e2}, ep12[1] = {e1 + e2};
261 TEST_CHECK_MSG(memcmp(dst, r12, (
size_t)
n * 8) == 0,
"fold exponent law");
267TEST_CASE(
"numth/powmod", powmod_exponent_and_product_laws) {
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) {
273 for (
int iter = 0; iter < 4; ++iter) {
274 mp_ptr m = alloc_limbs(
n), b = alloc_limbs(
n), c = alloc_limbs(
n);
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);
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};
286 TEST_CHECK_MSG(memcmp(dst, r12, (
size_t)
n * 8) == 0,
"b^(e1+e2) == b^e1*b^e2");
288 u64 e = 0x9e3779b97f4a7c15ull;
305 u64 seed = 0x1b873593f00dbeebull;
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) {
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);
316 for (
mp_size_t i = 0; i < 3; ++i) ep[i] = xorshift64(&seed);
317 ep[2] |= (
u64)1 << 63;
319 memcpy(bp, b, (
size_t)
n * 8);
320 ulong es[5] = {1, 2, 5, 0xdeadbeef, ep[0]};
321 for (
size_t e_index = 0; e_index <
ARRAY_SIZE(es); ++e_index) {
322 ulong e = es[e_index];
326 TEST_CHECK_MSG(memcmp(dst, dst2, (
size_t)
n * 8) == 0,
"powlo == powmod(B^n)");
330 TEST_CHECK_MSG(memcmp(dst, dst2, (
size_t)
n * 8) == 0,
"powlo 3-limb exp == powmod");
333 mp_ptr d1 = alloc_limbs(1);
339 mp_ptr d2 = alloc_limbs(2);
345 u64 e1 = ep[0] >> 1, e2 = ep[0] - e1;
347 mp_ptr p1 = alloc_limbs(
n), p2 = alloc_limbs(
n),
prod = alloc_limbs(2 *
n), dm = alloc_limbs(
n);
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];
376 if (nb > cap)
continue;
377 mp_ptr m = alloc_limbs(cap), b = alloc_limbs(cap), dst = alloc_limbs(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);
384 u64 s5 = seed ^ (
u64)
k * 0x9e3779b97f4a7c15ull ^ odd;
385 random_limbs(b,
n, &s5);
387 if (b[
n - 1] == 0) b[
n - 1] = 1;
388 mp_ptr q = alloc_limbs(cap);
392 mp_ptr z = alloc_limbs(cap);
394 mp_limb_t e2[1] = {2}, eodd[1] = {0x51ed270b9a3c8f11ull}, e1[1] = {1};
396 bool zk = norm_len(dst,
n) == 0;
399 TEST_CHECK_MSG(memcmp(dst, b, (
size_t)
n * 8) == 0,
"even-mod e=1 == b");
400 mp_ptr mm1 = alloc_limbs(cap);
402 sub_small_inplace(mm1,
n, 1);
404 TEST_CHECK_MSG(memcmp(dst, mm1, (
size_t)
n * 8) == 0,
"(-1)^odd == m-1");
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);
426 mp_ptr bmod = alloc_limbs(cap),
r2 = alloc_limbs(cap);
430 mp_ptr p2k = alloc_limbs(cap),
b2 = alloc_limbs(cap),
r1 = alloc_limbs(cap),
431 d2 = alloc_limbs(cap);
433 p2k[
k / 64] |= (
u64)1 << (
k % 64);
449 u64 s2 = 0xa4093822299f31d0ull;
451 for (
size_t n_index = 0; n_index <
ARRAY_SIZE(n_values); ++n_index) {
453 mp_ptr m = alloc_limbs(
n), b = alloc_limbs(
n), d1 = alloc_limbs(
n), d2 = alloc_limbs(
n);
458 TEST_CHECK_MSG(memcmp(d1, d2, (
size_t)
n * 8) == 0,
"odd dispatch match");
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},
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);
486 int form = lmmp_mont_sp_init_(&mc, m,
n);
489 int samples =
n > 100 ? 2 : 4;
490 for (
int it = 0; it < samples; ++it) {
491 random_limbs(
t, 2 * (
size_t)
n, &seed);
494 t[2 * (size_t)
n - 1] &= (tb == 64) ? ~(
u64)0 : (((
u64)1 << tb) - 1);
497 lmmp_mont_sp_redc_(r,
t, &mc);
501 mp_ptr P = alloc_limbs(2 *
n), q = alloc_limbs(
n + 2), rm = alloc_limbs(
n),
504 memcpy(P +
n, r, (
size_t)
n * 8);
517 mp_ptr m = alloc_limbs(4);
524 mp_ptr m = alloc_limbs(2);
527 TEST_CHECK_MSG(lmmp_mont_sp_init_(&mc, m, 2) == 0,
"sp probe all-ones");
531 mp_ptr m = alloc_limbs(5);
534 m[2] = 0x13579bdf2468ace0ull;
537 TEST_CHECK_MSG(lmmp_mont_sp_init_(&mc, m, 5) == 0,
"sp probe 3-limb cluster");
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);
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define lmmp_dec(p)
减1宏(预期无借位)
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
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]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
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]
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]
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]
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_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_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_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]
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]
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]
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 特化)
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CHECK_MSG(cond, msg)
#define TEST_CASE(category, name)
#define TEST_RUN(category, name)
static int top_bits(u64 x)
static mp_size_t sp_shape_limbs(mp_ptr dst, u64 k, int e, int form)
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)