LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
28
LMMP_VECT_CONSERVATIVE
29
30
31
#define MONT63_MAX ((ulong)(0x7fffffffffffffff))
32
33
/**
34
* @brief 蒙域约化 REDC
35
* @warning m<2^63
36
*/
37
static
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
*/
48
static
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
52
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
,
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);
57
lmmp_param_assert
(d <=
MONT63_MAX
);
58
lmmp_param_assert
(dinv * d == 1);
59
lmmp_param_assert
(dinv + mi == 0);
60
lmmp_param_assert
(base < d);
61
lmmp_param_assert
(
r2
< 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
114
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
,
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);
119
lmmp_param_assert
(d <=
MONT63_MAX
);
120
lmmp_param_assert
(dinv * d == 1);
121
lmmp_param_assert
(dinv + mi == 0);
122
lmmp_param_assert
(base < d);
123
lmmp_param_assert
(
r2
< 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
}
k
#define k
mont63_reduce
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)
定义
is_prime_ulong.c:67
MONT63_MAX
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
is_prime_ulong.c:36
mont63_mul
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
定义
is_prime_ulong.c:83
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
LMMP_VECT_CONSERVATIVE
#define LMMP_VECT_CONSERVATIVE
定义
lmmp.h:201
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
longlong.h
r2
#define r2
t
#define t
s
#define s
c1
#define c1
c0
#define c0
numth.h
ulong
uint64_t ulong
定义
numth.h:39
trialdiv.h
lmmp_mod_8chunk_1_
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
定义
mod_chunk.c:114
lmmp_mod_4chunk_1_
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
定义
mod_chunk.c:52
src
lmmp
numth
mod_chunk.c
生成于
, 为 LMMP使用
1.18.0