LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powmod_2.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 "impl/tmp_alloc.h"
24#include "impl/longlong.h"
25#include "numth/powmod.h"
26#include "lmmp/lmmpn.h"
27#include "lmmp/numth.h"
28
29#define getbit(p, bi) ((p[(bi - 1) / LIMB_BITS] >> (bi - 1) % LIMB_BITS) & 1)
30
31static inline mp_limb_t getbits(const mp_limb_t* p, mp_bitcnt_t bi, mp_bitcnt_t nbits) {
32 mp_bitcnt_t nbits_in_r;
33 mp_limb_t r;
34 mp_size_t i;
35
36 if (bi <= nbits) {
37 return p[0] & (((mp_limb_t)1 << bi) - 1);
38 } else {
39 bi -= nbits; /* bit index of low bit to extract */
40 i = bi / LIMB_BITS; /* word index of low bit to extract */
41 bi %= LIMB_BITS; /* bit index in low word */
42 r = p[i] >> bi; /* extract (low) bits */
43 nbits_in_r = LIMB_BITS - bi; /* number of bits now in r */
44 if (nbits_in_r < nbits) /* did we get enough bits? */
45 r += p[i + 1] << nbits_in_r; /* prepend bits from higher word */
46 return r & (((mp_limb_t)1 << nbits) - 1);
47 }
48}
49
51 return (n - 1) * LIMB_BITS + lmmp_limb_bits_(p[n - 1]);
52}
53
54/* mul_128/sqr_128/mont2_redc 与 is_prime_2.c 同源拷贝(编译器分派的
55 惯例与正确性论证见彼处) */
56static inline void mul_128(u128 a, u128 b, u128* hi, u128* lo) {
57#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
58 ulong a0 = _u128low(a), a1 = _u128high(a);
59 ulong b0 = _u128low(b), b1 = _u128high(b);
60 u128 p00 = (u128)a0 * b0;
61 u128 p01 = (u128)a0 * b1;
62 u128 p10 = (u128)a1 * b0;
63 u128 p11 = (u128)a1 * b1;
64 u128 mid = p01 + p10;
65 u128 cm = mid < p01; /* 129 位交叉和进位,属 hi 的第 64 位 */
66 u128 l = (mid << 64) + p00;
67 u128 cl = l < p00; /* 进位属 hi 的第 0 位 */
68 *lo = l;
69 *hi = p11 + (mid >> 64) + cl + (cm << 64);
70#else
71 ulong u[4];
72 _umul128to256_(_u128high(a), _u128low(a), _u128high(b), _u128low(b), u);
73 *lo = ((u128)u[1] << 64) | u[0];
74 *hi = ((u128)u[3] << 64) | u[2];
75#endif
76}
77
78/* a^2 -> (hi, lo):交叉积单次乘法后整体加倍(3 乘法平方) */
79static inline void sqr_128(u128 a, u128* hi, u128* lo) {
80#if defined(__clang__) && !defined(LMMP_ASM_ARM64)
81 ulong a0 = _u128low(a), a1 = _u128high(a);
82 u128 p0 = (u128)a0 * a0;
83 u128 m = (u128)a0 * a1; /* 交叉积,加倍后 129 位 */
84 u128 p1 = (u128)a1 * a1;
85 u128 ml = m << 1;
86 u128 mh = m >> 127; /* 加倍进位(0/1),属 hi 的第 64 位 */
87 u128 l = (ml << 64) + p0;
88 u128 cl = l < p0;
89 *lo = l;
90 *hi = p1 + (ml >> 64) + cl + (mh << 64);
91#else
92 ulong u[4];
93 _usqr128to256_(_u128high(a), _u128low(a), u);
94 *lo = ((u128)u[1] << 64) | u[0];
95 *hi = ((u128)u[3] << 64) | u[2];
96#endif
97}
98
99/* 2 limb REDC:r = (T + q*n)/B^2,T = thi*B^2 + tlo < n*B^2,q = tlo*ninv
100 mod B^2(u128 截断乘恰为其低 128 位)。n 接近 B^2 时和可达 129 位,
101 回绕进位下按模 2^128 回绕减 n 恰为真值且已 < n */
102static inline u128 mont2_redc(u128 thi, u128 tlo, u128 n, u128 ninv) {
103#if defined(LMMP_ASM_ARM64)
104 u128 q = tlo * ninv;
105 u128 qh, ql;
106 mul_128(q, n, &qh, &ql);
107 ulong t0 = _u128low(tlo), t1 = _u128high(tlo);
108 ulong p0 = _u128low(ql), p1 = _u128high(ql);
109 ulong k0 = (t0 + p0) < t0; /* lo 低 limb 进位(lo 值本身无消费者) */
110 ulong l1 = t1 + p1;
111 ulong k1 = l1 < t1;
112 l1 += k0;
113 k1 |= l1 < k0;
114 ulong h0 = _u128low(thi) + _u128low(qh);
115 ulong j0 = h0 < _u128low(qh);
116 h0 += k1;
117 j0 |= h0 < k1;
118 ulong h1 = _u128high(thi) + _u128high(qh);
119 ulong j1 = h1 < _u128high(qh);
120 h1 += j0;
121 j1 |= h1 < j0;
122 ulong n0 = _u128low(n), n1 = _u128high(n);
123 if (j1 || (h1 > n1) || (h1 == n1 && h0 >= n0)) {
124 ulong bw = h0 < n0; /* 借位跨 limb 传播 */
125 h0 -= n0;
126 h1 -= n1 + bw; /* j1 分支下回绕即真值 */
127 }
128 return ((u128)h1 << 64) | h0;
129#else
130 u128 q = tlo * ninv;
131 u128 qh, ql, lo, hi, c, c1, c2;
132 mul_128(q, n, &qh, &ql);
133 lo = tlo + ql;
134 c = lo < tlo;
135 hi = thi + qh;
136 c1 = hi < thi;
137 hi += c;
138 c2 = c && hi == 0;
139 if (c1 | c2)
140 hi -= n;
141 else if (hi >= n)
142 hi -= n;
143 return hi;
144#endif
145}
146
147static inline u128 mont2_sqr(u128 a, u128 n, u128 ninv) {
148 u128 h, l;
149 sqr_128(a, &h, &l);
150 return mont2_redc(h, l, n, ninv);
151}
152
153static inline u128 mont2_mul_2(u128 a, u128 b, u128 n, u128 ninv) {
154 u128 h, l;
155 mul_128(a, b, &h, &l);
156 return mont2_redc(h, l, n, ninv);
157}
158
160 mp_ptr restrict dst,
163 mp_size_t en,
165) {
166 lmmp_param_assert(dst != NULL && bp != NULL && ep != NULL && mod != NULL);
167 lmmp_param_assert(en > 0 && ep[en - 1] > 0);
168 lmmp_param_assert(mod[0] % 2 == 1);
169 lmmp_param_assert(mod[1] != 0);
170
171 u128 n = _u128load(mod);
172 if (_u128load(bp) == 0) {
173 lmmp_zero(dst, 2);
174 return;
175 }
176 mp_bitcnt_t ebi = count_bits(ep, en);
177 /* 指数为 1:契约 [bp,2] < [mod,2],直接拷贝即已取模 */
178 if (ebi == 1) {
179 lmmp_copy(dst, bp, 2);
180 return;
181 }
182
183 unsigned windowsize = lmmp_powmod_win_size_(ebi);
184 lmmp_debug_assert(windowsize < ebi);
185 /* ninv = -m^(-1) mod B^2:u128 回绕取负 */
186 mp_limb_t inv[2];
187 lmmp_binvert_2_(inv, mod);
188 u128 ninv = 0 - _u128load(inv);
189
190 /* 进蒙域:x_m = b*B^2 mod m,一次 4/2 除法(低位补两个零 limb 实现 <<B^2) */
191 u128 u;
192 {
193 mp_limb_t num[4] = {0, 0, bp[0], bp[1]};
194 mp_limb_t r[2];
195 lmmp_div_(NULL, r, num, 4, mod, 2);
196 u = _u128load(r);
197 }
198
199 mp_bitcnt_t cnt;
200 unsigned this_windowsize;
201 mp_limb_t expbits;
202 TEMP_DECL;
203 u128* restrict pp = TALLOC_TYPE((mp_size_t)1 << (windowsize - 1), u128);
204
205 pp[0] = u;
206 if (windowsize > 1) {
207 u128 b2 = mont2_sqr(u, n, ninv);
208 for (mp_size_t i = 1; i < ((mp_size_t)1 << (windowsize - 1)); i++)
209 pp[i] = mont2_mul_2(pp[i - 1], b2, n, ninv);
210
211 expbits = getbits(ep, ebi, windowsize);
212 ebi -= windowsize;
213
214 ctz_shr_u64(expbits, expbits, cnt);
215 ebi += cnt;
216
217 u = pp[expbits >> 1];
218 } else {
219 --ebi;
220 }
221
222 while (ebi != 0) {
223 while (getbit(ep, ebi) == 0) {
224 u = mont2_sqr(u, n, ninv);
225 if (--ebi == 0)
226 goto done;
227 }
228
229 /* The next bit of the exponent is 1. Now extract the largest block of
230 bits <= windowsize, and such that the least significant bit is 1. */
231
232 expbits = getbits(ep, ebi, windowsize);
233 this_windowsize = LMMP_MIN(windowsize, ebi);
234
235 ctz_shr_u64(expbits, expbits, cnt);
236 this_windowsize -= cnt;
237 ebi -= this_windowsize;
238
239 while (this_windowsize > 1) {
240 u = mont2_sqr(u, n, ninv);
241 u = mont2_sqr(u, n, ninv);
242 this_windowsize -= 2;
243 }
244
245 if (this_windowsize != 0)
246 u = mont2_sqr(u, n, ninv);
247 u = mont2_mul_2(u, pp[expbits >> 1], n, ninv);
248 }
249
250done:
251 /* 出蒙域:REDC(u * 1) = u*B^(-2) mod m */
252 _u128store(dst, mont2_redc(0, u, n, ninv));
253 TEMP_FREE;
254}
#define lmmp_limb_bits_
static void mul_128(u128 a, u128 b, u128 *hi, u128 *lo)
static void sqr_128(u128 a, u128 *hi, u128 *lo)
static u128 mont2_mul_2(u128 a, u128 b, u128 n, u128 ninv)
static u128 mont2_redc(u128 thi, u128 tlo, u128 n, u128 ninv)
static u128 mont2_sqr(u128 a, u128 n, u128 ninv)
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
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
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
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4])
#define b0
#define b1
#define a0
#define a1
#define b2
#define n
#define lo
#define c1
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
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]
#define getbit(p, bi)
定义 powlo.c:65
static mp_bitcnt_t count_bits(mp_srcptr p, mp_size_t n)
定义 powlo.c:86
static mp_limb_t getbits(const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
定义 powlo.c:67
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)