LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powmod_1.c 文件参考
#include "impl/tmp_alloc.h"
#include "impl/longlong.h"
#include "numth/powmod.h"
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
powmod_1.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define getbit(p, bi)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static mp_bitcnt_t count_bits (mp_srcptr p, mp_size_t n)
static mp_limb_t getbits (const mp_limb_t *p, mp_bitcnt_t bi, mp_bitcnt_t nbits)
void lmmp_powmod_1_ (mp_ptr restrict dst, mp_srcptr restrict bp, mp_srcptr restrict ep, mp_size_t en, mp_limb_t mod)
static mp_limb_t powmod1_redc_ (u128 t, mp_limb_t m, mp_limb_t ninv)

宏定义说明

◆ getbit

#define getbit ( p,
bi )
值:
((p[(bi - 1) / LIMB_BITS] >> (bi - 1) % LIMB_BITS) & 1)
#define LIMB_BITS
定义 lmmp.h:102

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 powmod_1.c 第 29 行定义.

函数说明

◆ count_bits()

mp_bitcnt_t count_bits ( mp_srcptr p,
mp_size_t n )
inlinestatic

在文件 powmod_1.c 第 50 行定义.

50 {
51 return (n - 1) * LIMB_BITS + lmmp_limb_bits_(p[n - 1]);
52}
#define lmmp_limb_bits_
#define n

引用了 count_bits(), LIMB_BITS, lmmp_limb_bits_ , 以及 n.

函数调用图:

◆ getbits()

mp_limb_t getbits ( const mp_limb_t * p,
mp_bitcnt_t bi,
mp_bitcnt_t nbits )
inlinestatic

在文件 powmod_1.c 第 31 行定义.

31 {
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}
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
uint64_t mp_limb_t
定义 lmmp.h:92

引用了 getbits() , 以及 LIMB_BITS.

函数调用图:

◆ lmmp_powmod_1_()

void lmmp_powmod_1_ ( mp_ptr restrict dst,
mp_srcptr restrict bp,
mp_srcptr restrict ep,
mp_size_t en,
mp_limb_t mod )

在文件 powmod_1.c 第 68 行定义.

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}
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_debug_assert(x)
定义 lmmp.h:498
#define LMMP_MIN(l, o)
返回两个数中的较小值
定义 lmmp.h:450
#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
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
#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)

引用了 _udiv128by64to64_(), b2, count_bits(), ctz_shr_u64, getbit, getbits(), lmmp_binvert_ulong_(), lmmp_debug_assert, LMMP_MIN, lmmp_param_assert, lmmp_powmod_1_(), powmod1_redc_(), restrict, TALLOC_TYPE, TEMP_DECL , 以及 TEMP_FREE.

函数调用图:

◆ powmod1_redc_()

mp_limb_t powmod1_redc_ ( u128 t,
mp_limb_t m,
mp_limb_t ninv )
inlinestatic

在文件 powmod_1.c 第 57 行定义.

57 {
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}
#define k
#define t
uint32_t uint
定义 numth.h:38

引用了 k, powmod1_redc_() , 以及 t.

被这些函数引用 lmmp_powmod_1_() , 以及 powmod1_redc_().

函数调用图:
这是这个函数的调用关系图: