LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
numth.h
浏览该文件的文档.
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#ifndef LMMP_NUMTH_H
24#define LMMP_NUMTH_H
25
26#include <stdbool.h>
27
28#include "lmmp.h"
29
30#ifdef __cplusplus
31extern "C" {
32#endif // __cplusplus
33
34typedef uint8_t uchar;
35typedef int8_t schar;
36typedef uint16_t ushort;
37typedef int16_t sshort;
38typedef uint32_t uint;
39typedef uint64_t ulong;
40typedef int32_t sint;
41typedef int64_t slong;
42typedef uint8_t* ucharp;
43typedef int8_t* scharp;
44typedef uint16_t* ushortp;
45typedef int16_t* sshortp;
46typedef uint32_t* uintp;
47typedef int32_t* sintp;
48typedef uint64_t* ulongp;
49typedef int64_t* slongp;
50
51
52/**
53 * @brief 计算 a 在2^32下的逆元
54 * @param a 待求逆元
55 * @warning a%2==1
56 * @return 逆元
57 */
59
60/**
61 * @brief 计算 a 在2^64下的逆元
62 * @param a 待求逆元
63 * @warning a%2==1
64 * @return 逆元
65 */
67
68/**
69 * @brief 计算 [numa,2] 在 B^2 下的逆元
70 * @param numa 待求逆元指针(长度为 2 个limb)
71 * @param dst 结果指针(长度为 2 个limb)
72 * @warning numa!=NULL, dst!=NULL, numa[0]%2==1, eqsep(dst,numa)
73 */
75
76/**
77 * @brief 计算 [numa,3] 在 B^3 下的逆元
78 * @param numa 待求逆元指针(长度为 3 个limb)
79 * @param dst 结果指针(长度为 3 个limb)
80 * @warning numa!=NULL, dst!=NULL, numa[0]%2==1, sep(dst,numa)
81 */
83
84/**
85 * @brief 计算 [numa,4] 在 B^4 下的逆元
86 * @param numa 待求逆元指针(长度为 4 个limb)
87 * @param dst 结果指针(长度为 4 个limb)
88 * @warning numa!=NULL, dst!=NULL, numa[0]%2==1, sep(dst,numa)
89 */
91
92/**
93 * @brief 计算 [numa,n] 在 B^n 下的逆元
94 * @param numa 待求逆元指针(长度为 n 个limb)
95 * @param dst 结果指针(长度为 n 个limb)
96 * @param n 结果的 limb 长度
97 * @param tp 临时工作区指针(长度为 5*(n+1)/2 个limb)
98 * @warning numa!=NULL, dst!=NULL, numa[0]%2==1, sep(dst,numa,tp)
99 */
101
102/**
103 * @brief 计算 a 在 B^n 下的逆元
104 * @param dst 结果指针(长度为 n 个limb)
105 * @param a 待求逆元
106 * @param n 结果的 limb 长度
107 * @warning a%2==1, n>1, dst!=NULL
108 */
110
111/**
112 * @brief 计算 [numa,2] 在 B^n 下的逆元
113 * @param dst 结果指针(长度为 n 个limb)
114 * @param numa 待求逆元指针(长度为 2 个limb)
115 * @param n 结果的 limb 长度
116 * @warning numa[0]%2==1, n>2, dst!=NULL, numa!=NULL, sep(dst,numa)
117 */
119
120/**
121 * @brief 计算 [numa,na] 在 B^n 下的逆元
122 * @param dst 结果指针(长度为 n 个limb)
123 * @param numa 待求逆元指针(长度为 na 个limb)
124 * @param na 待求逆元的 limb 长度
125 * @param n 结果的 limb 长度
126 * @param tp 临时工作区指针(长度为 (9*na+5)/2 个limb)
127 * @warning numa[0]%2==1, n>na, dst!=NULL, numa!=NULL, tp!=NULL, sep(dst,numa,tp)
128 */
130
131/**
132 * @brief 计算 [numa,na] 在 B^n 下的逆元
133 * @param dst 结果指针(长度为 n 个limb)
134 * @param numa 待求逆元指针(长度为 na 个limb)
135 * @param na 待求逆元的 limb 长度
136 * @param n 结果的 limb 长度
137 * @warning n>=na>0, numa!=NULL, dst!=NULL, numa[0]%2==1, sep(dst,numa)
138 */
140
141/**
142 * @brief 精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
143 * @param dst 结果指针(长度为 nn 个limb)
144 * @param np 被除数指针(长度为 nn 个limb)
145 * @param nn 被除数的 limb 长度
146 * @param d 除数
147 * @param dinv 除数的逆元(d*dinv==1 mod 2^64)
148 * @warning d%2==1, d*dinv==1 mod 2^64, nn>0, dst!=NULL, np!=NULL, eqsep(dst,np)
149 */
151
152/**
153 * @brief 精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
154 * @param dst 结果指针(长度为 nn-1 个limb)
155 * @param np 被除数指针(长度为 nn 个limb)
156 * @param nn 被除数的 limb 长度
157 * @param dp 除数指针(长度为 2 个limb)
158 * @param dinv 除数的逆元指针(长度为 2 个limb)
159 * @warning dp[0]%2==1, dp*dinv==1 mod 2^128, nn>1, dst!=NULL, np!=NULL, dp!=NULL, dinv!=NULL
160 * eqsep(dst,np), sep(dp,dinv,[dst|np])
161 */
163
164/**
165 * @brief 精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
166 * @param dst 结果指针(长度为 nn-dn+1 个limb)
167 * @param np 被除数指针(长度为 nn 个limb),将会被修改为全零
168 * @param nn 被除数的 limb 长度
169 * @param dp 除数指针(长度为 dn 个limb)
170 * @param dn 结除数的 limb 长度
171 * @param dinv 除数[dp,dn]关于B^dn的逆元,若为NULL,则自动计算
172 * @warning dp[0]%2==1, nn>=dn>0, dst!=NULL, np!=NULL, dp!=NULL, eqsep(dst,np), sep(dp,dinv,[dst|np])
173 * @note 若dst==np,只会覆写 [dst,nn-dn+1] 区域
174 */
176
177/**
178 * @brief 精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
179 * @param dst 结果指针(长度为 nn-dn+1 个limb)
180 * @param np 被除数指针(长度为 nn 个limb),将会被覆写为全零
181 * @param nn 被除数的 limb 长度
182 * @param dp 除数指针(长度为 dn 个limb)
183 * @param dn 除数的 limb 长度
184 * @warning dp[0]%2==1, nn>=dn>0, dst!=NULL, np!=NULL, dp!=NULL, eqsep(dst,np), sep(dp,[dst|np])
185 * @note 若dst==np,将会覆写 [dst,nn] 区域,其中 [dst,nn-dn+1] 为商,[dst+nn-dn+1,dn-1] 将会被覆写为0
186 */
188
189/**
190 * @brief 精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
191 * @param dst 结果指针(长度为 nn-dn+1 个limb)
192 * @param np 被除数指针(长度为 nn 个limb)
193 * @param nn 被除数的 limb 长度
194 * @param dp 除数指针(长度为 dn 个limb)
195 * @param dn 结除数的 limb 长度
196 * @warning dp[0]%2==1, nn>=dn>0, dn>=nn-dn+1, dst!=NULL, np!=NULL, dp!=NULL, sep(dst,np,dp)
197 */
199
200/**
201 * @brief 精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
202 * @param dst 结果指针(长度为 nn-dn+1 个limb)
203 * @param np 被除数指针(长度为 nn 个limb)
204 * @param nn 被除数的 limb 长度
205 * @param dp 除数指针(长度为 dn 个limb)
206 * @param dn 结除数的 limb 长度
207 * @warning dp[0]%2==1, nn>=dn>0, dst!=NULL, np!=NULL, dp!=NULL, eqsep(dst,np), sep([dst|np],dp)
208 */
210
211/**
212 * @brief 计算两个无符号整数的最大公约数
213 * @param u 第一个无符号整数
214 * @param v 第二个无符号整数
215 * @return 最大公约数
216 * @warning u!=0, v!=0
217 */
219
220/**
221 * @brief 计算两个无符号整数的最大公约数
222 * @param up 第一个无符号整数指针
223 * @param un 第一个无符号整数的 limb 长度
224 * @param v 第二个无符号整数
225 * @warning v!=0, up!=NULL, un>0
226 * @return 最大公约数
227 */
229
230/**
231 * @brief 计算两个无符号整数的最大公约数
232 * @param up 第一个无符号整数指针,长度为 2
233 * @param vp 第二个无符号整数指针,长度为 2
234 * @param dst 结果指针(长度为 2,两个 limb 都会进行写入,即使最高位可能为0)
235 * @warning up!=NULL, vp!=NULL, [up,2]!=0, [vp,2]!=0, dst!=NULL, eqsep(dst,[up|vp])
236 * @note up 和 vp 的高位允许为 0,但要求任一个数的高低位不能全为 0
237 * @return dst 的实际 limb 长度
238 */
240
241/**
242 * @brief 计算两个无符号整数的最大公约数
243 * @param up 第一个无符号整数指针
244 * @param un 第一个无符号整数的 limb 长度
245 * @param vp 第二个无符号整数指针,长度为 2
246 * @param dst 结果指针(长度至少为 2,两个 limb 都会进行写入,即使最高位可能为0)
247 * @warning up!=NULL, un>2, vp!=NULL, vp[1]!=0, dst!=NULL, eqsep(dst,[up|vp])
248 * @return dst 的实际 limb 长度
249 */
251
252/**
253 * @brief 计算两个无符号整数的最大公约数(Lehmer算法)
254 * @param dst 结果指针(长度至少为 min(un,vn))
255 * @param up 第一个无符号整数指针
256 * @param un 第一个无符号整数的 limb 长度
257 * @param vp 第二个无符号整数指针
258 * @param vn 第二个无符号整数的 limb 长度
259 * @warning up!=NULL, un>0, vp!=NULL, vn>0, eqsep(dst,[up|vp]), dst!=NULL, up[un-1]!=0, vp[vn-1]!=0
260 * @return dst 的实际 limb 长度
261 */
263
264/**
265 * @brief hgcd 变换矩阵
266 * @note / a \ / m00 m01 \ / a' \
267 * | | = | | * | |
268 * \ b / \ m10 m11 / \ b' /
269 * 其中 (a;b) 为 hgcd 入口数对,(a';b') 为归约后数对。矩阵元素均非负,
270 * det(M) = ±1,元素值不超过入口较大分量的规模。
271 * 每个元素显式存储真实长度 n[i][j](归一化,顶 limb 非零;
272 * n[i][j]==0 表示零元素),不做零填充:元素缓冲 [0, n[i][j]) 之外
273 * 的内容无效,一切访问以长度为准。长度由库内计算过程显式维护
274 * (乘法进位/最高位),不做前导零扫描。
275 * 各元素长度 <= alloc。
276 */
277typedef struct {
278 mp_ptr m[2][2]; /* 元素指针,各指向 alloc limbs 的连续区域 */
279 mp_size_t n[2][2]; /* 各元素真实长度(归一化;0 表示零元素) */
280 mp_size_t alloc; /* 每元素容量(limb) */
282
283/**
284 * @brief 初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
285 * @param M 变换矩阵
286 * @param alloc 每元素容量(limb)。若随后用于 n limb 数对的 hgcd,需 alloc >= n+2
287 * @warning M!=NULL, alloc>0
288 * @note 使用完毕须调用 lmmp_hgcd_matrix_free_ 释放
289 */
291
292/**
293 * @brief 释放 hgcd 变换矩阵的元素缓冲
294 * @param M 变换矩阵
295 * @warning M!=NULL, M 须由 lmmp_hgcd_matrix_init_ 初始化且未被释放
296 */
298
299/**
300 * @brief 半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
301 * @param M 变换矩阵(入口应为单位矩阵,出口满足 (a;b) = M*(a';b'))
302 * @param ap 较大分量输入兼输出数组(长度为 n 个limb,出口保证较大者位于 ap)
303 * @param bp 较小分量输入兼输出数组(长度为 n 个limb,允许高位零填充)
304 * @param n ap,bp 的公共长度
305 * @warning M!=NULL, ap!=NULL, bp!=NULL, sep(ap,bp), n>0, M->alloc>=n+2,
306 * ap[n-1]!=0(a 须归一化;bp 非全零,允许高位零填充),[ap,n]>[bp,n](值序)
307 * @return 归约后公共长度(成功时一般 <= n/2+2;若归约中遇到整除完成态会提前返回,
308 * 此时 [bp,*] 可能已为 0,由调用者检查);0 表示未做任何归约(M 保持单位矩阵)
309 * @note gcd(a,b) = gcd(a',b')。渐进复杂度 O(M(n) log n),M 为乘法复杂度。
310 * 长输入下经由 lmmp_gcd_hgcd_ 使用;直接调用时注意 ap/bp 需要各自 n limbs 容量。
311 */
313
314/**
315 * @brief 计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
316 * @param dst 结果指针(长度至少为 bn)
317 * @param up 第一个无符号整数数组(长度为 un 个limb)
318 * @param un 第一个无符号整数的 limb 长度
319 * @param vp 第二个无符号整数数组(长度为 vn 个limb)
320 * @param vn 第二个无符号整数的 limb 长度
321 * @warning up!=NULL, un>=vn>0, vp!=NULL, dst!=NULL, eqsep(dst,[up|vp]), up[un-1]!=0, vp[vn-1]!=0
322 * @return dst 的实际 limb 长度
323 * @note 不平衡输入(un >= 2*vn)先做取模预归约将两数长度拉近,再进入
324 * 分治主路径:不平衡时 hgcd 的阶段 A 递归失效,预归约普遍更快
325 * (越悬殊收益越大,见 hgcd.c 实现注)
326 */
328
329/**
330 * @brief 计算两个无符号整数的最大公约数(通用分发入口)
331 * @param dst 结果指针(长度至少为 min(un,vn))
332 * @param up 第一个无符号整数指针
333 * @param un 第一个无符号整数的 limb 长度
334 * @param vp 第二个无符号整数指针
335 * @param vn 第二个无符号整数的 limb 长度
336 * @warning up!=NULL, un>0, vp!=NULL, vn>0, eqsep(dst,[up|vp]), dst!=NULL, up[un-1]!=0, vp[vn-1]!=0
337 * @return dst 的实际 limb 长度
338 */
340
341/**
342 * @brief 扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
343 * @param u 第一个无符号整数
344 * @param v 第二个无符号整数
345 * @param s 输出 u 的贝祖系数(带符号)
346 * @param t 输出 v 的贝祖系数(带符号,可为 NULL 表示不需要)
347 * @warning u!=0, v!=0, s!=NULL
348 * @return 最大公约数 g
349 * @note 取极小系数:|s| <= v/(2g)、|t| <= u/(2g)(由此唯一)。v|u 时 s=0、t=1
350 */
352
353/**
354 * @brief 扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g
355 * @param dstg 结果指针(长度为 1 个limb)
356 * @param dsts u 的贝祖系数幅度(长度为 1 个limb,s==0 时写 0)
357 * @param sn 输出 s 的带符号 limb 长度([1|-1|0])
358 * @param dstt v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL 表示不需要)
359 * @param tn 输出 t 的带符号 limb 长度(dstt==NULL 时忽略,可为 NULL)
360 * @param up 第一个无符号整数指针
361 * @param un 第一个无符号整数的 limb 长度
362 * @param v 第二个无符号整数(单 limb)
363 * @warning up!=NULL, un>0, v!=0, dstg!=NULL, dsts!=NULL, sn!=NULL, sep([dsts|dstt],dstg)
364 * @return g 的 limb 长度(恒 1)
365 * @note 取极小系数 |s| <= v/(2g)(单 limb)、|t| <= u/(2g)。v|[up,un] 时 s=0、t=1。
366 * dstg 允许与 up 别名(eqsep);dsts/dstt 在 up 的所有读取完成后才写入
367 */
369 mp_srcptr up, mp_size_t un, ulong v);
370
371/**
372 * @brief 扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
373 * @param dstg 结果指针(长度至少为 2 个limb)
374 * @param dsts u 的贝祖系数幅度(长度至少为 2 个limb,s==0 时写 0)
375 * @param sn 输出 s 的带符号 limb 长度
376 * @param dstt v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL)
377 * @param tn 输出 t 的带符号 limb 长度(dstt==NULL 时忽略)
378 * @param up 第一个无符号整数指针
379 * @param un 第一个无符号整数的 limb 长度
380 * @param vp 第二个无符号整数指针(长度为 2)
381 * @warning up!=NULL, un>2, vp!=NULL, vp[1]!=0, dstg!=NULL, dsts!=NULL, sn!=NULL,
382 * sep([dsts|dstt],dstg)
383 * @return g 的实际 limb 长度
384 * @note 取极小系数(同 lmmp_gcdext_11_ 注)。经 lmmp_mod_2_ 预归约后转
385 * lmmp_gcdext_lehmer_(无独立 2x2 核)。dstg 允许与 [up|vp] 别名
386 */
388 mp_srcptr up, mp_size_t un, mp_srcptr vp);
389
390/**
391 * @brief 扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g
392 * @param dstg 结果指针(长度至少为 min(un,vn))
393 * @param dsts u 的贝祖系数幅度(长度至少为 vn 个limb,s==0 时写 0)
394 * @param sn 输出 s 的带符号 limb 长度([1|-1|0])
395 * @param dstt v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL 表示不需要)
396 * @param tn 输出 t 的带符号 limb 长度(dstt==NULL 时忽略,可为 NULL)
397 * @param up 第一个无符号整数指针
398 * @param un 第一个无符号整数的 limb 长度
399 * @param vp 第二个无符号整数指针
400 * @param vn 第二个无符号整数的 limb 长度
401 * @warning up!=NULL, un>0, vp!=NULL, vn>0, dstg!=NULL, dsts!=NULL, sn!=NULL,
402 * up[un-1]!=0, vp[vn-1]!=0, sep([dsts|dstt],dstg)
403 * @return g 的实际 limb 长度
404 * @note 取极小系数(同 lmmp_gcdext_11_ 注)。un/vn 任意大小关系(内部值序
405 * 归一化,系数按原参数序输出)。归约骨架与 gcd_lehmer.c 同构,共因子
406 * 走单行跟踪(GMP 行向量思想):全程保持 V = u0*a + u1*b(行元素非负,
407 * a;b 为当前数对),t 在输出相位经恒等式导出(dstt==NULL 时跳过)。
408 * dstg 允许与 [up|vp] 别名(eqsep);dsts/dstt 在 up/vp 的所有读取
409 * 完成后才写入
410 */
412 mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn);
413
414/**
415 * @brief 扩展欧几里得(hgcd 分治,长输入优选):g = gcd(u,v),s*u + t*v = g
416 * @param dstg 结果指针(长度至少为 min(un,vn))
417 * @param dsts u 的贝祖系数幅度(长度至少为 vn 个limb,s==0 时写 0)
418 * @param sn 输出 s 的带符号 limb 长度([1|-1|0])
419 * @param dstt v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL)
420 * @param tn 输出 t 的带符号 limb 长度(dstt==NULL 时忽略)
421 * @param up 第一个无符号整数指针
422 * @param un 第一个无符号整数的 limb 长度
423 * @param vp 第二个无符号整数指针
424 * @param vn 第二个无符号整数的 limb 长度
425 * @warning up!=NULL, un>0, vp!=NULL, vn>0, dstg!=NULL, dsts!=NULL, sn!=NULL,
426 * up[un-1]!=0, vp[vn-1]!=0, sep([dsts|dstt],dstg)
427 * @return g 的实际 limb 长度
428 * @note 取极小系数(同 lmmp_gcdext_11_ 注)。un/vn 任意大小关系(内部值序
429 * 归一化,系数按原参数序输出)。GMP mpn_gcdext 结构:初始一次取模
430 * (商丢弃,共因子无损),主循环对高位片调库内 hgcd 核 + 低位修补,
431 * 单行 (u0,u1) 共因子跟踪(V = u0*a + u1*b,每轮 4 次行乘),降至
432 * 阈值下转 lmmp_gcdext_lehmer_;t 在输出相位经恒等式导出。
433 * dstg 允许与 [up|vp] 别名(eqsep)
434 */
436 mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn);
437
438/**
439 * @brief 扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g
440 * @param dstg 结果指针(长度至少为 min(un,vn))
441 * @param dsts u 的贝祖系数幅度(长度至少为 vn 个limb)
442 * @param sn 输出 s 的带符号 limb 长度
443 * @param dstt v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL)
444 * @param tn 输出 t 的带符号 limb 长度(dstt==NULL 时忽略)
445 * @param up 第一个无符号整数指针
446 * @param un 第一个无符号整数的 limb 长度
447 * @param vp 第二个无符号整数指针
448 * @param vn 第二个无符号整数的 limb 长度
449 * @warning up!=NULL, un>0, vp!=NULL, vn>0, dstg!=NULL, dsts!=NULL, sn!=NULL,
450 * up[un-1]!=0, vp[vn-1]!=0, sep([dsts|dstt],dstg)
451 * @return g 的实际 limb 长度
452 * @note vn==1 转 lmmp_gcdext_1_、vn==2(un>2)转 lmmp_gcdext_2_,两侧均
453 * 超过 GCD_HGCD_THRESHOLD 转 lmmp_gcdext_hgcd_(分治),否则
454 * lmmp_gcdext_lehmer_。dstg 允许与 [up|vp] 别名
455 */
457 mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn);
458
459/**
460 * @brief 模逆元(单 limb):求 u^{-1} mod m
461 * @param u 被求逆元数
462 * @param m 模数
463 * @warning u!=0, m!=0
464 * @return 逆元(落在 [0,m));m>1 且 gcd(u,m)>1(不存在)时返回 0;m==1 时返回 0(模 1 下逆元为 0)
465 */
467
468/**
469 * @brief 模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
470 * @param dst 结果指针(长度至少为 mn 个limb)
471 * @param up 被求逆元数指针
472 * @param un 被求逆元数的 limb 长度
473 * @param mp 模数指针
474 * @param mn 模数的 limb 长度
475 * @warning up!=NULL, un>0, mp!=NULL, mn>0, dst!=NULL, up[un-1]!=0, mp[mn-1]!=0,
476 * sep(dst,[up|mp])
477 * @return dst 的实际 limb 长度;0 表示逆元不存在(gcd(u,m)>1)
478 * @note 结果落在 [0,m)。mn==1 时约化为标量路径。dst 允许与 up 别名(eqsep)
479 */
481
482/**
483 * @brief 计算两个无符号整数的乘积,对mod取模,商放入 q 中
484 * @param a 第一个无符号整数
485 * @param b 第二个无符号整数
486 * @param q 商的结果指针
487 * @param mod 取模数
488 * @warning a < mod, b < mod, q!=NULL
489 * @return 余数
490 */
492
493/**
494 * @brief 计算 base^exp 对 mod 取模
495 * @param base 底数
496 * @param exp 指数
497 * @param mod 模数
498 * @warning base<mod, mod>1, mod%2==1
499 * @return base^exp 对 mod 取模的结果
500 */
502
503/**
504 * @brief 计算 base^exp 对 mod 取模
505 * @param base 底数
506 * @param exp 指数
507 * @param mod 模数
508 * @warning base<mod, mod>1, mod%2==1
509 * @return base^exp 对 mod 取模的结果
510 */
512
513/**
514 * @brief 计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
515 * @param dst 结果指针(长度为 n 个limb)
516 * @param bp 底数指针
517 * @param n 底数的 limb 长度
518 * @param ep 指数指针
519 * @param en 指数的 limb 长度
520 * @warning dst!=NULL, bp!=NULL, ep!=NULL, en>0, n>0, ep[en-1]>0, sep(dst,[bp|ep])
521 */
523
524/**
525 * @brief 计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)
526 * @param dst 结果指针(长度为 1 个limb)
527 * @param bp 底数指针(长度为 1 个limb)
528 * @param ep 指数指针
529 * @param en 指数的 limb 长度
530 * @warning dst!=NULL, bp!=NULL, ep!=NULL, en>0, ep[en-1]>0, sep(dst,[bp|ep])
531 * @note 指数为 1 时直接截断取 [bp,1];单 limb 乘法 mod B 即自然回绕,
532 * 全程无归约开销
533 */
535
536/**
537 * @brief 计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
538 * @param dst 结果指针(长度为 2 个limb)
539 * @param bp 底数指针(长度为 2 个limb)
540 * @param ep 指数指针
541 * @param en 指数的 limb 长度
542 * @warning dst!=NULL, bp!=NULL, ep!=NULL, en>0, ep[en-1]>0, sep(dst,[bp|ep])
543 * @note 指数为 1 时直接截断取 [bp,2];乘法与平方均走 longlong.h 的
544 * 128 位低位积内联(_umul128to128_),全程无归约开销
545 */
547
548/**
549 * @brief Montgomery 归约(REDC):计算 ([tp,2n] + q*[mp,n]) / B^n,其中
550 * q = [tp,n] * [ninv,n] mod B^n,即结果为 [tp,2n] * B^(-n) % [mp,n]
551 * @param dst 结果指针(长度为 n 个limb)
552 * @param tp 被归约数指针(长度为 2n 个limb)
553 * @param ninv -[mp,n]^(-1) mod B^n(长度为 n 个limb)
554 * @param mp 模数指针(长度为 n 个limb)
555 * @param n 模数的 limb 长度
556 * @warning dst!=NULL, tp!=NULL, ninv!=NULL, mp!=NULL, n>0, mp[0]%2==1, mp[n-1]>0,
557 * [ninv,n] == -[mp,n]^(-1) mod B^n, sep(dst,[tp|ninv|mp]), [tp,2n] < B^n*[mp,n]
558 * @return 结果最高位(第 n+1 limb 的值,[0|1]),返回值:[dst,n] 即归约结果,且结果 < 2*[mp,n]
559 * @note 典型用法(蒙域乘法):a_m = a*B^n mod m 与 b_m = b*B^n mod m(均 < m)的
560 * 全积 [tp,2n] = a_m*b_m 经本函数得 (a*b)*B^n mod m(仍在蒙域),随后若
561 * 结果 >= m 再减一次 m 即得 < m 的规范蒙域剩余。
562 * 注意:对普通整数 a、b 的全积直接调用得到的是 a*b*B^(-n) mod m(带
563 * Montgomery 缩放因子,条件减法不能将其消去),并非 a*b mod m;如需单次
564 * REDC 完成普通模乘,一操作数取普通域、另一取蒙域:REDC(a*b_m) = a*b mod m
565 */
567
568/**
569 * @brief 计算奇模数模幂 [dst,1] = [bp,1]^[ep,en] % mod
570 * @param dst 结果指针(长度为 1 个limb)
571 * @param bp 底数指针(长度为 1 个limb)
572 * @param ep 指数指针
573 * @param en 指数的 limb 长度
574 * @param mod 模数
575 * @warning dst!=NULL, bp!=NULL, ep!=NULL, en>0, ep[en-1]>0, mod%2==1, mod>1, [bp,1]<mod
576 */
578
579/**
580 * @brief 计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2]
581 * @param dst 结果指针(长度为 2 个limb)
582 * @param bp 底数指针(长度为 2 个limb)
583 * @param ep 指数指针
584 * @param en 指数的 limb 长度
585 * @param mod 模数指针(长度为 2 个limb)
586 * @warning dst!=NULL, bp!=NULL, ep!=NULL, mod!=NULL, en>0, ep[en-1]>0, mod[0]%2==1,
587 * mod[1]!=0, [mod,2]>1, [bp,2]<[mod,2]
588 */
590
591/**
592 * @brief 计算奇模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
593 * @param dst 结果指针(长度为 n 个limb,规范剩余 < [mp,n],高位可能为 0)
594 * @param bp 底数指针(长度为 n 个limb)
595 * @param ep 指数指针
596 * @param en 指数的 limb 长度
597 * @param mp 模数指针(长度为 n 个limb)
598 * @param n 模数的 limb 长度
599 * @warning dst!=NULL, bp!=NULL, ep!=NULL, mp!=NULL, en>0, ep[en-1]>0, n>0,
600 * mp[0]%2==1, mp[n-1]>0, [mp,n]>1, [bp,n]<[mp,n], sep(dst,[bp|ep|mp])
601 */
603
604/**
605 * @brief 计算任意模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
606 * @param dst 结果指针(长度为 n 个limb,规范剩余 < [mp,n],高位可能为 0)
607 * @param bp 底数指针(长度为 n 个limb)
608 * @param ep 指数指针
609 * @param en 指数的 limb 长度
610 * @param mp 模数指针(长度为 n 个limb,奇偶皆可)
611 * @param n 模数的 limb 长度
612 * @warning dst!=NULL, bp!=NULL, ep!=NULL, mp!=NULL, en>0, ep[en-1]>0, n>0,
613 * mp[n-1]>0, [mp,n]>1, [bp,n]<[mp,n], sep(dst,[bp|ep|mp])
614 */
616
617/**
618 * @brief 大于n的下一个素数
619 * @param n 起始点(不含)
620 * @warning 如果 n 大于等于ulong可表示最大的质数,则返回ulong_max
621 * @return 大于n的下一个素数
622 */
624
625/**
626 * @brief 小于等于n的上一个素数
627 * @param n 起始点(含)
628 * @warning 如果 n 小于2,则返回 0
629 * @return 小于等于n的上一个素数,如果n恰好为素数,则返回 n
630 */
632
633/**
634 * @brief 判断素数
635 * @param n 待判断的数
636 * @return 若 n 为素数,返回 true,否则返回 false
637 */
639
640/**
641 * @brief 判断素数
642 * @param n 待判断的数
643 * @return 若 n 为素数,返回 true,否则返回 false
644 */
646
647/**
648 * @brief 判断素数(无试除法,单 limb 档)
649 * @param n 待判断的数(建议为极有可能为素数的数)
650 * @note 不进行试除法过滤,适用于判断已被小素数试除法过滤的数或强伪素数
651 * @warning n>2
652 * @return 若 n 为素数,返回 true,否则返回 false
653 */
655
656/**
657 * @brief 判断 128 位素数
658 * @param lo 待判断数的低 64 位
659 * @param hi 待判断数的高 64 位
660 * @warning hi>0
661 * @note 在 lmmp_is_prime_2_notrial_ 前进行小素数试除。适合随机输入或一般情况。
662 * @return 0 = 合数;1 = 素数(确定性判据);2 = 极可能是素数(强 BPSW 型非确定性判据)
663 */
665
666/**
667 * @brief 判断 128 位素数(无试除法)
668 * @param lo 待判断数的低 64 位
669 * @param hi 待判断数的高 64 位
670 * @warning hi>0, lo%2==1
671 * @note 不进行试除法,对于含有明显小因子的输入不会早退。建议输入
672 * 不含小因子或强伪素数、半素数等。
673 * B <= n < SWbound = 3317044064679887385961981(约
674 * 2^81.5)时为确定性判据(前 13 个素数基底的 Rabin-Miller,
675 * Sorenson-Webster),返回 1;更大时为 BPSW 型判据(基底 2 强伪素数
676 * 测试叠加强 Lucas-Selfridge 测试的 V 阶梯实现,Lucas 参数含 A*
677 * 脆弱区绕行((5|n)=-1 时 Q 取 1/5 的归一化形),另含 BFW vpsp 与
678 * Q-Euler 两项强化检查,素数必然全过),学界无已知反例,返回 2。
679 * @return 0 = 合数;1 = 素数(确定性判据);2 = 极可能是素数(强 BPSW 型非确定性判据)
680 */
682
683/**
684 * @brief 强 Lucas-Selfridge 测试(大于 128 位)
685 * @param np 待测奇数指针(nn 个limb)
686 * @param nn 待测数的 limb 长度
687 * @warning np!=NULL, nn>2, np[nn-1]>0, np[0]%2==1
688 * @note Selfridge 方法 A:P=1,Q=(1-D)/4,D 取 5,-7,9,-11,... 中首个
689 * (D|n)=-1 者;V-only 阶梯实现,判据与标准 U/V 强 Lucas 测试精确一致
690 * (U_d=0 经 P=1 恒等式 D*U_d = 2V_{d+1} - V_d 以 2V_{d+1}=V_d 检出),
691 * 判据命中后叠加 BFW vpsp(V_{n+1}=2Q)与 Q-Euler(Q^{(n+1)/2}=+-Q)
692 * 两项强化检查(Baillie-Fiori-Wagstaff 2021,素数必然全过)。
693 * 判定合数的情形含 gcd(|D|,n)>1 与 n 为完全平方数。
694 * 单轮成本约为单轮 MR 的 1.6~2 倍
695 * @return 1 = 通过强 Lucas 测试;0 = 合数
696 */
698
699/**
700 * @brief 大整数素性检验(强度分档,大于 128 位)
701 * @param np 待测数指针(nn 个limb)
702 * @param nn 待测数的 limb 长度
703 * @param strength 检测强度 [0,7],语义同 lmmp_is_prime_n_notrial_,强度越高理论误判率越低。
704 * 强度>=4时,已是接受集为标准 BPSW 素性(学界目前无已知反例)接受集的子集。
705 * @warning np!=NULL, nn>2, np[nn-1]>0, 0<=strength<=7
706 * @note 在 lmmp_is_prime_n_notrial_ 前进行小素数试除,适合随机输入或者一般情况。
707 * 建议使用强度 5 档,能够很好的平衡伪素数和素数的平均耗时。素性强度可以参照
708 * lmmp_is_prime_n_notrial_中的说明。
709 * @return 0 = 合数;1 = 素数(确定性判据,本契约域不可达);
710 * 2 = 极大概率为素数
711 */
712LMMP_API int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength);
713
714/**
715 * @brief 大整数素性检验(无试除法,强度分档,大于 128 位)
716 * @param np 待测数指针(nn 个limb)
717 * @param nn 待测数的 limb 长度
718 * @param strength 检测强度 [0,7]。随机基底 MR 分两层:"1+n" 搭配指先跑至多
719 * x 轮 1 limb 随机基底(a in [3,B) 均匀,廉价,可尽早拒判)再跑至多 y 轮
720 * 全域(n limb 随机基底,[2,n-2] 均匀)基底。各层均为“至多”轮数,任一轮检出
721 * 合数即提前终止:
722 * | 强度| 基底2 MR | 1 limb 基底 MR | n limb 基底 MR | 强 Lucas |
723 * | --- | ------- | -------------- | -------------- | -------- |
724 * | 0 | √ | 3 | 2 | - |
725 * | 1 | √ | 4 | 3 | - |
726 * | 2 | √ | 5 | 4 | - |
727 * | 3 | √ | 6 | 5 | - |
728 * | 4 | √ | 0 | 0 | √ |
729 * | 5 | √ | 2 | 0 | √ |
730 * | 6 | √ | 3 | 1 | √ |
731 * | 7 | √ | 4 | 2 | √ |
732 * @warning np!=NULL, nn>2, np[nn-1]>0, np[0]%2==1, 0<=strength<=7
733 * @note 1. 不进行试除法,对于含有明显小因子的输入不会早退。建议输入不含小因子或强伪素数、半素数等。
734 * 2. 建议实际使用强度 5 档,能够很好的平衡伪素数和素数的平均耗时,对于真素数不会耗费过长的时间,
735 * 且可以更快的过滤伪素数。该档为 BPSW 型判据(基底 2 MR 叠加强 Lucas)之上增加 2 轮
736 * 1 limb 随机基底 MR;其中 Lucas 半部含 BFW vpsp 与 Q-Euler 两项强化检查
737 * (Baillie-Fiori-Wagstaff 2021,素数必然全过),故接受集为标准 BPSW 接受集的子集
738 * (合数只可能多拒、不可能少拒)。
739 * 3. 强卢卡斯判据本身和 MR 测量相当正交,因此强度档大于4时,增加更多轮次 MR 测试存在边际效应,
740 * 并不能无条件的降低 BPSW 条件下的实际误判率。更多的 MR 轮次,只承担早退的任务,对于部分
741 * 伪素数可以更早的返回,而不是进行卢卡斯检验。但对于可能通过的(伪)素数,总时间反而增加。
742 * @attention 1 limb 基底空间仅 2^64,可能存在精心构造的伪素数,使其可以通过 1 limb 基底空间的所有
743 * MR 测试。此测试主要用于搭配全基底空间快速过滤,不承诺对抗性输入下的强度保证。
744 * @return 0 = 合数;1 = 素数(确定性判据,本契约域不可达);2 = 极大概率为素数
745 */
746LMMP_API int lmmp_is_prime_n_notrial_(mp_srcptr np, mp_size_t nn, int strength);
747
748/**
749 * @brief Proth 数 k*2^n+1 的素性判定(普罗斯定理)
750 * @param k 系数(k < 2^32)
751 * @param n 指数(2 的幂次)
752 * @warning k>0 且为奇数, n>0
753 * @return 0 = 合数;1 = 素数(确定性判据,本契约域可达);
754 * 2 = 极大概率为素数(BPSW 型素数;回退路径,极少触发)
755 */
757
758/**
759 * @brief 计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
760 * @param base 底数指针
761 * @param n 底数 limb 长度
762 * @param exp 指数
763 * @warning n>0, base[n-1]!=0, [base,n]>1
764 * @return 返回值为 [base,n]^exp 需要的 limb 缓冲区长度(比实际长度多)
765 */
767
768/**
769 * @brief 计算幂次方需要的limb缓冲区长度 base ^ exp
770 * @param base 底数
771 * @param exp 指数
772 * @warning exp>0, base>=1
773 * @return 返回值为 base^exp 需要的 limb 缓冲区长度(比实际长度多)
774 */
776
777/**
778 * @brief 计算奇数次幂算法 [dst,rn] = [base,n] ^ exp
779 * @param dst 结果指针
780 * @param rn 结果指针的 limb 缓冲区长度
781 * @param base 底数指针
782 * @param n 底数指针的 limb 长度
783 * @param exp 指数
784 * @warning n>0, base[n-1]!=0, sep(dst,base), [base,n]>1, exp>=3, exp%2==1
785 * @return 返回 dst 的实际 limb 长度
786 */
788
789/**
790 * @brief 计算幂次方 [dst,rn] = [base,1] ^ exp
791 * @param dst 结果指针
792 * @param rn 结果指针的 limb 长度
793 * @param base 底数(4位无符号整数)
794 * @param exp 指数
795 * @warning 1<=base<=0xf, exp>0
796 * @return 返回 dst 的实际 limb 长度
797 */
799
800/**
801 * @brief 计算幂次方 [dst,rn] = [base,1] ^ exp
802 * @param dst 结果指针
803 * @param rn 结果指针的 limb 长度
804 * @param base 底数(8位无符号整数)
805 * @param exp 指数
806 * @warning 0<base<=0xff, exp>0
807 * @return 返回 dst 的实际 limb 长度
808 */
810
811/**
812 * @brief 计算幂次方 [dst,rn] = [base,1] ^ exp
813 * @param dst 结果指针
814 * @param rn 结果指针的 limb 长度
815 * @param base 底数(16位无符号整数)
816 * @param exp 指数
817 * @warning 0<base<=0xffff, exp>0
818 * @return 返回 dst 的实际 limb 长度
819 */
821
822/**
823 * @brief 计算幂次方 [dst,rn] = [base,1] ^ exp
824 * @param dst 结果指针
825 * @param rn 结果指针的 limb 长度
826 * @param base 底数(32位无符号整数)
827 * @param exp 指数
828 * @warning 0<base<=2^32-1, exp>0
829 * @return 返回 dst 的实际 limb 长度
830 */
832
833/**
834 * @brief 计算幂次方 [dst,rn] = [base,1] ^ exp
835 * @param dst 结果指针
836 * @param rn 结果指针的 limb 长度
837 * @param base 底数(64位无符号整数)
838 * @param exp 指数
839 * @warning 2^32<=base<=2^64-1, exp>0
840 * @return 返回 dst 的实际 limb 长度
841 */
843
844/**
845 * @brief 计算幂次方 [dst,rn] = [base,1] ^ exp
846 * @param dst 结果指针
847 * @param base 底数
848 * @param exp 指数
849 * @warning base>=1, exp>0
850 * @return 返回 dst 的实际 limb 长度
851 */
853
854/**
855 * @brief 计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp
856 * @param dst 结果指针
857 * @param rn 结果指针的 limb 长度
858 * @param base 底数指针
859 * @param n 底数指针的 limb 长度
860 * @param exp 指数
861 * @warning n>0, base[n-1]!=0, sep(dst,base), exp>0
862 * @return 返回 dst 的实际 limb 长度
863 */
865
866/**
867 * @brief 计算大整数幂 [dst,rn] = [base,n] ^ exp
868 * @param dst 结果指针
869 * @param rn 结果指针的 limb 长度
870 * @param base 底数指针
871 * @param n 底数指针的 limb 长度
872 * @param exp 指数
873 * @warning n>0, base[n-1]!=0, sep(dst,base), exp>0
874 * @return 返回 dst 的实际 limb 长度
875 */
877
878/**
879 * @brief 计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
880 * @param n Fibonacci 数列的下标
881 * @return 缓冲区长度,比 F[n] 的实际长度多 2-4 个 limb
882 */
884
885/**
886 * @brief 计算 Fibonacci 数 [dst,rn] = F[n]
887 * @param dst 结果指针
888 * @param rn dst 的 limb 缓冲区长度
889 * @param n Fibonacci 数列的下标
890 * @warning dst!=NULL, rn>=lmmp_fibonacci_size_(n)
891 * @return F[n] 的实际 limb 长度(n==0 时 返回 0)
892 */
894
895/**
896 * @brief 计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
897 * @param dst F[n] 结果指针
898 * @param dst2 F[n-1] 结果指针
899 * @param rn dst 与 dst2 各自的 limb 缓冲区长度
900 * @param n Fibonacci 数列的下标
901 * @warning dst!=NULL, dst2!=NULL, sep(dst,dst2), rn>=lmmp_fibonacci_size_(n)
902 * @return F[n] 的实际 limb 长度(n==0时,返回1);F[n-1] 的实际长度为ret-(dst2[ret-1]==0),至多比返回值少1
903 */
905
906/**
907 * @brief 计算 nPr 排列数的 limb 缓冲区长度
908 * @param n 排列数的总数
909 * @param r 排列数的选择数
910 * @param bits 被修改为 nPr 的2的因子数
911 * @warning r<=n, bits!=NULL
912 * @return nPr 排列数的 limb 缓冲区长度(比实际长度多)
913 */
915
916/**
917 * @brief 计算 nPr 排列数的奇数部分
918 * @param dst 结果指针
919 * @param rn 结果指针的 limb 长度(nPr_size_ 函数的返回值 - bits/LIMB_BITS)
920 * @param n 排列数的总数
921 * @param r 排列数的选择数
922 * @warning 0xffff>=n>=r, dst!=NULL, rn>0
923 * @return 返回 dst 的实际 limb 长度
924 */
926
927/**
928 * @brief 计算 nPr 排列数的奇数部分
929 * @param dst 结果指针
930 * @param rn 结果指针的 limb 长度(nPr_size_ 函数的返回值 - bits/LIMB_BITS)
931 * @param n 排列数的总数
932 * @param r 排列数的选择数
933 * @warning 0xffffffff>=n>=r, dst!=NULL, rn>0
934 * @return 返回 dst 的实际 limb 长度
935 */
937
938/**
939 * @brief 计算 nPr 排列数的奇数部分
940 * @param dst 结果指针
941 * @param rn 结果指针的 limb 长度(nPr_size_ 函数的返回值 - bits/LIMB_BITS)
942 * @param n 排列数的总数
943 * @param r 排列数的选择数
944 * @warning n>=r, dst!=NULL, rn>0
945 * @return 返回 dst 的实际 limb 长度
946 */
948
949/**
950 * @brief 计算 nPr 排列数 ( nPr = n! / (n-r)! )
951 * @param dst 结果指针
952 * @param bits nPr 的2的因子数
953 * @param rn 结果指针的 limb 长度
954 * @param n 排列数的总数
955 * @param r 排列数的选择数
956 * @warning n>=r, dst!=NULL, rn>0
957 * @return 返回 dst 的实际 limb 长度
958 */
960
961/**
962 * @brief 计算 n! 阶乘的 limb 缓冲区长度
963 * @param n 阶乘的阶数
964 * @param bits 被修改为 n! 的2的因子数
965 * @warning bits!=NULL
966 * @return n! 阶乘的 limb 缓冲区长度(比实际长度多)
967 */
969
970/**
971 * @brief 计算 n! 阶乘的奇数部分
972 * @param dst 结果指针
973 * @param rn 结果指针的 limb 长度(factorial_size_ 函数的返回值 - bits/LIMB_BITS)
974 * @param n 阶乘的阶数
975 * @warning n>0xffff, dst!=NULL, rn>0
976 * @return 返回 dst 的实际 limb 长度
977 */
979
980/**
981 * @brief 计算 n! 阶乘
982 * @param dst 结果指针
983 * @param bits n! 的2的因子数
984 * @param rn 结果指针的 limb 长度
985 * @param n 阶乘的阶数
986 * @warning dst!=NULL, rn>0
987 * @return 返回 dst 的实际 limb 长度
988 */
990
991/**
992 * @brief 计算 n!! 双阶乘的 limb 缓冲区长度
993 * @param n 双阶乘的阶数
994 * @param bits 被修改为 n!! 的2的因子数
995 * @warning bits!=NULL
996 * @return n!! 双阶乘的 limb 缓冲区长度
997 */
999
1000/**
1001 * @brief 计算 n!! 双阶乘
1002 * @param dst 结果指针
1003 * @param bits n!! 的2的因子数
1004 * @param rn 结果指针的 limb 长度
1005 * @param n 双阶乘的阶数
1006 * @warning dst!=NULL, rn>0
1007 * @note 0的双阶乘为1,n为偶数时,n!!=2*4*...*n,n为奇数时,n!!=1*3*...*n
1008 * @return 返回 dst 的实际 limb 长度
1009 */
1011
1012/**
1013 * @brief 计算hyper阶乘的 limb 缓冲区长度
1014 * @param n hyper阶乘的阶数
1015 * @param bits 被修改为 hyper阶乘的2的因子数
1016 * @warning bits!=NULL
1017 * @return hyper阶乘的 limb 缓冲区长度
1018 */
1020
1021/**
1022 * @brief 计算hyper阶乘(k^k累乘至n)
1023 * @param dst 结果指针
1024 * @param bits hyper阶乘的2的因子数
1025 * @param rn 结果指针的 limb 长度
1026 * @param n hyper阶乘的阶数
1027 * @warning dst!=NULL, rn>0
1028 * @return dst 的实际 limb 长度
1029 */
1031
1032/**
1033 * @brief 计算super阶乘的 limb 缓冲区长度
1034 * @param n super阶乘的阶数
1035 * @param bits 被修改为 super阶乘的2的因子数
1036 * @warning bits!=NULL
1037 * @return super阶乘的 limb 缓冲区长度
1038 */
1040
1041/**
1042 * @brief 计算super阶乘(k!累乘至n)
1043 * @param dst 结果指针
1044 * @param bits super阶乘的2的因子数
1045 * @param rn 结果指针的 limb 长度
1046 * @param n super阶乘的阶数
1047 * @warning dst!=NULL, rn>0
1048 * @return dst 的实际 limb 长度
1049 */
1051
1052/**
1053 * @brief 计算质数阶乘的 limb 缓冲区长度
1054 * @param n 质数阶乘的阶数
1055 * @return 质数阶乘的 limb 缓冲区长度
1056 */
1058
1059/**
1060* @brief 计算质数阶乘(不超过n的质数累乘)
1061* @param dst 结果指针
1062* @param rn 结果指针的 limb 长度
1063* @param n 质数阶乘的阶数
1064* @warning dst!=NULL, rn>0
1065* @return dst 的实际 limb 长度
1066*/
1068
1069/**
1070 * @brief 计算 nCr 组合数的 limb 缓冲区长度
1071 * @param n 组合数的总数
1072 * @param r 组合数的选择数
1073 * @param bits 被修改为 nCr 的2的因子数
1074 * @warning r<=n/2, bits!=NULL
1075 * @return nCr 组合数的 limb 缓冲区长度(比实际长度多 1-2 个 limb)
1076 */
1078
1079/**
1080 * @brief 计算 nCr 组合数的奇数部分
1081 * @param dst 结果指针
1082 * @param rn 结果指针的 limb 长度
1083 * @param n 组合数的总数
1084 * @param r 组合数的选择数
1085 * @return 返回 dst 的实际 limb 长度
1086 * @warning r<=n/2, n<=0xffff, dst!=NULL, rn>0
1087 */
1089
1090/**
1091 * @brief 计算 nCr 组合数的奇数部分
1092 * @param dst 结果指针
1093 * @param rn 结果指针的 limb 长度
1094 * @param n 组合数的总数
1095 * @param r 组合数的选择数
1096 * @return 返回 dst 的实际 limb 长度
1097 * @warning r<=n/2, 0xffff<n, dst!=NULL, rn>0
1098 */
1100
1101/**
1102 * @brief 计算 nCr 组合数 ( nCr = n! / (r!(n-r)!) )
1103 * @param dst 结果指针
1104 * @param bits nCr 的2的因子数
1105 * @param rn 结果指针的 limb 长度
1106 * @param n 组合数的总数
1107 * @param r 组合数的选择数
1108 * @return 返回 dst 的实际 limb 长度
1109 * @warning r<=n/2, n<=0xffffffff, dst!=NULL, rn>0
1110 */
1112
1113/**
1114 * @brief 计算多项式系数的 limb 缓冲区长度
1115 * @param r 需要计算的系数的数组
1116 * @param m 系数的个数
1117 * @param n 输出变量,将会被修改为 r[i] 的总和,即r1+r2+...+rm
1118 * @return 多项式系数的 limb 缓冲区长度(比实际长度多 1-2 个 limb)
1119 * @note 多项式系数为 ( r1+r2+...+rm )! / ( r1! * r2! * ... * rm!)
1120 * @warning 我们使用 ulong* n 来同时计算 r[i] 的总和,因为 n 可能超过 0xffffffff。
1121 * 我们预计算 n,这不仅可以作为后续多项式系数函数的参数传入。
1122 * 同时也请调用者注意判断 n 是否超过了 0xffffffff
1123 * 这是 lmmp_multinomial_ 函数的限制。
1124 */
1126
1127/**
1128 * @brief 计算多项式系数
1129 * @param dst 结果指针
1130 * @param rn 结果指针的 limb 长度
1131 * @param n r[i] 的总和
1132 * @param r 需要计算的系数的数组
1133 * @param m 系数的个数
1134 * @warning m>1, n>0
1135 * @note 多项式系数为 ( r1+r2+...+rm )! / ( r1! * r2! * ... * rm!)
1136 * @return 返回 dst 的实际 limb 长度
1137 */
1139
1140/**
1141 * @brief 计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
1142 * @param x 首项
1143 * @param n 等差数列共n+1项
1144 * @param m 公差
1145 * @warning x>0, m>1, n>0, x+n*m<=0xffffffff
1146 * @return 等差数列乘积的 limb 缓冲区长度(比实际长度多 1-2 个 limb)
1147 */
1149
1150/**
1151 * @brief 计算等差数列乘积 x(x+m)...(x+n*m)
1152 * @param dst 结果指针
1153 * @param rn 结果指针的 limb 长度
1154 * @param x 首项
1155 * @param n 等差数列共n+1项
1156 * @param m 公差(大于1)
1157 * @warning x>0, m>1, n>0, dst!=NULL, rn>0, x+n*m<=0xffffffff
1158 * @return 结果的实际的 limb 缓冲区长度
1159 */
1161
1162/**
1163 * @brief 除去 [np,nn] 中的 [dp,dn] 的因子
1164 * @param np 被除数指针,将会被修改为除去因子后的数
1165 * @param nn 被除数指针的 limb 长度,将会被修改除去因子后的长度
1166 * @param dp 除数指针
1167 * @param dn 除数指针的 limb 长度
1168 * @warning np!=NULL, nn>0, dp!=NULL, dn>0, [dp,dn]!=1
1169 * @note 如果[np,nn]能被[dp,dn]整除,则[np,nn]将被修改为除去因子后的数,nn将被修改为除去因子后的长度。
1170 * 如果不能被整除,则[np,nn]保持不变,并返回0。
1171 * @return [np,nn]中被[dp,dn]除去的因子的个数,如果不能被整除,则返回0
1172 */
1174
1175/**
1176 * @brief 计算算术平方根 floor(sqrt(a))
1177 * @param a 被开方数
1178 * @return floor(sqrt(a))
1179 */
1181
1182/**
1183 * @brief 计算算术平方根 floor(sqrt(x))
1184 * @param dstr 余数指针(1个limb)
1185 * @param x 被开方数
1186 * @warning x>=B/4, dstr!=NULL
1187 * @note [dstr,1]=sqrtrem(x), return floor(sqrt(x))
1188 * @return floor(sqrt(x))
1189 */
1191
1192/**
1193 * @brief 计算算术平方根 floor(sqrt([numa,2]))
1194 * @param dstr 余数指针(2个limb)
1195 * @param numa 被开方数指针
1196 * @warning numa[1]>=B/4, dstr!=NULL, numa!=NULL, eqsep(dstr,numa)
1197 * @note return: floor(sqrt([numa,2])), [dstr,2]=remainder
1198 * @return floor(sqrt([numa,2]))
1199 */
1201
1202/**
1203 * @brief 计算算术平方根 floor(sqrt([numa,3]))
1204 * @param dsts 结果指针(2个limb)
1205 * @param dstr 余数指针(3个limb,最高位补零),传 NULL 表示不计算余数
1206 * @param numa 被开方数指针
1207 * @warning numa[2]>=B/4, dsts!=NULL, numa!=NULL, eqsep(dsts,numa), eqsep(dstr,numa)
1208 * @note [dstr,3] = [numa,3] - [dsts,2]^2 <= 2*[dsts,2]
1209 */
1210LMMP_API void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa);
1211
1212/**
1213 * @brief 计算算术平方根 floor(sqrt([numa,4]))
1214 * @param dsts 结果指针(2个limb)
1215 * @param dstr 余数指针(3个limb),传 NULL 表示不计算余数
1216 * @param numa 被开方数指针
1217 * @warning numa[3]>=B/4, dsts!=NULL, numa!=NULL, eqsep(dsts,numa), eqsep(dstr,numa)
1218 * @note [dstr,3] = [numa,4] - [dsts,2]^2 <= 2*[dsts,2]
1219 */
1220LMMP_API void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa);
1221
1222/**
1223 * @brief 计算算术平方根 floor(sqrt([numa,2*ns]))
1224 * @param dst 结果指针(ns个limb)
1225 * @param numa 被开方数指针(2*ns个limb,且会被修改,若计算余数,余数存储在[numa,ns+1]中)
1226 * @param ns 结果指针的 limb 长度
1227 * @param tp 临时指针(3*ns/2+1个limb)
1228 * @param calr 是否计算余数(0表示不计算余数,1表示计算余数)
1229 * @warning numa[2*ns-1]>=B/4, dst!=NULL, numa!=NULL, tp!=NULL, sep(dst,numa,tp)
1230 * @note 即使输入calr=0,numa也会被修改,如果calr=1,则[numa,ns+1]将会储存余数。
1231 */
1233
1234/**
1235 * @brief 计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])),
1236 * 则 [dstis,ns+1] 满足 I-1 <= [dstis,ns+1] <= I,且 dstis[ns]=1
1237 * @param dstis 目标数组
1238 * @param ns dstis数组的 limb 长度为 ns+1
1239 * @param numa 输入数组
1240 * @param na numa数组的 limb 长度
1241 * @warning ns>=3, na>0, ns>=na(否则语义变化,见@note), numa[na-1]>=B/4,
1242 * dstis!=NULL, numa!=NULL, sep(dstis,numa)
1243 * @note 结果是 I 的至多低估 1 的下近似,绝不高估;随机输入实测几乎恒等于 I,
1244 * 仅当 I 邻近 B^ns 或 2*B^ns 的构造输入(如 [numa,na]=B^na/4、B^na-1 等)
1245 * 会得到 I-1。
1246 * 恒有 dstis[ns]=1,即结果落在 [B^ns, 2*B^ns) 内。
1247 * 当 ns<na 时语义不同:仅使用 numa 的最高 ns 个 limb(记为 a_top),
1248 * 结果变为 floor(sqrt(B^(3*ns)/a_top))-[0|1],与 I 相差 B^((ns-na)/2) 倍。
1249 */
1251
1252/**
1253 * @brief 计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))
1254 * @param dsts 目标数组(长度为 nf+na/2+1 个limb)
1255 * @param numa 输入数组(长度为 na 个limb)
1256 * @param na numa数组的 limb 长度
1257 * @param nf 精度因子
1258 * @warning na>0, nf>=2, nf+na/2+1>=na, dsts!=NULL, numa!=NULL, eqsep(dsts,numa)
1259 * @note 设 x = sqrt([numa,na]*B^(2*nf))(实数),round 为四舍五入(恰为 1/2 时进位),
1260 * 则结果恰为 round(x-eps),其中 0 <= eps < 2^-31(na 为奇数)或 2^-63(na 为偶数)。
1261 * eps 非负,故结果绝不超过 round(x);仅当 x 的小数部分落在 [1/2, 1/2+eps)
1262 * 时得到 floor(x) 而非 floor(x)+1(随机输入下概率 < 2^-30),此即
1263 * [floor|round] 的确切含义。
1264 */
1266
1267/**
1268 * @brief 计算 [numa,na] * B^(2*nf) 的平方根和余数
1269 * @param dsts 平方根结果输出指针(长度为 nf+na/2+1 个limb)
1270 * @param dstr 余数结果输出指针(NULL表示不计算余数)
1271 * @param numa 源操作数指针(长度为 na 个limb)
1272 * @param na 操作数的 limb 长度
1273 * @param nf 精度因子
1274 * @note if (dstr != NULL) {
1275 * [dsts,nf+na/2+1], [dstr,nf+na/2+1] = sqrtrem([numa,na]*B^(2*nf))
1276 * } else {
1277 * if (nf == 0) {
1278 * [dsts,na/2+1] = floor(sqrt([numa,na]))
1279 * } else {
1280 * [dsts,nf+na/2+1] = [floor|round](sqrt([numa,na]*B^(2*nf)))
1281 * }
1282 * }
1283 * @attention 如你需要精确的floor(sqrt(x))语义,请确保nf==0
1284 * @warning na>0, numa[na-1]!=0, eqsep(dsts,numa), eqsep(dstr,numa)
1285 */
1286LMMP_API void lmmp_sqrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf);
1287
1288/**
1289 * @brief 计算算数立方根 floor(cbrt(n))
1290 * @param n 被开方数
1291 * @return floor(cbrt(n))
1292 * @warning n>0
1293 * @note 使用Chebyshev估计,当n较大时,此算法更占优势
1294 */
1296
1297/**
1298 * @brief 计算算数立方根 floor(cbrt(n))
1299 * @param n 被开方数
1300 * @return floor(cbrt(n))
1301 * @note 会依据n的大小,选择合适的算法
1302 */
1304
1305/**
1306 * @brief 计算算数立方根 floor(cbrt(a0+a1*B+a2*B^2))
1307 * @param a0 低位 limb
1308 * @param a1 中位 limb
1309 * @param a2 高位 limb
1310 * @warning a1和a2应至少有一个大于0
1311 * @note a2可以为0,但a1需要大于0,即这个数至少应有65个bit
1312 * @return floor(cbrt(a0+a1*B+a2*B^2))
1313 */
1315
1316/**
1317 * @brief 计算算术立方根 floor(cbrt([numa,na]))
1318 * @param dst 结果指针(2个limb)
1319 * @param numa 被开方数指针
1320 * @param na 被开方数的 limb 长度
1321 * @warning 3<na<=6, numa[na-1]!=0, dst!=NULL, numa!=NULL, sep(dst,numa)
1322 */
1323LMMP_API void lmmp_cbrt_6_(mp_ptr dst, mp_srcptr numa, mp_size_t na);
1324
1325/**
1326 * @brief 计算算术立方根 [dst,2] = floor(cbrt([numa,6]))
1327 * @param dst 结果指针(2个limb)
1328 * @param numa 被开方数指针(6个limb,会被修改;返回时 [numa,5] 储存余数,即[numa,6] - [dst,2]^3)
1329 * @param tp 临时指针(至少8个limb)
1330 * @warning numa[5]>=0x6000000000000000, dst!=NULL, numa!=NULL, tp!=NULL, sep(dst,numa,tp)
1331 * @note cbrt_6_ 的 na==6 快速路径;余数是修正循环的副产物,无需额外计算。
1332 */
1334
1335/**
1336 * @brief 计算算术立方根 floor(cbrt([numa,3*ns]))
1337 * @param dst 结果指针(ns个limb)
1338 * @param numa 被开方数指针(3*ns个limb,且会被修改,若计算余数,余数存储在[numa,2*ns+1]中)
1339 * @param ns 结果指针的 limb 长度
1340 * @param tp 临时指针(6*ns+4个limb)
1341 * @param calr 是否计算余数(0表示不计算余数,1表示计算余数)
1342 * @warning numa[3*ns-1]>=0x6000000000000000, dst!=NULL, numa!=NULL, tp!=NULL, sep(dst,numa,tp)
1343 * @note 即使输入calr=0,numa也会被修改,如果calr=1,则[numa,2*ns+1]将会储存余数。
1344 */
1346
1347/**
1348 * @brief 计算逆立方根的定点下近似:记 I=floor(cbrt(B^(3*ns+na)/[numa,na])),
1349 * 则 [dstis,ns+1] 满足 I-1 <= [dstis,ns+1] <= I,且 dstis[ns]>=1
1350 * @param dstis 目标数组(长度为 ns+1 个limb)
1351 * @param ns dstis数组的 limb 长度为 ns+1
1352 * @param numa 输入数组
1353 * @param na numa数组的 limb 长度
1354 * @warning ns>=3, na>0, ns>=na, numa[na-1]>=B/8 (0x2000000000000000),
1355 * dstis!=NULL, numa!=NULL, sep(dstis,numa)
1356 * @note 结果是 I 的至多低估 1 的下近似,绝不高估;随机输入实测几乎恒等于 I,
1357 * 仅当 I 邻近 B^ns 或 2*B^ns 的构造输入(如 [numa,na]=B^na-1、B^na/8
1358 * 等)会得到 I-1。
1359 * 恒有 dstis[ns]>=1,即结果落在 [B^ns, 2*B^ns] 内。
1360 * 当 ns<na 时语义不同:仅使用 numa 的最高 ns 个 limb(记为 a_top),
1361 * 结果变为 floor(cbrt(B^(4*ns)/a_top))-[0|1],与 I 相差 B^((ns-na)/3) 倍。
1362 */
1364
1365/**
1366 * @brief 计算近似立方根 [dsts,na/3+nf+1]=[floor|round](cbrt([numa,na]*B^(3*nf))),
1367 * 输入须已归一化:na ≡ 0 (mod 3) 且顶 limb >= B/8
1368 * @param dsts 目标数组(长度至少 na/3+nf+1 个limb)
1369 * @param numa 输入数组(长度为 na 个limb,已 3 对齐归一化)
1370 * @param na numa数组的 limb 长度(3 的倍数)
1371 * @param nf 精度因子
1372 * @warning na>0, na%3==0, numa[na-1]>=B/8, nf>=2, 3*nf>=2*na+3, dsts!=NULL,
1373 * numa!=NULL, sep(dsts,numa)
1374 * @note 设 x = cbrt([numa,na]*B^(3*nf))(实数),round 为四舍五入(恰为 1/2 时进位),
1375 * 则结果恰为 round(x-eps),其中 0 <= eps < 2^-62。eps 非负,故结果绝不超过
1376 * round(x);仅当 x 的小数部分落在 [1/2, 1/2+eps) 时得到 floor(x) 而非
1377 * floor(x)+1(随机输入下概率 < 2^-62),此即 [floor|round] 的确切含义。
1378 */
1380
1381/**
1382 * @brief 计算 [numa,na] * B^(3*nf) 的立方根和余数
1383 * @param dsts 立方根结果输出指针(缓冲区长度至少 nf+na/3+3 个limb)
1384 * @param dstr 余数结果输出指针(缓冲区长度至少 2*(nf+na/3)+3 个limb,NULL 表示不计算余数)
1385 * @param numa 源操作数指针(长度为 na 个limb)
1386 * @param na 操作数的 limb 长度
1387 * @param nf 精度因子
1388 * @warning na>0, numa[na-1]!=0, eqsep(dsts,numa), eqsep(dstr,numa)
1389 * @note if (dstr != NULL) {
1390 * [dsts],[dstr] = cbrtrem([numa,na]*B^(3*nf)),即精确 floor 立方根
1391 * 与余数 [numa,na]*B^(3*nf) - [dsts]^3(长度 2*ns+1,ns 为根长)
1392 * } else {
1393 * if (nf == 0) {
1394 * [dsts] = floor(cbrt([numa,na]))
1395 * } else {
1396 * [dsts] = [floor|round](cbrt([numa,na]*B^(3*nf)))
1397 * }
1398 * }
1399 * @attention 如你需要精确的floor(cbrt(x))语义,请确保nf==0或传入dstr
1400 */
1401LMMP_API void lmmp_cbrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf);
1402
1403/**
1404 * @brief 计算 floor(n^(1/root))
1405 * @param n 被开方数
1406 * @param root 开方次数
1407 * @return floor(n^(1/root))
1408 * @note root=0时,返回0
1409 */
1411
1412/**
1413 * @brief 计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
1414 * @param na 被开方数的 limb 长度
1415 * @param root 开方次数
1416 * @return tp 至少需要的 limb 数
1417 * @warning na>0, root>=4, root<=2^56
1418 */
1420
1421/**
1422 * @brief 计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
1423 * @param dsts 结果指针(nr = ceil(na/root) 个 limb,顶 limb 恒非零)
1424 * @param dstr 余数结果输出指针((root-1)*nr+1 个 limb,NULL 表示不计算余数)
1425 * @param numa 被开方数指针(只读)
1426 * @param na 被开方数的 limb 长度
1427 * @param root 开方次数
1428 * @param tp 临时区(至少 lmmp_nthroot_size_(na,root) 个 limb)
1429 * @warning na>0, numa[na-1]!=0, root>=4, root<=2^56, sep(dsts,dstr,numa,tp)
1430 * @note 任意长度输入的统一入口,恒为精确 floor 语义(dstr=NULL 不牺牲
1431 * 精度,与 lmmp_cbrt_/lmmp_sqrt_ 的 [floor|round] 口径不同)。
1432 * 对虚拟 Ã = A·2^root 求根后纯移位恢复 S(嵌套 floor 恒等式):
1433 * log2/exp2 128bit 定点种子 + 位窗牛顿精化(层成本 M(e2/64) 与
1434 * root 解耦)+ 认证式窗口探针/全幂端点修正。root=4 走
1435 * sqrt∘sqrt 专用路线(嵌套 floor 恒等式,余数由两级 sqrtrem
1436 * 代数展开)。ns<=1 域分派至 lmmp_nthroot_ulong_。
1437 */
1438LMMP_API void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp);
1439
1440/**
1441 * @brief 计算 [p,n] % 2^48-1
1442 * @param p 被除数指针
1443 * @param n 被除数的 limb 长度
1444 * @warning p!=NULL, n>0
1445 * @return [numa,na] % 2^48-1
1446 */
1448
1449/**
1450 * @brief 非完全平方数过滤器
1451 * @param p 输入数
1452 * @warning p>0
1453 * @return false 意味着必定为非完全平方数,所有完全平方数和部分非完全平方数会返回 true
1454 * @note 此过滤器主要针对随机输入情况,对于大概率是完全平方数的输入,可以无需此函数。
1455 */
1457
1458/**
1459 * @brief 非完全平方数过滤器
1460 * @param p 输入指针
1461 * @param n 输入的 limb 长度
1462 * @warning p!=NULL, n>0, p[n-1]>0
1463 * @return false 意味着必定为非完全平方数,所有完全平方数和部分非完全平方数会返回 true
1464 * @note 此过滤器主要针对随机输入情况,对于大概率是完全平方数的输入,可以无需此函数。
1465 */
1467
1468/**
1469 * @brief 判断[p,n]是否为完全平方数
1470 * @param p 输入指针
1471 * @param n 输入的 limb 长度
1472 * @warning p!=NULL, n>0, p[n-1]>0
1473 * @return 为完全平方数返回 true,否则返回 false
1474 */
1476
1477#ifdef __cplusplus
1478}
1479#endif // __cplusplus
1480
1481#endif // LMMP_NUMTH_H
#define k
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_API
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 lmmp.h:77
size_t mp_bitcnt_t
定义 lmmp.h:98
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
#define a0
#define a1
#define a2
#define t
#define tp
#define s
#define n
#define lo
void lmmp_divexact_unbalance_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, mp_ptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
mp_size_t lmmp_odd_nCr_uint_(mp_ptr dst, mp_size_t rn, uint n, uint r)
计算 nCr 组合数的奇数部分
mp_limb_t lmmp_cbrt_3_(mp_limb_t a0, mp_limb_t a1, mp_limb_t a2)
计算算数立方根 floor(cbrt(a0+a1*B+a2*B^2))
void lmmp_cbrt_6_fast_(mp_ptr dst, mp_ptr numa, mp_ptr tp)
计算算术立方根 [dst,2] = floor(cbrt([numa,6]))
void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,3]))
uint lmmp_powmod_uint_odd_(uint base, ulong exp, uint mod)
计算 base^exp 对 mod 取模
mp_size_t lmmp_multinomial_size_(const uintp r, uint m, ulong *n)
计算多项式系数的 limb 缓冲区长度
ulong lmmp_prev_prime_ulong_(ulong n)
小于等于n的上一个素数
mp_size_t lmmp_odd_factorial_uint_(mp_ptr dst, mp_size_t rn, uint n)
计算 n!
mp_size_t n[2][2]
void lmmp_sqrt_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似平方根 [dsts,nf+na/2+1]=[floor|round](sqrt([numa,na]*B^(2*nf)))
定义 sqrt.c:392
mp_size_t lmmp_nthroot_size_(mp_size_t na, ulong root)
计算 lmmp_nthroot_ 所需的 tp 缓冲区长度(任意长度输入入口)
mp_size_t lmmp_remove_(mp_ptr np, mp_size_t *nn, mp_srcptr dp, mp_size_t dn)
除去 [np,nn] 中的 [dp,dn] 的因子
void lmmp_powlo_(mp_ptr dst, mp_srcptr bp, mp_size_t n, mp_srcptr ep, mp_size_t en)
计算 [bp,n]^[ep,en] mod B^n,并将结果写入 [dst,n]
mp_size_t lmmp_gcd_lehmer_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(Lehmer算法)
int16_t * sshortp
定义 numth.h:45
ulong lmmp_gcdext_11_(ulong u, ulong v, slong *s, slong *t)
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_fibonacci2_(mp_ptr dst, mp_ptr dst2, mp_size_t rn, ulong n)
计算 Fibonacci 数对:[dst,rn] = F[n],[dst2,rn] = F[n-1]
mp_size_t lmmp_u4_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
void lmmp_binvert_unbalance_1_(mp_ptr dst, mp_limb_t a, mp_size_t n)
计算 a 在 B^n 下的逆元
void lmmp_cbrt_newton_(mp_ptr dsts, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算近似立方根 [dsts,na/3+nf+1]=[floor|round](cbrt([numa,na]*B^(3*nf))), 输入须已归一化:na ≡ 0 (mod 3) 且顶 limb >= B...
定义 cbrt.c:688
mp_size_t lmmp_pow_1_size_(mp_limb_t base, ulong exp)
计算幂次方需要的limb缓冲区长度 base ^ exp
定义 pow.c:65
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_modinv_ulong_(ulong u, ulong m)
模逆元(单 limb):求 u^{-1} mod m
mp_size_t lmmp_odd_nPr_ushort_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
ulong lmmp_cbrt_chebyshev_(ulong n)
计算算数立方根 floor(cbrt(n))
void lmmp_sqrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术平方根 floor(sqrt([numa,2*ns]))
mp_size_t lmmp_pow_win2_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方2比特窗口快速幂算法 [dst,rn] = [base,n] ^ exp
bool lmmp_perfsqr_filter_1_(mp_limb_t p)
非完全平方数过滤器
mp_size_t lmmp_gcd_2_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp)
计算两个无符号整数的最大公约数
int lmmp_is_prime_2_notrial_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数(无试除法)
ulong lmmp_binvert_ulong_(ulong a)
计算 a 在2^64下的逆元
mp_size_t lmmp_arith_seqprod_size_(uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)的 limb 缓冲区长度
mp_limb_t lmmp_redc_(mp_ptr dst, mp_srcptr tp, mp_srcptr ninv, mp_srcptr mp, mp_size_t n)
Montgomery 归约(REDC):计算 ([tp,2n] + q*[mp,n]) / B^n,其中 q = [tp,n] * [ninv,n] mod B^n,即结果为 [tp,...
void lmmp_cbrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算 [numa,na] * B^(3*nf) 的立方根和余数
定义 cbrt.c:718
void lmmp_powlo_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,2]^[ep,en] mod B^2,并将结果写入 [dst,2](lmmp_powlo_ 的 2 limb 特化)
void lmmp_binvert_n_dc_(mp_ptr dst, mp_srcptr numa, mp_size_t n, mp_ptr tp)
计算 [numa,n] 在 B^n 下的逆元
mp_size_t lmmp_u32_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
uint16_t * ushortp
定义 numth.h:44
mp_size_t lmmp_pow_1_(mp_ptr dst, mp_size_t rn, mp_limb_t base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
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
uint64_t * ulongp
定义 numth.h:48
uint32_t uint
定义 numth.h:38
int lmmp_is_strong_lucas_(mp_srcptr np, mp_size_t nn)
强 Lucas-Selfridge 测试(大于 128 位)
ulong lmmp_cbrt_ulong_(ulong n)
计算算数立方根 floor(cbrt(n))
bool lmmp_is_prime_uint_(uint n)
判断素数
mp_size_t lmmp_superfac_size_(ushort n, mp_bitcnt_t *bits)
计算super阶乘的 limb 缓冲区长度
ulong lmmp_powmod_ulong_odd_(ulong base, ulong exp, ulong mod)
计算 base^exp 对 mod 取模
void lmmp_powmod_odd_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n)
计算奇模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
mp_size_t lmmp_2factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
uint lmmp_binvert_uint_(uint a)
计算 a 在2^32下的逆元
mp_size_t lmmp_pow_basecase_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算奇数次幂算法 [dst,rn] = [base,n] ^ exp
void lmmp_powmod_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mp, mp_size_t n)
计算任意模数模幂 [dst,n] = [bp,n]^[ep,en] % [mp,n]
ulong lmmp_mulmod_ulong_(ulong a, ulong b, ulong mod, ulongp q)
计算两个无符号整数的乘积,对mod取模,商放入 q 中
uint8_t * ucharp
定义 numth.h:42
int lmmp_is_prime_2_(mp_limb_t lo, mp_limb_t hi)
判断 128 位素数
int8_t * scharp
定义 numth.h:43
uint32_t * uintp
定义 numth.h:46
void lmmp_divexact_basecase_(mp_ptr dst, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn-dn+1]=[np,nn]/[dp,dn],且余数必须为0),朴素算法
mp_size_t lmmp_factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
void lmmp_binvert_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n, mp_ptr tp)
计算 [numa,na] 在 B^n 下的逆元
mp_size_t lmmp_modinv_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t mn)
模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
int64_t slong
定义 numth.h:41
mp_size_t lmmp_u64_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_u8_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
void lmmp_binvert_2_(mp_ptr dst, mp_srcptr numa)
计算 [numa,2] 在 B^2 下的逆元
mp_size_t lmmp_hgcd_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n)
半扩展欧几里得:将数对原地归约至约一半规模,并累积变换矩阵
mp_size_t lmmp_primefac_size_(uint n)
计算质数阶乘的 limb 缓冲区长度
int16_t sshort
定义 numth.h:37
mp_size_t lmmp_hyperfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算hyper阶乘(k^k累乘至n)
mp_size_t lmmp_u16_pow_1_(mp_ptr dst, mp_size_t rn, ulong base, ulong exp)
计算幂次方 [dst,rn] = [base,1] ^ exp
mp_size_t lmmp_gcdext_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g
void lmmp_binvert_3_(mp_ptr dst, mp_srcptr numa)
计算 [numa,3] 在 B^3 下的逆元
mp_size_t lmmp_gcdext_2_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp)
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
void lmmp_divexact_1_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_limb_t d, mp_limb_t dinv)
精确除法([dst,nn]=[np,nn]/d,且余数必须为0)
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
mp_size_t lmmp_2factorial_size_(uint n, mp_bitcnt_t *bits)
计算 n!
int8_t schar
定义 numth.h:35
mp_size_t lmmp_factorial_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n)
计算 n!
bool lmmp_perfsqr_(mp_srcptr p, mp_size_t n)
判断[p,n]是否为完全平方数
int lmmp_is_prime_n_notrial_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(无试除法,强度分档,大于 128 位)
mp_limb_t lmmp_gcd_11_(mp_limb_t u, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:28
mp_size_t lmmp_gcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
定义 gcd.c:27
mp_size_t lmmp_gcd_hgcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(hgcd 分治,长输入优选)
mp_size_t lmmp_hyperfac_size_(ushort n, mp_bitcnt_t *bits)
计算hyper阶乘的 limb 缓冲区长度
mp_size_t lmmp_nCr_size_(uint n, uint r, mp_bitcnt_t *bits)
计算 nCr 组合数的 limb 缓冲区长度
void lmmp_binvert_4_(mp_ptr dst, mp_srcptr numa)
计算 [numa,4] 在 B^4 下的逆元
mp_size_t lmmp_nCr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, uint n, uint r)
计算 nCr 组合数 ( nCr = n!
bool lmmp_is_prime_ulong_notrial_(ulong n)
判断素数(无试除法,单 limb 档)
uint16_t ushort
定义 numth.h:36
mp_size_t lmmp_nPr_size_(ulong n, ulong r, mp_bitcnt_t *bits)
计算 nPr 排列数的 limb 缓冲区长度
mp_size_t lmmp_primefac_(mp_ptr dst, mp_size_t rn, uint n)
计算质数阶乘(不超过n的质数累乘)
mp_size_t lmmp_pow_(mp_ptr dst, mp_size_t rn, mp_srcptr base, mp_size_t n, ulong exp)
计算大整数幂 [dst,rn] = [base,n] ^ exp
void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,4]))
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
void lmmp_divexact_2_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_srcptr dinv)
精确除法([dst,nn]=[np,nn]/[dp,2],且余数必须为0)
void lmmp_cbrt_6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
计算算术立方根 floor(cbrt([numa,na]))
int64_t * slongp
定义 numth.h:49
bool lmmp_is_prime_ulong_(ulong n)
判断素数
ulong lmmp_nthroot_ulong_(ulong n, ulong root)
计算 floor(n^(1/root))
void lmmp_nthroot_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, ulong root, mp_ptr tp)
计算算术根 [dsts,nr] = floor([numa,na]^(1/root))(任意 na/任意顶 limb)
mp_size_t lmmp_multinomial_(mp_ptr dst, mp_size_t rn, uint n, const uintp r, uint m)
计算多项式系数
void lmmp_hgcd_matrix_free_(lmmp_hgcd_matrix_t *M)
释放 hgcd 变换矩阵的元素缓冲
uint64_t ulong
定义 numth.h:39
void lmmp_powmod_2_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en, mp_srcptr mod)
计算奇模数模幂 [dst,2] = [bp,2]^[ep,en] % [mod,2]
mp_size_t lmmp_fibonacci_size_(ulong n)
计算 Fibonacci 数 F[n](及 F[n-1])所需的 limb 缓冲区长度
int32_t sint
定义 numth.h:40
mp_size_t lmmp_fibonacci_(mp_ptr dst, mp_size_t rn, ulong n)
计算 Fibonacci 数 [dst,rn] = F[n]
mp_size_t lmmp_superfac_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ushort n)
计算super阶乘(k!
int lmmp_is_prothprime_(uint k, mp_size_t n)
Proth 数 k*2^n+1 的素性判定(普罗斯定理)
void lmmp_invcbrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆立方根的定点下近似:记 I=floor(cbrt(B^(3*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...
mp_size_t lmmp_gcdext_1_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, ulong v)
扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g
void lmmp_binvert_unbalance_2_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
计算 [numa,2] 在 B^n 下的逆元
mp_size_t lmmp_gcdext_hgcd_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(hgcd 分治,长输入优选):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_gcdext_lehmer_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g
mp_limb_t lmmp_mod_2p48sub1_(mp_srcptr p, mp_size_t n)
计算 [p,n] % 2^48-1
mp_size_t lmmp_arith_seqprod_(mp_ptr dst, mp_size_t rn, uint x, uint n, uint m)
计算等差数列乘积 x(x+m)...(x+n*m)
void lmmp_hgcd_matrix_init_(lmmp_hgcd_matrix_t *M, mp_size_t alloc)
初始化 hgcd 变换矩阵为单位矩阵(堆分配元素缓冲)
mp_limb_t lmmp_gcd_1_(mp_srcptr up, mp_size_t un, mp_limb_t v)
计算两个无符号整数的最大公约数
定义 gcd_1.c:46
int32_t * sintp
定义 numth.h:47
mp_size_t lmmp_pow_size_(mp_srcptr base, mp_size_t n, ulong exp)
计算幂次方需要的limb缓冲区长度 [base,n] ^ exp
定义 pow.c:103
mp_size_t lmmp_odd_nPr_ulong_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
void lmmp_invsqrt_newton_(mp_ptr dstis, mp_size_t ns, mp_srcptr numa, mp_size_t na)
计算逆平方根的定点下近似:记 I=floor(sqrt(B^(2*ns+na)/[numa,na])), 则 [dstis,ns+1] 满足 I-1 <= [dstis,...
void lmmp_sqrt_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_size_t nf)
计算 [numa,na] * B^(2*nf) 的平方根和余数
定义 sqrt.c:441
mp_size_t lmmp_odd_nCr_ushort_(mp_ptr dst, mp_size_t rn, uint n, uint r)
计算 nCr 组合数的奇数部分
void lmmp_powlo_1_(mp_ptr dst, mp_srcptr bp, mp_srcptr ep, mp_size_t en)
计算 [bp,1]^[ep,en] mod B,并将结果写入 [dst,1](lmmp_powlo_ 的 1 limb 特化)
ulong lmmp_next_prime_ulong_(ulong n)
大于n的下一个素数
mp_size_t lmmp_nPr_(mp_ptr dst, mp_bitcnt_t bits, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数 ( nPr = n!
mp_size_t lmmp_gcd_22_(mp_ptr dst, mp_srcptr up, mp_srcptr vp)
计算两个无符号整数的最大公约数
定义 gcd_2.c:60
mp_size_t lmmp_odd_nPr_uint_(mp_ptr dst, mp_size_t rn, ulong n, ulong r)
计算 nPr 排列数的奇数部分
void lmmp_cbrt_divide_(mp_ptr dst, mp_ptr numa, mp_size_t ns, mp_ptr tp, int calr)
计算算术立方根 floor(cbrt([numa,3*ns]))
bool lmmp_perfsqr_filter_(mp_srcptr p, mp_size_t n)
非完全平方数过滤器
void lmmp_binvert_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t n)
计算 [numa,na] 在 B^n 下的逆元
void lmmp_divexact_divide_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0),分治算法
hgcd 变换矩阵