LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
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/* 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 即规范结果 */
57static 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
69 mp_ptr restrict dst,
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
149done:
150 /* 出蒙域:REDC(u * 1) = u*B^(-1) mod m */
151 dst[0] = powmod1_redc_(u, mod, ninv);
152 TEMP_FREE;
153}
#define k
#define lmmp_limb_bits_
mp_limb_t * mp_ptr
定义 lmmp.h:96
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
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
#define b2
#define t
#define n
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
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
uint32_t uint
定义 numth.h:38
#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
static mp_limb_t powmod1_redc_(u128 t, mp_limb_t m, mp_limb_t ninv)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define TEMP_DECL
#define TEMP_FREE
#define TALLOC_TYPE(n, type)