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

浏览该文件的源代码.

宏定义

#define MONT63_MAX   ((ulong)(0x7fffffffffffffff))
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static ulong from_mont63 (ulong x, ulong m, ulong m_inv)
static ulong from_mont64 (ulong x, ulong m, ulong m_inv)
uint lmmp_powmod_uint_odd_ (uint base, ulong exp, uint mod)
 计算 base^exp 对 mod 取模
ulong lmmp_powmod_ulong_odd_ (ulong base, ulong exp, ulong mod)
 计算 base^exp 对 mod 取模
static ulong mont63_mul (ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont63_R2 (ulong m)
static ulong mont63_reduce (u128 t, ulong m, ulong m_inv)
static ulong mont64_mul (ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont64_R2 (ulong m)
static ulong mont64_reduce (u128 t, ulong m, ulong m_inv)
static ulong mont_R2 (ulong m)
static ulong to_mont63 (ulong x, ulong R2, ulong m, ulong m_inv)
static ulong to_mont64 (ulong x, ulong R2, ulong m, ulong m_inv)

宏定义说明

◆ MONT63_MAX

#define MONT63_MAX   ((ulong)(0x7fffffffffffffff))

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_ulong.c 第 35 行定义.

函数说明

◆ from_mont63()

ulong from_mont63 ( ulong x,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 86 行定义.

86 {
87 return mont63_reduce(x, m, m_inv);
88}
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)

引用了 from_mont63() , 以及 mont63_reduce().

被这些函数引用 from_mont63() , 以及 lmmp_powmod_ulong_odd_().

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

◆ from_mont64()

ulong from_mont64 ( ulong x,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 62 行定义.

62 {
63 return mont64_reduce(x, m, m_inv);
64}
static ulong mont64_reduce(u128 t, ulong m, ulong m_inv)

引用了 from_mont64() , 以及 mont64_reduce().

被这些函数引用 from_mont64() , 以及 lmmp_powmod_ulong_odd_().

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

◆ lmmp_powmod_uint_odd_()

uint lmmp_powmod_uint_odd_ ( uint base,
ulong exp,
uint mod )

计算 base^exp 对 mod 取模

参数
base底数
exp指数
mod模数
警告
base<mod, mod>1, mod%2==1
返回
base^exp 对 mod 取模的结果

在文件 powmod_ulong.c 第 94 行定义.

94 {
95 lmmp_param_assert(mod > base);
96 lmmp_param_assert(mod % 2 == 1);
97 lmmp_param_assert(mod > 1);
98 ulong dst = 1;
99 ulong b = base;
100 _udiv64_t binv = _udiv64_gen(mod);
101 ulong q;
102 while (1) {
103 if (exp & 1) {
104 dst *= b;
105 q = _udiv64by64_q_preinv(dst, &binv);
106 dst -= q * mod;
107 }
108 exp >>= 1;
109 if (exp == 0)
110 break;
111 b *= b;
112 q = _udiv64by64_q_preinv(b, &binv);
113 b -= q * mod;
114 }
115 return dst;
116}
#define lmmp_param_assert(x)
定义 lmmp.h:509
static _udiv64_t _udiv64_gen(uint64_t d)
static uint64_t _udiv64by64_q_preinv(uint64_t numer, const _udiv64_t *denom)
uint64_t ulong
定义 numth.h:39

引用了 _udiv64_gen(), _udiv64by64_q_preinv(), lmmp_param_assert , 以及 lmmp_powmod_uint_odd_().

被这些函数引用 lmmp_mulmod_ulong_(), lmmp_powmod_uint_odd_(), lmmp_powmod_ulong_odd_() , 以及 TEST_CASE().

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

◆ lmmp_powmod_ulong_odd_()

ulong lmmp_powmod_ulong_odd_ ( ulong base,
ulong exp,
ulong mod )

计算 base^exp 对 mod 取模

参数
base底数
exp指数
mod模数
警告
base<mod, mod>1, mod%2==1
返回
base^exp 对 mod 取模的结果

在文件 powmod_ulong.c 第 118 行定义.

118 {
119 lmmp_param_assert(mod > base);
120 lmmp_param_assert(mod % 2 == 1);
121 lmmp_param_assert(mod > 1);
122 if (mod <= MP_UINT_MAX)
123 return lmmp_powmod_uint_odd_(base, exp, mod);
124 else if (mod <= MONT63_MAX) {
125 ulong R2 = mont63_R2(mod);
126 ulong m_inv = lmmp_binvert_ulong_(mod);
127 m_inv = -m_inv;
128 ulong dst = to_mont63(1, R2, mod, m_inv);
129 base = to_mont63(base, R2, mod, m_inv);
130 while (1) {
131 if (exp & 1)
132 dst = mont63_mul(dst, base, mod, m_inv);
133 exp >>= 1;
134 if (exp == 0)
135 break;
136 base = mont63_mul(base, base, mod, m_inv);
137 }
138 return from_mont63(dst, mod, m_inv);
139 } else {
140 ulong R2 = mont64_R2(mod);
141 ulong m_inv = lmmp_binvert_ulong_(mod);
142 m_inv = -m_inv;
143 ulong dst = to_mont64(1, R2, mod, m_inv);
144 base = to_mont64(base, R2, mod, m_inv);
145 while (1) {
146 if (exp & 1)
147 dst = mont64_mul(dst, base, mod, m_inv);
148 exp >>= 1;
149 if (exp == 0)
150 break;
151 base = mont64_mul(base, base, mod, m_inv);
152 }
153 return from_mont64(dst, mod, m_inv);
154 }
155}
static ulong mont64_R2(ulong m)
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
static ulong to_mont63(ulong x, ulong R2, ulong m, ulong m_inv)
static ulong mont63_R2(ulong m)
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv)
static ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv)
#define MP_UINT_MAX
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
static ulong from_mont64(ulong x, ulong m, ulong m_inv)
static ulong from_mont63(ulong x, ulong m, ulong m_inv)

引用了 from_mont63(), from_mont64(), lmmp_binvert_ulong_(), lmmp_param_assert, lmmp_powmod_uint_odd_(), lmmp_powmod_ulong_odd_(), MONT63_MAX, mont63_mul(), mont63_R2(), mont64_mul(), mont64_R2(), MP_UINT_MAX, to_mont63() , 以及 to_mont64().

被这些函数引用 lmmp_mulmod_ulong_(), lmmp_powmod_ulong_odd_() , 以及 TEST_CASE().

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

◆ mont63_mul()

ulong mont63_mul ( ulong a,
ulong b,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 90 行定义.

90 {
91 return mont63_reduce((u128)a * b, m, m_inv);
92}

引用了 mont63_mul() , 以及 mont63_reduce().

函数调用图:

◆ mont63_R2()

ulong mont63_R2 ( ulong m)
inlinestatic

在文件 powmod_ulong.c 第 78 行定义.

78 {
79 return mont_R2(m);
80}
static ulong mont_R2(ulong m)

引用了 mont63_R2() , 以及 mont_R2().

函数调用图:

◆ mont63_reduce()

ulong mont63_reduce ( u128 t,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 70 行定义.

70 {
71 // m < 2^63 时 k*m + t < 2^127,无 129 位溢出
72 ulong k = _u128low(t) * m_inv;
73 u128 sum = (u128)k * m + t;
74 ulong hi = _u128high(sum);
75 return hi >= m ? hi - m : hi;
76}
#define k
#define t

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

函数调用图:

◆ mont64_mul()

ulong mont64_mul ( ulong a,
ulong b,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 66 行定义.

66 {
67 return mont64_reduce((u128)a * b, m, m_inv);
68}

引用了 mont64_mul() , 以及 mont64_reduce().

函数调用图:

◆ mont64_R2()

ulong mont64_R2 ( ulong m)
inlinestatic

在文件 powmod_ulong.c 第 54 行定义.

54 {
55 return mont_R2(m);
56}

引用了 mont64_R2() , 以及 mont_R2().

函数调用图:

◆ mont64_reduce()

ulong mont64_reduce ( u128 t,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 37 行定义.

37 {
38 // sum = k*m + t < 2^129,第 129 位 c 由 128 位回绕捕获
39 ulong k = _u128low(t) * m_inv;
40 u128 km = (u128)k * m;
41 u128 sum = km + t;
42 uint c = sum < km;
43 ulong hi = _u128high(sum);
44 if (c) return hi - m; // 2^128 + hi - m 的低 128 位高位即结果
45 return hi >= m ? hi - m : hi;
46}
uint32_t uint
定义 numth.h:38

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

函数调用图:

◆ mont_R2()

ulong mont_R2 ( ulong m)
inlinestatic

在文件 powmod_ulong.c 第 48 行定义.

48 {
49 mp_bitcnt_t shift = 0;
50 clz_shl_u64(m, m, shift);
51 return _bpow_preinv_(m, shift, 2, lmmp_inv_1_(m));
52}
size_t mp_bitcnt_t
定义 lmmp.h:98
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
static uint64_t _bpow_preinv_(uint64_t m, uint64_t k, int nb, uint64_t inv)
#define clz_shl_u64(r, x, cnt)

引用了 _bpow_preinv_(), clz_shl_u64, lmmp_inv_1_() , 以及 mont_R2().

函数调用图:

◆ to_mont63()

ulong to_mont63 ( ulong x,
ulong R2,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 82 行定义.

82 {
83 return mont63_reduce((u128)x * R2, m, m_inv);
84}

引用了 mont63_reduce() , 以及 to_mont63().

函数调用图:

◆ to_mont64()

ulong to_mont64 ( ulong x,
ulong R2,
ulong m,
ulong m_inv )
inlinestatic

在文件 powmod_ulong.c 第 58 行定义.

58 {
59 return mont64_reduce((u128)x * R2, m, m_inv);
60}

引用了 mont64_reduce() , 以及 to_mont64().

函数调用图: