LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
powmod_1.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
31
static
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
50
static
inline
mp_bitcnt_t
count_bits
(
mp_srcptr
p,
mp_size_t
n
) {
51
return
(
n
- 1) *
LIMB_BITS
+
lmmp_limb_bits_
(p[
n
- 1]);
52
}
53
54
/* 1 limb REDC:r = (T + k*m)/B mod m,k = T_lo*ninv mod B,ninv = -m^(-1) mod B。
55
T < m*B 时结果 < 2m;k*m + T < 2^129,第 129 位 c 由 128 位回绕捕获,
56
回绕进位下 hi - m 即规范结果 */
57
static
inline
mp_limb_t
powmod1_redc_
(u128
t
,
mp_limb_t
m,
mp_limb_t
ninv) {
58
mp_limb_t
k
= _u128low(
t
) * ninv;
59
u128 km = (u128)
k
* m;
60
u128 sum = km +
t
;
61
uint
c = sum < km;
62
mp_limb_t
hi = _u128high(sum);
63
if
(c)
64
return
hi - m;
65
return
hi >= m ? hi - m : hi;
66
}
67
68
void
lmmp_powmod_1_
(
69
mp_ptr
restrict
dst,
70
mp_srcptr
restrict
bp,
71
mp_srcptr
restrict
ep,
72
mp_size_t
en,
73
mp_limb_t
mod
74
) {
75
lmmp_param_assert
(dst != NULL && bp != NULL && ep != NULL);
76
lmmp_param_assert
(en > 0 && ep[en - 1] > 0);
77
lmmp_param_assert
(mod % 2 == 1 && mod > 1);
78
lmmp_param_assert
(bp[0] < mod);
79
80
if
(bp[0] == 0) {
81
dst[0] = 0;
82
return
;
83
}
84
mp_bitcnt_t
ebi =
count_bits
(ep, en);
85
/* 指数为 1:契约 [bp,1] < mod,直接拷贝即已取模 */
86
if
(ebi == 1) {
87
dst[0] = bp[0];
88
return
;
89
}
90
91
unsigned
windowsize = lmmp_powmod_win_size_(ebi);
92
lmmp_debug_assert
(windowsize < ebi);
93
mp_limb_t
ninv = 0 -
lmmp_binvert_ulong_
(mod);
94
/* 进蒙域:x_m = b*B mod m,128/64 一步除法(b < mod 保证商不溢出) */
95
mp_limb_t
u;
96
(void)
_udiv128by64to64_
(bp[0], 0, mod, &u);
97
98
mp_bitcnt_t
cnt;
99
unsigned
this_windowsize;
100
mp_limb_t
expbits;
101
TEMP_DECL
;
102
mp_ptr
restrict
pp =
TALLOC_TYPE
((
mp_size_t
)1 << (windowsize - 1),
mp_limb_t
);
103
104
pp[0] = u;
105
if
(windowsize > 1) {
106
mp_limb_t
b2
=
powmod1_redc_
((u128)u * u, mod, ninv);
107
for
(
mp_size_t
i = 1; i < ((
mp_size_t
)1 << (windowsize - 1)); i++)
108
pp[i] =
powmod1_redc_
((u128)pp[i - 1] *
b2
, mod, ninv);
109
110
expbits =
getbits
(ep, ebi, windowsize);
111
ebi -= windowsize;
112
113
ctz_shr_u64
(expbits, expbits, cnt);
114
ebi += cnt;
115
116
u = pp[expbits >> 1];
117
}
else
{
118
--ebi;
119
}
120
121
while
(ebi != 0) {
122
while
(
getbit
(ep, ebi) == 0) {
123
u =
powmod1_redc_
((u128)u * u, mod, ninv);
124
if
(--ebi == 0)
125
goto
done;
126
}
127
128
/* The next bit of the exponent is 1. Now extract the largest block of
129
bits <= windowsize, and such that the least significant bit is 1. */
130
131
expbits =
getbits
(ep, ebi, windowsize);
132
this_windowsize =
LMMP_MIN
(windowsize, ebi);
133
134
ctz_shr_u64
(expbits, expbits, cnt);
135
this_windowsize -= cnt;
136
ebi -= this_windowsize;
137
138
while
(this_windowsize > 1) {
139
u =
powmod1_redc_
((u128)u * u, mod, ninv);
140
u =
powmod1_redc_
((u128)u * u, mod, ninv);
141
this_windowsize -= 2;
142
}
143
144
if
(this_windowsize != 0)
145
u =
powmod1_redc_
((u128)u * u, mod, ninv);
146
u =
powmod1_redc_
((u128)u * pp[expbits >> 1], mod, ninv);
147
}
148
149
done:
150
/* 出蒙域:REDC(u * 1) = u*B^(-1) mod m */
151
dst[0] =
powmod1_redc_
(u, mod, ninv);
152
TEMP_FREE
;
153
}
k
#define k
lmmp_limb_bits_
#define lmmp_limb_bits_
定义
inlines.h:164
mp_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_bitcnt_t
size_t mp_bitcnt_t
定义
lmmp.h:98
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
lmmp_debug_assert
#define lmmp_debug_assert(x)
定义
lmmp.h:498
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
LMMP_MIN
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义
lmmp.h:450
LIMB_BITS
#define LIMB_BITS
定义
lmmp.h:102
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
longlong.h
ctz_shr_u64
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
longlong.h:55
_udiv128by64to64_
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
定义
longlong.h:386
b2
#define b2
t
#define t
n
#define n
numth.h
lmmp_binvert_ulong_
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
定义
binvert_1.c:49
lmmp_powmod_1_
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
uint
uint32_t uint
定义
numth.h:38
getbit
#define getbit(p, bi)
定义
powlo.c:65
count_bits
static mp_bitcnt_t count_bits(mp_srcptr p, mp_size_t n)
定义
powlo.c:86
getbits
static mp_limb_t getbits(const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
定义
powlo.c:67
powmod.h
powmod1_redc_
static mp_limb_t powmod1_redc_(u128 t, mp_limb_t m, mp_limb_t ninv)
定义
powmod_1.c:57
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
tmp_alloc.h
TEMP_DECL
#define TEMP_DECL
定义
tmp_alloc.h:145
TEMP_FREE
#define TEMP_FREE
定义
tmp_alloc.h:175
TALLOC_TYPE
#define TALLOC_TYPE(n, type)
定义
tmp_alloc.h:173
src
lmmp
numth
powmod_1.c
生成于
, 为 LMMP使用
1.18.0