LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_powmod.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23/* 模幂家族验证(无 BigInt oracle;整数幂见 test_numth_pow.cpp):
24 1. 费马小定理(素模 p:b^(p-1)==1)、指数律、乘法性、
25 n==1 时 u64 简单参考(mullh 乘 + mod_1 余)、奇模数下
26 powmod_/powmod_1_/powmod_2_/powmod_odd_ 四入口一致、偶模数
27 CRT 代数重建、(-1)^e 与 b=0/e=1 写死角点
28 2. powlo 与 powmod_(B^n) 双算法互比(值恒相等)
29 3. REDC / mont_sp_redc:值域界 + r*B^n ≡ t (mod m) 同余重建
30*/
31
32#include "lmmp/lmmpn.h"
33#include "lmmp/numth.h"
34/* impl/powmod.h 为 C 头(restrict 限定符),C++ TU 以 __restrict 适配后包含 */
35#define restrict __restrict
36#include "numth/powmod.h"
37#undef restrict
38#include "cases.h"
40
41#include <string.h>
42
43// 64 位内任意模数参考模幂:mullh 全积 + mod_1 取余(独立于被测蒙域路径)
44static u64 powmod_ref_u64(u64 b, const u64* ep, mp_size_t en, u64 m) {
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}
60
61// 顶部 limb 有效位数
62static int top_bits(u64 x) { return 64 - __builtin_clzll(x); }
63
64// 奇模数构造:m 随机奇归一化;b 归约到 < m(div_ 一步)
65static void make_odd_mod(mp_ptr m, mp_ptr b, mp_size_t n, u64 *seed) {
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}
76
77// 模乘归约:[a,n]*[b,n] mod [m,n] → r(库乘 + 库除)
78static 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,
79 mp_ptr t, mp_ptr q) {
80 lmmp_mul_(t, a, n, b, n);
81 lmmp_div_(q, r, t, 2 * n, m, n);
82}
83
84// m = k*2^e + form(k <= 2^64,e >= 64)装配到 dst(容量 e/64+3),返回规范化长度
85static mp_size_t sp_shape_limbs(mp_ptr dst, u64 k, int e, int form) {
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}
95
96TEST_CASE("numth/powmod", redc_value) {
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}
147
148TEST_CASE("numth/powmod", powmod_odd_and_dispatch) {
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}
266
267TEST_CASE("numth/powmod", powmod_exponent_and_product_laws) {
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}
303
304TEST_CASE("numth/powmod", powlo_family) {
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}
363
364TEST_CASE("numth/powmod", powmod_even_two_adic) {
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}
463
464/*
465 稀疏模数蒙域旁路 lmmp_mont_sp_redc_ 直测(含探测):
466 - ±1 两形 × 簇偏移跨 limb 边界 × 尺寸跨 REDC 阈值;
467 - 值域 r < m 与同余 r·B^n ≡ t (mod m) 经库除法双侧取余精确比对;
468 - 探测否定侧:稠密、全 B−1、3 limb 簇均返回 0。
469*/
470TEST_CASE("numth/powmod", mont_sp_redc_value) {
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}
541
542void test_powmod(void) {
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 k
#define prod
#define bn
#define lmmp_mullh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
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)
单精度数取余
定义 div.c:38
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)
比较函数
定义 cmp.c:26
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
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
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
#define r2
#define r1
#define b2
#define t
#define s
#define n
void test_powmod(void)
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]
uint64_t ulong
定义 numth.h:39
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)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38
#define TEST_CASE(category, name)
定义 test.h:35
#define TEST_RUN(category, name)
定义 test.h:36
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)