54 while (i < rn && r[i] == ~(
mp_limb_t)0) ++i;
59 return memcmp(x, y, (
size_t)
n *
sizeof(
mp_limb_t)) == 0;
62TEST_CASE(
"mul/mersenne_dc", mersenne_dc_vs_oracle) {
63 u64 seed = 0x51ce5eed1a2b3c4dull;
64 const mp_size_t sizes[] = {2, 3, 5, 8, 13, 14, 16, 17, 31, 32, 64, 100, 256,
65 511, 512, 768, 1000, 1024, 1721, 2048, 3442};
66 for (
size_t rn_index = 0; rn_index <
ARRAY_SIZE(sizes); ++rn_index) {
68 mp_size_t shapes[6][2] = {{rn, rn}, {rn, rn / 2 + 1}, {rn, 1},
69 {rn / 2 + 1, rn / 2 + 1}, {3 * rn / 4 + 1, rn / 4 + 1},
70 {rn / 2, rn / 4 + 1}};
71 for (
size_t sh_index = 0; sh_index <
ARRAY_SIZE(shapes); ++sh_index) {
74 if (nb > na || na > rn || na + nb <= rn / 2)
continue;
75 for (
int mode = 0; mode < 3; ++mode) {
76 mp_ptr a = alloc_limbs(na), b = alloc_limbs(nb);
78 random_limbs(a, na, &seed);
79 random_limbs(b, nb, &seed);
80 }
else if (mode == 1) {
87 mp_ptr r = alloc_limbs(rn), ro = alloc_limbs(rn), full = alloc_limbs(2 * rn + 2);
99 mp_size_t ans[4] = {rn, 3 * rn / 4 + 1, rn > 2 ? rn / 4 + 1 : rn, rn / 2};
100 for (
size_t an_index = 0; an_index <
ARRAY_SIZE(ans); ++an_index) {
102 if (
an > rn || 4 *
an <= rn)
continue;
103 for (
int mode = 0; mode < 3; ++mode) {
106 random_limbs(a,
an, &seed);
111 mp_ptr r = alloc_limbs(rn), ro = alloc_limbs(rn), full = alloc_limbs(2 * rn + 2);
117 for (
mp_size_t i = 0; i < rn; ++i) r[i] = ~ro[i];
127TEST_CASE(
"mul/mersenne_next_size", mersenne_next_size_props) {
141 u64 seed = 0x2f6e1d5a9c83b701ull;
142 for (
int t = 0;
t < 16; ++
t) {
145 mp_ptr a = alloc_limbs(
n), b = alloc_limbs(
n);
146 mp_ptr r = alloc_limbs(rn), ro = alloc_limbs(rn), full = alloc_limbs(2 * rn + 2);
147 random_limbs(a,
n, &seed);
148 random_limbs(b,
n, &seed);
149 if (
n +
n > rn / 2) {
158TEST_CASE(
"mul/mersenne_fft", mersenne_fft_single_limb) {
160 const mp_limb_t b = 0xfedcba9876543210ull;
195 TEST_RUN(
"mul/mersenne_dc", mersenne_dc_vs_oracle);
196 TEST_RUN(
"mul/mersenne_next_size", mersenne_next_size_props);
197 TEST_RUN(
"mul/mersenne_fft", mersenne_fft_single_limb);
198 TEST_RUN(
"mul/fermat_fft", fermat_cache_single_limb);
#define lmmp_copy(dst, src, n)
#define lmmp_zero(dst, n)
const mp_limb_t * mp_srcptr
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define MUL_MERSENNE_DC_THRESHOLD
#define MUL_FFT_MODF_THRESHOLD
void test_mul_mersenne(void)
void lmmp_mul_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
void lmmp_mul_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_sqr_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
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]
void lmmp_sqr_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_sqr_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
#define lmmp_inc_1(p, inc)
加指定值宏(预期无进位)
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
void lmmp_mul_mersenne_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static void lmmp_fft_gr_cache_free_(fft_gr_cache *ctx)
释放费马或梅森数模乘法缓存上下文
void lmmp_mul_fermat_cache_(mp_ptr dst, mp_srcptr numa, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_mul_fermat_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
费马数模乘法(缓存版) [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1 第二个操作数将被缓存
void lmmp_mul_mersenne_cache_init_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, fft_gr_cache *ctx)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1 第二个操作数将被缓存
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEST_CASE(category, name)
#define TEST_RUN(category, name)
static bool limbs_same(const mp_limb_t *x, const mp_limb_t *y, mp_size_t n)
static void mersenne_oracle(mp_ptr r, mp_size_t rn, mp_srcptr a, mp_size_t na, mp_srcptr b, mp_size_t nb, mp_ptr full)
Copyright (C) 2026 HJimmyK (Jericho Knox)