LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
/*
30
mont63 只能用于小于 2^63 的数,否则会溢出导致计算结果不正确
31
mont64 可以用于任意大小的数,但由于考虑了溢出的情况,所以速度理论上会慢一些(并未详细测试)
32
33
(本文件与 is_prime_ulong.c 各持一份同源拷贝,库内惯例勿强行收敛)
34
*/
35
#define MONT63_MAX ((ulong)(0x7fffffffffffffff))
36
37
static
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
48
static
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
54
static
inline
ulong
mont64_R2
(
ulong
m) {
55
return
mont_R2
(m);
56
}
57
58
static
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
62
static
inline
ulong
from_mont64
(
ulong
x,
ulong
m,
ulong
m_inv) {
63
return
mont64_reduce
(x, m, m_inv);
64
}
65
66
static
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
70
static
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
78
static
inline
ulong
mont63_R2
(
ulong
m) {
79
return
mont_R2
(m);
80
}
81
82
static
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
86
static
inline
ulong
from_mont63
(
ulong
x,
ulong
m,
ulong
m_inv) {
87
return
mont63_reduce
(x, m, m_inv);
88
}
89
90
static
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
94
uint
lmmp_powmod_uint_odd_
(
uint
base,
ulong
exp,
uint
mod) {
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
118
ulong
lmmp_powmod_ulong_odd_
(
ulong
base,
ulong
exp,
ulong
mod) {
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
}
k
#define k
inlines.h
mont63_reduce
static ulong mont63_reduce(u128 t, ulong m, ulong m_inv)
定义
is_prime_ulong.c:67
mont64_R2
static ulong mont64_R2(ulong m)
定义
is_prime_ulong.c:55
MONT63_MAX
#define MONT63_MAX
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
is_prime_ulong.c:36
to_mont63
static ulong to_mont63(ulong x, ulong R2, ulong m, ulong m_inv)
定义
is_prime_ulong.c:79
mont63_R2
static ulong mont63_R2(ulong m)
定义
is_prime_ulong.c:75
mont63_mul
static ulong mont63_mul(ulong a, ulong b, ulong m, ulong m_inv)
定义
is_prime_ulong.c:83
mont_R2
static ulong mont_R2(ulong m)
定义
is_prime_ulong.c:49
mont64_mul
static ulong mont64_mul(ulong a, ulong b, ulong m, ulong m_inv)
定义
is_prime_ulong.c:63
mont64_reduce
static ulong mont64_reduce(u128 t, ulong m, ulong m_inv)
定义
is_prime_ulong.c:38
to_mont64
static ulong to_mont64(ulong x, ulong R2, ulong m, ulong m_inv)
定义
is_prime_ulong.c:59
MP_UINT_MAX
#define MP_UINT_MAX
定义
mparam.h:28
mp_bitcnt_t
size_t mp_bitcnt_t
定义
lmmp.h:98
lmmp_param_assert
#define lmmp_param_assert(x)
定义
lmmp.h:509
lmmpn.h
lmmp_inv_1_
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义
inv.c:124
longlong.h
_bpow_preinv_
static uint64_t _bpow_preinv_(uint64_t m, uint64_t k, int nb, uint64_t inv)
定义
longlong.h:626
_udiv64_gen
static _udiv64_t _udiv64_gen(uint64_t d)
定义
longlong.h:734
_udiv64by64_q_preinv
static uint64_t _udiv64by64_q_preinv(uint64_t numer, const _udiv64_t *denom)
定义
longlong.h:740
clz_shl_u64
#define clz_shl_u64(r, x, cnt)
定义
longlong.h:69
_udiv64_t
定义
longlong.h:675
t
#define t
numth.h
lmmp_powmod_uint_odd_
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
定义
powmod_ulong.c:94
lmmp_binvert_ulong_
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
定义
binvert_1.c:49
uint
uint32_t uint
定义
numth.h:38
lmmp_powmod_ulong_odd_
ulong lmmp_powmod_ulong_odd_(ulong base, ulong exp, ulong mod)
计算 base^exp 对 mod 取模
定义
powmod_ulong.c:118
ulong
uint64_t ulong
定义
numth.h:39
from_mont64
static ulong from_mont64(ulong x, ulong m, ulong m_inv)
定义
powmod_ulong.c:62
from_mont63
static ulong from_mont63(ulong x, ulong m, ulong m_inv)
定义
powmod_ulong.c:86
src
lmmp
numth
powmod_ulong.c
生成于
, 为 LMMP使用
1.18.0