LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
powmod_ulong.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/inlines.h"
24#include "impl/longlong.h"
25#include "mparam.h"
26#include "lmmp/lmmpn.h"
27#include "lmmp/numth.h"
28
29/*
30mont63 只能用于小于 2^63 的数,否则会溢出导致计算结果不正确
31mont64 可以用于任意大小的数,但由于考虑了溢出的情况,所以速度理论上会慢一些(并未详细测试)
32
33(本文件与 is_prime_ulong.c 各持一份同源拷贝,库内惯例勿强行收敛)
34*/
35#define MONT63_MAX ((ulong)(0x7fffffffffffffff))
36
37static inline ulong mont64_reduce(u128 t, ulong m, ulong m_inv) {
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}
47
48static inline ulong mont_R2(ulong m) {
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}
53
54static inline ulong mont64_R2(ulong m) {
55 return mont_R2(m);
56}
57
58static inline ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv) {
59 return mont64_reduce((u128)x * R2, m, m_inv);
60}
61
62static inline ulong from_mont64(ulong x, ulong m, ulong m_inv) {
63 return mont64_reduce(x, m, m_inv);
64}
65
66static inline ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv) {
67 return mont64_reduce((u128)a * b, m, m_inv);
68}
69
70static inline ulong mont63_reduce(u128 t, ulong m, ulong m_inv) {
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}
77
78static inline ulong mont63_R2(ulong m) {
79 return mont_R2(m);
80}
81
82static inline ulong to_mont63(ulong x, ulong R2, ulong m, ulong m_inv) {
83 return mont63_reduce((u128)x * R2, m, m_inv);
84}
85
86static inline ulong from_mont63(ulong x, ulong m, ulong m_inv) {
87 return mont63_reduce(x, m, m_inv);
88}
89
90static inline ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv) {
91 return mont63_reduce((u128)a * b, m, m_inv);
92}
93
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}
117
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}
#define k
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)
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 mont_R2(ulong m)
static ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv)
static ulong mont64_reduce(u128 t, ulong m, ulong m_inv)
static ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv)
#define MP_UINT_MAX
size_t mp_bitcnt_t
定义 lmmp.h:98
#define lmmp_param_assert(x)
定义 lmmp.h:509
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)
static _udiv64_t _udiv64_gen(uint64_t d)
static uint64_t _udiv64by64_q_preinv(uint64_t numer, const _udiv64_t *denom)
#define clz_shl_u64(r, x, cnt)
#define t
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
uint32_t uint
定义 numth.h:38
ulong lmmp_powmod_ulong_odd_(ulong base, ulong exp, ulong mod)
计算 base^exp 对 mod 取模
uint64_t ulong
定义 numth.h:39
static ulong from_mont64(ulong x, ulong m, ulong m_inv)
static ulong from_mont63(ulong x, ulong m, ulong m_inv)