LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
mod_chunk.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#include "lmmp/numth.h"
24#include "lmmp/lmmpn.h"
25#include "impl/longlong.h"
26#include "impl/trialdiv.h"
27
29
30
31#define MONT63_MAX ((ulong)(0x7fffffffffffffff))
32
33/**
34 * @brief 蒙域约化 REDC
35 * @warning m<2^63
36 */
37static inline ulong mont63_reduce(u128 t, ulong m, ulong m_inv) {
38 // m < 2^63 时 k*m + t < 2^127,无 129 位溢出
39 ulong k = _u128low(t) * m_inv;
40 u128 sum = (u128)k * m + t;
41 ulong hi = _u128high(sum);
42 return hi >= m ? hi - m : hi;
43}
44
45/**
46 * @brief 蒙域乘:a*b*R^-1 mod m(R=B)
47 */
48static inline ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv) {
49 return mont63_reduce((u128)a * b, m, m_inv);
50}
51
53 mp_limb_t base, mp_limb_t mi) {
54 lmmp_param_assert(na > 0);
55 lmmp_param_assert(numa != NULL);
56 lmmp_param_assert(d % 2 == 1);
58 lmmp_param_assert(dinv * d == 1);
59 lmmp_param_assert(dinv + mi == 0);
60 lmmp_param_assert(base < d);
62
63 mp_size_t L = na >> 2, t = na & 3;
64 ulong bw = r2, wm = base;
65 for (mp_size_t ee = L; ee; ee >>= 1) {
66 if (ee & 1) wm = mont63_mul(wm, bw, d, mi);
67 bw = mont63_mul(bw, bw, d, mi);
68 }
69 ulong bt = r2; /* mont(B^t):t=0 时终段有 if(t) 守卫 */
70 for (mp_size_t k = 1; k < t; ++k) bt = mont63_mul(bt, r2, d, mi);
71
72 const mp_limb_t *p0 = numa + t, *p1 = numa + t + L, *p2 = numa + t + 2 * L,
73 *p3 = numa + t + 3 * L, *e = numa + t + L;
74 ulong c0 = 0, c1 = 0, c2 = 0, c3 = 0;
75 while (p0 < e) {
76 ulong s, l, q;
77 s = *p0++;
78 l = s - c0;
79 q = l * dinv;
80 c0 = _u128high((u128)q * d) + (s < c0);
81 s = *p1++;
82 l = s - c1;
83 q = l * dinv;
84 c1 = _u128high((u128)q * d) + (s < c1);
85 s = *p2++;
86 l = s - c2;
87 q = l * dinv;
88 c2 = _u128high((u128)q * d) + (s < c2);
89 s = *p3++;
90 l = s - c3;
91 q = l * dinv;
92 c3 = _u128high((u128)q * d) + (s < c3);
93 }
94 ulong cb = 0;
95 for (mp_size_t i = 0; i < t; ++i) {
96 ulong s = numa[i], l = s - cb;
97 ulong q = l * dinv;
98 cb = _u128high((u128)q * d) + (s < cb);
99 }
100 ulong cj[4] = {c0, c1, c2, c3}, wT = wm, acc = 0;
101 for (int j = 0; j < 3; ++j) {
102 acc += mont63_mul(cj[j], wm, d, mi);
103 acc = acc >= d ? acc - d : acc;
104 wm = mont63_mul(wm, wT, d, mi);
105 }
106 acc += mont63_mul(cj[3], wm, d, mi);
107 acc = acc >= d ? acc - d : acc;
108 acc += cb; /* 底组项权重 B^t*w^0 */
109 acc = acc >= d ? acc - d : acc;
110 if (t) acc = mont63_mul(acc, bt, d, mi); /* ×B^t:N ≡ -B^t*acc */
111 return acc ? d - acc : 0;
112}
113
115 mp_limb_t base, mp_limb_t mi) {
116 lmmp_param_assert(na > 0);
117 lmmp_param_assert(numa != NULL);
118 lmmp_param_assert(d % 2 == 1);
120 lmmp_param_assert(dinv * d == 1);
121 lmmp_param_assert(dinv + mi == 0);
122 lmmp_param_assert(base < d);
124
125 mp_size_t L = na >> 3, t = na & 7;
126 ulong bw = r2, wm = base;
127 for (mp_size_t ee = L; ee; ee >>= 1) {
128 if (ee & 1) wm = mont63_mul(wm, bw, d, mi);
129 bw = mont63_mul(bw, bw, d, mi);
130 }
131 ulong bt = r2; /* mont(B^t):t=0 时终段有 if(t) 守卫 */
132 for (mp_size_t k = 1; k < t; ++k) bt = mont63_mul(bt, r2, d, mi);
133
134 const mp_limb_t *p0 = numa + t, *p1 = numa + t + L, *p2 = numa + t + 2 * L,
135 *p3 = numa + t + 3 * L, *p4 = numa + t + 4 * L, *p5 = numa + t + 5 * L,
136 *p6 = numa + t + 6 * L, *p7 = numa + t + 7 * L, *e = numa + t + L;
137 ulong c0 = 0, c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0, c7 = 0;
138 while (p0 < e) {
139 ulong s, l, q;
140 s = *p0++;
141 l = s - c0;
142 q = l * dinv;
143 c0 = _u128high((u128)q * d) + (s < c0);
144 s = *p1++;
145 l = s - c1;
146 q = l * dinv;
147 c1 = _u128high((u128)q * d) + (s < c1);
148 s = *p2++;
149 l = s - c2;
150 q = l * dinv;
151 c2 = _u128high((u128)q * d) + (s < c2);
152 s = *p3++;
153 l = s - c3;
154 q = l * dinv;
155 c3 = _u128high((u128)q * d) + (s < c3);
156 s = *p4++;
157 l = s - c4;
158 q = l * dinv;
159 c4 = _u128high((u128)q * d) + (s < c4);
160 s = *p5++;
161 l = s - c5;
162 q = l * dinv;
163 c5 = _u128high((u128)q * d) + (s < c5);
164 s = *p6++;
165 l = s - c6;
166 q = l * dinv;
167 c6 = _u128high((u128)q * d) + (s < c6);
168 s = *p7++;
169 l = s - c7;
170 q = l * dinv;
171 c7 = _u128high((u128)q * d) + (s < c7);
172 }
173 ulong cb = 0;
174 for (mp_size_t i = 0; i < t; ++i) {
175 ulong s = numa[i], l = s - cb;
176 ulong q = l * dinv;
177 cb = _u128high((u128)q * d) + (s < cb);
178 }
179 ulong cj[8] = {c0, c1, c2, c3, c4, c5, c6, c7}, wT = wm, acc = 0;
180 for (int j = 0; j < 7; ++j) {
181 acc += mont63_mul(cj[j], wm, d, mi);
182 acc = acc >= d ? acc - d : acc;
183 wm = mont63_mul(wm, wT, d, mi);
184 }
185 acc += mont63_mul(cj[7], wm, d, mi);
186 acc = acc >= d ? acc - d : acc;
187 acc += cb; /* 底组项权重 B^t*w^0 */
188 acc = acc >= d ? acc - d : acc;
189 if (t) acc = mont63_mul(acc, bt, d, mi); /* ×B^t:N ≡ -B^t*acc */
190 return acc ? d - acc : 0;
191}
#define k
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_VECT_CONSERVATIVE
定义 lmmp.h:201
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define r2
#define t
#define s
#define c1
#define c0
uint64_t ulong
定义 numth.h:39
mp_limb_t lmmp_mod_8chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
8 链折叠取模:r = [numa,na] mod d
mp_limb_t lmmp_mod_4chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
4 链折叠取模:r = [numa,na] mod d