LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
lmmpn.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_LMMPN_H
24#define LMMP_LMMPN_H
25
26#include <stdbool.h>
27
28#include "lmmp.h"
29
30#define LMMP_INLINE static inline
31
32#ifdef __cplusplus
33extern "C" {
34#endif
35
36/**
37 * @brief 运行时判断端序
38 * @return true 表示小端序,false 表示大端序
39 */
41 int num = 1;
42 return (*(char*)&num) != 0;
43}
44
45/**
46 * @brief 计算满足 2^k > x 的最小自然数k
47 * @param x 输入的64位无符号整数
48 * @return 满足条件的最小自然数k
49 */
51
52/**
53 * @brief 计算一个64位无符号整数中1的个数
54 * @param x 输入的64位无符号整数
55 * @return 1的个数
56 */
58
59/**
60 * @brief 计算一个单精度数(limb)中前导零的个数
61 * @param x 输入的64位无符号整数
62 * @return 前导零的位数(范围:0~64)
63 */
65
66/**
67 * @brief 计算一个单精度数(limb)中末尾零的个数
68 * @param x 输入的64位无符号整数
69 * @return 末尾零的位数(范围:0~64)
70 */
72
73/**
74 * @brief 计算两个64位无符号整数相乘的高位结果 (a*b)/B
75 * @param a 第一个64位无符号整数
76 * @param b 第二个64位无符号整数
77 * @return 乘积的高64位结果
78 */
80
81/**
82 * @brief 计算两个64位无符号整数相乘的128位结果 (a*b)
83 * @param dst 输出结果缓冲区,存储乘积结果,长度为 2
84 * @param a 第一个64位无符号整数
85 * @param b 第二个64位无符号整数
86 * @warning dst!=NULL
87 * @return 无返回值
88 */
90
91/**
92 * @brief 带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
93 * @param dst 结果输出指针
94 * @param numa 第一个加数指针
95 * @param numb 第二个加数指针
96 * @param n limb长度
97 * @param c 初始进位值 [0|1]
98 * @warning c=[0|1], n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
99 * @return 运算后的最终进位值 [0|1]
100 */
102
103/**
104 * @brief 无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
105 * @param dst 结果输出指针
106 * @param numa 第一个加数指针
107 * @param numb 第二个加数指针
108 * @param n limb长度
109 * @warning n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
110 * @return 运算后的最终进位值 [0|1]
111 */
113
114/**
115 * @brief 带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
116 * @param dst 结果输出指针
117 * @param numa 被减数指针
118 * @param numb 减数指针
119 * @param n limb长度
120 * @param c 初始借位值 [0|1]
121 * @warning c=[0|1], n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
122 * @return 运算后的最终借位值 [0|1]
123 */
125
126/**
127 * @brief 无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
128 * @param dst 结果输出指针
129 * @param numa 被减数指针
130 * @param numb 减数指针
131 * @param n limb长度
132 * @warning n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
133 * @return 运算后的最终借位值 [0|1]
134 */
136
137/**
138 * @brief 同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
139 * @param dsta 加法结果输出指针
140 * @param dstb 减法结果输出指针
141 * @param numa 第一个操作数指针(被加数/被减数)
142 * @param numb 第二个操作数指针(加数/减数)
143 * @param n limb长度
144 * @warning n>0, eqsep(dsta,[numa|numb]), eqsep(dstb,[numa|numb]), dsta!=NULL, dstb!=NULL, numa!=NULL, numb!=NULL
145 * @return 组合返回值 cb = 2*c + b (c为加法进位, b为减法借位)
146 * 返回值范围: 0(无进位无借位),1(无进位有借位),2(有进位无借位),3(有进位有借位)
147 */
149
150/**
151 * @brief 加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
152 * @param dst 结果输出指针
153 * @param numa 第一个加数指针
154 * @param numb 第二个加数指针
155 * @param n limb长度
156 * @warning n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
157 * @return 右移操作产生的进位值 [0|1]
158 */
160
161/**
162 * @brief 带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1
163 * @param dst 结果输出指针
164 * @param numa 第一个加数指针
165 * @param numb 第二个加数指针
166 * @param n limb长度
167 * @param c 初始进位值 [0|1]
168 * @warning n>0, c=[0|1], eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
169 * @return 右移操作产生的进位值 [0|1]
170 */
172
173/**
174 * @brief 减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
175 * @param dst 结果输出指针
176 * @param numa 被减数指针
177 * @param numb 减数指针
178 * @param n 操作数的位数(limb数量)
179 * @warning n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
180 * @return 右移操作产生的进位值 (0或1)
181 */
183
184/**
185 * @brief 带借位减法后右移1位 [dst,n] = ([numa,n] - [numb,n] - c) >> 1
186 * @param dst 结果输出指针
187 * @param numa 被减数指针
188 * @param numb 减数指针
189 * @param n limb长度
190 * @param c 初始借位值 [0|1]
191 * @warning n>0, c=[0|1], eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
192 * @return 右移操作产生的进位值 [0|1]
193 */
195
196/**
197 * @brief 右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
198 * @param dst 结果输出指针
199 * @param numa 源操作数指针
200 * @param na limb长度
201 * @param shr 右移的位数 (0~63)
202 * @warning na>0, 0<=shr<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
203 * 允许dst指针地址小于numa(即支持原地长移位操作)
204 * @return 其最高shr个比特位填充[numa,na]被移出的shr个最低位,其余比特位为0
205 */
207
208/**
209 * @brief 带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位
210 * @param dst 结果输出指针
211 * @param numa 源操作数指针
212 * @param na limb长度
213 * @param shr 右移的位数 (0~63)
214 * @param c 进位值(其低(64-shr)位必须为0)
215 * @warning na>0, 0<=shr<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
216 * c的低(64-shr)位必须为0
217 * 允许dst指针地址小于numa(即支持原地长移位操作)
218 * @return 其最高shr个比特位填充[numa,na]被移出的shr个最低位,其余比特位为0
219 */
221
222/**
223 * @brief 左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
224 * @param dst 结果输出指针
225 * @param numa 源操作数指针
226 * @param na limb长度
227 * @param shl 左移的位数 (0~63)
228 * @warning na>0, 0<=shl<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
229 * @return 其最低shl个比特位填充[numa,na]被移出的shl个最高位,其余比特位为0
230 */
232
233/**
234 * @brief 带进位的左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充c的低shl位
235 * @param dst 结果输出指针
236 * @param numa 源操作数指针
237 * @param na limb长度
238 * @param shl 左移的位数 (0~63)
239 * @param c 进位值(其高(64-shl)位必须为0)
240 * @warning na>0, 0<=shl<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
241 * c的高(64-shl)位必须为0
242 * @return 其最低shl个比特位填充[numa,na]被移出的shl个最高位,其余比特位为0
243 */
245
246/**
247 * @brief 按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
248 * @param dst 结果输出指针
249 * @param numa 源操作数指针
250 * @param na limb长度
251 * @warning na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL
252 */
253LMMP_API void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na);
254
255/**
256 * @brief 左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1
257 * @param dst 结果输出指针
258 * @param numa 源操作数指针
259 * @param na limb长度
260 * @param shl 左移的位数 (0~63)
261 * @warning na>0, 0<=shl<64, eqsep(dst,numa), dst!=NULL, numa!=NULL
262 * @return 其最低shl个比特位填充[numa,na]被移出的shl个最高位,其余比特位为0
263 */
265
266/**
267 * @brief 加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
268 * @param dst 结果输出指针
269 * @param numa 被加数指针
270 * @param numb 加数指针(先左移1位)
271 * @param n limb长度
272 * @warning n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL
273 * @return 运算后的进位值 [0|1|2]
274 */
276
277/**
278 * @brief 减法结合左移1位操作 [dst,n] = [numa,n] - ([numb,n] << 1)
279 * @param dst 结果输出指针
280 * @param numa 被减数指针
281 * @param numb 减数指针(先左移1位)
282 * @param n limb长度
283 * @warning n>0, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL
284 * @return 运算后的借位值 [0|1|2]
285 */
287
288/**
289 * @brief 乘以单limb并累加操作 [numa,n] += [numb,n] * b
290 * @param numa 被加数指针(结果也存储在此)
291 * @param numb 乘数指针
292 * @param n limb长度
293 * @param b 乘数
294 * @warning n>0, eqsep(numa,numb)), numa!=NULL, numb!=NULL
295 * @return 运算后的进位limb值
296 */
298
299/**
300 * @brief 乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
301 * @param numa 被加数指针(前 n limb 就地累加结果,第 n+1 limb 直接覆写)
302 * @param numb 乘数数组指针
303 * @param n limb长度
304 * @param bp 双limb乘数(2 个limb)
305 * @warning n>0, eqsep(numa,numb), sep(numa,bp), numb!=NULL, bp!=NULL
306 * @return 第 n+1 limb(最高溢出 limb)
307 * @note 第 n limb 写入 numa[n](覆写而非累加该处旧值)
308 */
310
311/**
312 * @brief 乘以单limb并累减操作 [numa,n] -= [numb,n] * b
313 * @param numa 被减数指针(结果也存储在此)
314 * @param numb 乘数指针
315 * @param n limb长度
316 * @param b 乘数
317 * @warning n>0, eqsep(numa,numb)), numa!=NULL, numb!=NULL
318 * @return 运算后的借位limb值
319 */
321
322/**
323 * @brief 乘以单limb操作 [dst,na] = [numa,na] * x
324 * @param dst 结果输出指针
325 * @param numa 被乘数指针
326 * @param na 操作数的 limb 长度
327 * @param x 单个limb乘数
328 * @warning na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL
329 * @return 运算后的进位limb值
330 */
332
333/**
334 * @brief 基础平方运算 [dst,2*na] = [numa,na]^2
335 * @param dst 输出结果缓冲区,长度至少为 2*na
336 * @param numa 输入操作数,长度为 na
337 * @param na 输入操作数的 limb 长度
338 * @warning 0<na, sep(dst,numa), dst!=NULL, numa!=NULL
339 * @return 无返回值,结果存储在dst中
340 */
342
343/**
344 * @brief Toom-2平方运算 [dst,2*na] = [numa,na]^2
345 * @param dst 输出结果缓冲区,长度至少为 2*na
346 * @param numa 输入操作数,长度为 na
347 * @param na 输入操作数的 limb 长度
348 * @warning 4<=na, sep(dst,numa), dst!=NULL, numa!=NULL
349 * @return 无返回值,结果存储在dst中
350 */
352
353/**
354 * @brief Toom-3平方运算 [dst,2*na] = [numa,na]^2
355 * @param dst 输出结果缓冲区,长度至少为 2*na
356 * @param numa 输入操作数,长度为 na
357 * @param na 输入操作数的 limb 长度
358 * @warning 5<=na, sep(dst,numa), dst!=NULL, numa!=NULL
359 * @return 无返回值,结果存储在dst中
360 */
362
363/**
364 * @brief Toom-4平方运算 [dst,2*na] = [numa,na]^2
365 * @param dst 输出结果缓冲区,长度至少为 2*na
366 * @param numa 输入操作数,长度为 na
367 * @param na 输入操作数的 limb 长度
368 * @warning 10<=na, sep(dst,numa), dst!=NULL, numa!=NULL
369 * @return 无返回值,结果存储在dst中
370 */
372
373/**
374 * @brief Toom-6平方运算 [dst,2*na] = [numa,na]^2
375 * (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)
376 * @param dst 输出结果缓冲区,长度至少为 2*na
377 * @param numa 输入操作数,长度为 na
378 * @param na 输入操作数的 limb 长度
379 * @warning 26<=na, sep(dst,numa), dst!=NULL, numa!=NULL
380 * @return 无返回值,结果存储在dst中
381 */
383
384/**
385 * @brief Toom-8平方运算 [dst,2*na] = [numa,na]^2
386 * (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)
387 * @param dst 输出结果缓冲区,长度至少为 2*na
388 * @param numa 输入操作数,长度为 na
389 * @param na 输入操作数的 limb 长度
390 * @warning 51<=na, na!=57, sep(dst,numa), dst!=NULL, numa!=NULL
391 * @return 无返回值,结果存储在dst中
392 */
394
395/**
396 * @brief 基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
397 * @param dst 输出结果缓冲区,长度至少为 na+nb
398 * @param numa 第一个输入操作数,长度为 na
399 * @param na 第一个操作数的 limb 长度
400 * @param numb 第二个输入操作数,长度为 nb
401 * @param nb 第二个操作数的 limb 长度
402 * @warning 0<nb<=na, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
403 * @return 无返回值,结果存储在dst中
404 */
406
407/**
408 * @brief Toom-22乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
409 * @param dst 输出结果缓冲区,长度至少为 na+nb
410 * @param numa 第一个输入操作数,长度为 na
411 * @param na 第一个操作数的 limb 长度
412 * @param numb 第二个输入操作数,长度为 nb
413 * @param nb 第二个操作数的 limb 长度
414 * @warning 1/2<nb/na<=1, nb>=5, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
415 * @return 无返回值,结果存储在dst中
416 */
418
419/**
420 * @brief Toom-32乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
421 * @param dst 输出结果缓冲区,长度至少为 na+nb
422 * @param numa 第一个输入操作数,长度为 na
423 * @param na 第一个操作数的 limb 长度
424 * @param numb 第二个输入操作数,长度为 nb
425 * @param nb 第二个操作数的 limb 长度
426 * @warning 1/3<nb/na<1, nb>=12, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
427 * @return 无返回值,结果存储在dst中
428 */
430
431/**
432 * @brief Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
433 * @param dst 输出结果缓冲区,长度至少为 na+nb
434 * @param numa 第一个输入操作数,长度为 na
435 * @param na 第一个操作数的 limb 长度
436 * @param numb 第二个输入操作数,长度为 nb
437 * @param nb 第二个操作数的 limb 长度
438 * @warning 2/3<nb/na<=1, nb>=26, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
439 * @return 无返回值,结果存储在dst中
440 */
442
443/**
444 * @brief Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
445 * @param dst 输出结果缓冲区,长度至少为 na+nb
446 * @param numa 第一个输入操作数,长度为 na
447 * @param na 第一个操作数的 limb 长度
448 * @param numb 第二个输入操作数,长度为 nb
449 * @param nb 第二个操作数的 limb 长度
450 * @warning 1/4<nb/na<2/3, nb>=20, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
451 * @return 无返回值,结果存储在dst中
452 */
454
455/**
456 * @brief Toom-42不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
457 * @param dst 输出结果缓冲区,长度至少为 na+nb
458 * @param numa 第一个输入操作数,长度为 na
459 * @param na 第一个操作数的 limb 长度
460 * @param numb 第二个输入操作数,长度为 nb
461 * @param nb 第二个操作数的 limb 长度
462 * @warning na>=3*nb, nb>=20, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
463 * @return 无返回值,结果存储在dst中
464 */
466
467/**
468 * @brief Toom-43乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
469 * @param dst 输出结果缓冲区,长度至少为 na+nb
470 * @param numa 第一个输入操作数,长度为 na
471 * @param na 第一个操作数的 limb 长度
472 * @param numb 第二个输入操作数,长度为 nb
473 * @param nb 第二个操作数的 limb 长度
474 * @warning 1/2<nb/na<1, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
475 * @return 无返回值,结果存储在dst中
476 */
478
479/**
480 * @brief Toom-44乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
481 * @param dst 输出结果缓冲区,长度至少为 na+nb
482 * @param numa 第一个输入操作数,长度为 na
483 * @param na 第一个操作数的 limb 长度
484 * @param numb 第二个输入操作数,长度为 nb
485 * @param nb 第二个操作数的 limb 长度
486 * @warning 3/4<nb/na<=1, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
487 * @return 无返回值,结果存储在dst中
488 */
490
491/**
492 * @brief Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
493 * (非对称切分+条件inf点,原生支持不平衡;评估点
494 * inf,±4,±2,±1,±1/2,±1/4,0)
495 * @param dst 输出结果缓冲区,长度至少为 na+nb
496 * @param numa 第一个输入操作数,长度为 na
497 * @param na 第一个操作数的 limb 长度
498 * @param numb 第二个输入操作数,长度为 nb
499 * @param nb 第二个操作数的 limb 长度
500 * @warning 46<=nb<=na, na*6<nb*17, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
501 * @return 无返回值,结果存储在dst中
502 */
504
505/**
506 * @brief Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
507 * (非对称切分+条件inf点,原生支持不平衡;评估点
508 * inf,±8,±4,±2,±1,±1/2,±1/4,±1/8,0)
509 * @param dst 输出结果缓冲区,长度至少为 na+nb
510 * @param numa 第一个输入操作数,长度为 na
511 * @param na 第一个操作数的 limb 长度
512 * @param numb 第二个输入操作数,长度为 nb
513 * @param nb 第二个操作数的 limb 长度
514 * @warning 86<=nb<=na, na<=4*nb, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
515 * @return 无返回值,结果存储在dst中
516 */
518
519/**
520 * @brief Toom-52乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
521 * @param dst 输出结果缓冲区,长度至少为 na+nb
522 * @param numa 第一个输入操作数,长度为 na
523 * @param na 第一个操作数的 limb 长度
524 * @param numb 第二个输入操作数,长度为 nb
525 * @param nb 第二个操作数的 limb 长度
526 * @warning 1/5<nb/na<1/2, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
527 * @return 无返回值,结果存储在dst中
528 */
530
531/**
532 * @brief Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
533 * @param dst 输出结果缓冲区,长度至少为 na+nb
534 * @param numa 第一个输入操作数,长度为 na
535 * @param na 第一个操作数的 limb 长度
536 * @param numb 第二个输入操作数,长度为 nb
537 * @param nb 第二个操作数的 limb 长度
538 * @warning 2/5<nb/na<3/4, na>4*n, nb>2*n while n=max(ceil(na/5),ceil(nb/3))
539 * sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
540 * @return 无返回值,结果存储在dst中
541 */
543
544/**
545 * @brief Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
546 * @param dst 输出结果缓冲区,长度至少为 na+nb
547 * @param numa 第一个输入操作数,长度为 na
548 * @param na 第一个操作数的 limb 长度
549 * @param numb 第二个输入操作数,长度为 nb
550 * @param nb 第二个操作数的 limb 长度
551 * @warning 1/6<nb/na<2/5, na>5*n, nb>n while n=max(ceil(na/6),ceil(nb/2))
552 * sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
553 * @return 无返回值,结果存储在dst中
554 */
556
557/**
558 * @brief Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
559 * @param dst 输出结果缓冲区,长度至少为 na+nb
560 * @param numa 第一个输入操作数,长度为 na
561 * @param na 第一个操作数的 limb 长度
562 * @param numb 第二个输入操作数,长度为 nb
563 * @param nb 第二个操作数的 limb 长度
564 * @warning na>=5*nb, nb>=??, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
565 * @return 无返回值,结果存储在dst中
566 */
568
569/**
570 * @brief 计算满足 >=n 的最小费马/梅森乘法可行尺寸
571 * @param n 输入的目标尺寸
572 * @return 满足条件的SSA乘法最小尺寸
573 */
575
576/**
577 * @brief 计算满足 >=n 的最小分治梅森乘法可行尺寸
578 * @param n 输入的目标尺寸
579 * @return 满足条件的分治梅森乘法最小尺寸
580 * @note 梅森缓存和fft算法应该改用 lmmp_fft_next_size_
581 */
583
584/**
585 * @brief 费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
586 * @param dst 输出结果缓冲区,长度至少为 rn+1
587 * @param rn 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn);
588 * rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值
589 * @param numa 第一个输入操作数,长度为 na
590 * @param na 第一个操作数的 limb 长度
591 * @param numb 第二个输入操作数,长度为 nb
592 * @param nb 第二个操作数的 limb 长度
593 * @warning eqsep(dst,[numa|numb]), 0<=[numa,na]<2*B^rn, 0<=[numb,nb]<2*B^rn, lmmp_fft_next_size_(rn)==rn,
594 * dst!=NULL, numa!=NULL, numb!=NULL
595 * @note 如果[numa,na]==[numb,nb],请使用lmmp_sqr_fermat_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_fermat_函数
596 * @return 无返回值,结果存储在dst中
597 */
599
600/**
601 * @brief FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
602 * @param dst 输出结果缓冲区,长度至少为 rn
603 * @param rn 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn);
604 * rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为可容纳乘积的推荐最小值
605 * @param numa 第一个输入操作数,长度为 na
606 * @param na 第一个操作数的 limb 长度
607 * @param numb 第二个输入操作数,长度为 nb
608 * @param nb 第二个操作数的 limb 长度
609 * @warning eqsep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, lmmp_fft_next_size_(rn)==rn,
610 * dst!=NULL, numa!=NULL, numb!=NULL
611 * @note 如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_fft_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_fft_函数
612 * @return 无返回值,结果存储在dst中
613 */
615
616/**
617 * @brief 分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
618 * @param dst 输出结果缓冲区,长度至少为 rn
619 * @param rn 模运算的阶数参数
620 * @param numa 第一个输入操作数,长度为 na
621 * @param na 第一个操作数的 limb 长度
622 * @param numb 第二个输入操作数,长度为 nb
623 * @param nb 第二个操作数的 limb 长度
624 * @warning sep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, na+nb>rn/2, dst!=NULL, numa!=NULL, numb!=NULL
625 * @note 如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_dc_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_dc_函数
626 * @return 无返回值,结果存储在dst中
627 */
629
630/**
631 * @brief 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
632 * @param dst 输出结果缓冲区,长度至少为 rn
633 * @param rn 模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc);
634 * rn = lmmp_fft_next_size_((na + nb + 1) >> 1) 为进入 fft 档的推荐最小值
635 * @param numa 第一个输入操作数,长度为 na
636 * @param na 第一个操作数的 limb 长度
637 * @param numb 第二个输入操作数,长度为 nb
638 * @param nb 第二个操作数的 limb 长度
639 * @warning sep(dst,[numa|numb]), 0<=[numa,na]<B^rn, 0<=[numb,nb]<B^rn, dst!=NULL, numa!=NULL, numb!=NULL
640 * @note na/nb 大小序不限(内部按交换律规范化为 nb<=na);rn 对齐粒度不限
641 * (未达 fft 可行尺寸时即使超过阈值也回落 dc);
642 * 如果[numa,na]==[numb,nb],请使用lmmp_sqr_mersenne_函数,此函数不会检查操作数是否一致并跳转到lmmp_sqr_mersenne_函数;
643 * @return 无返回值,结果存储在dst中
644 */
646
647/**
648 * @brief SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
649 * @param dst 输出结果缓冲区,长度至少为 rn+1
650 * @param rn 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn);
651 * rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为可容纳乘积的推荐最小值
652 * @param numa 操作数,长度为 na
653 * @param na 操作数的 limb 长度
654 * @warning eqsep(dst,numa), 0<=[numa,na]<2*B^rn, lmmp_fft_next_size_(rn)==rn, dst!=NULL, numa!=NULL
655 * @return 无返回值,结果存储在dst中
656 */
658
659/**
660 * @brief FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
661 * @param dst 输出结果缓冲区,长度至少为 rn
662 * @param rn 模运算的阶数参数,须为 FFT 可行尺寸(lmmp_fft_next_size_(rn)==rn);
663 * rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为可容纳乘积的推荐最小值
664 * @param numa 输入操作数,长度为 na
665 * @param na 输入操作数的 limb 长度
666 * @warning eqsep(dst,numa), 0<=[numa,na]<B^rn, lmmp_fft_next_size_(rn)==rn, dst!=NULL, numa!=NULL
667 * @return 无返回值,结果存储在dst中
668 */
670
671/**
672 * @brief 分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
673 * @param dst 输出结果缓冲区,长度至少为 rn
674 * @param rn 模运算的阶数参数
675 * @param numa 输入操作数,长度为 na
676 * @param na 输入操作数的 limb 长度
677 * @warning sep(dst,numa), 0<=[numa,na]<B^rn, 4*na>rn, dst!=NULL, numa!=NULL
678 * @return 无返回值,结果存储在dst中
679 */
681
682/**
683 * @brief 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
684 * @param dst 输出结果缓冲区,长度至少为 rn
685 * @param rn 模运算的阶数参数,任意正尺寸均可(未对齐 fft 可行尺寸时回落 dc);
686 * rn = lmmp_fft_next_size_((2*na + 1) >> 1) 为进入 fft 档的推荐最小值
687 * @param numa 输入操作数,长度为 na
688 * @param na 输入操作数的 limb 长度
689 * @warning sep(dst,numa), 0<=[numa,na]<B^rn, dst!=NULL, numa!=NULL
690 * @return 无返回值,结果存储在dst中
691 */
693
694/**
695 * @brief FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
696 * @param dst 输出结果缓冲区,长度至少为 na+nb
697 * @param numa 第一个输入操作数,长度为 na
698 * @param na 第一个操作数的 limb 长度
699 * @param numb 第二个输入操作数,长度为 nb
700 * @param nb 第二个操作数的 limb 长度
701 * @warning ???<=nb<=na, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
702 * @return 无返回值,结果存储在dst中
703 */
705
706/**
707 * @brief FFT平方运算 [dst,2*na] = [numa,na]^2
708 * @param dst 输出结果缓冲区,长度至少为 2*na
709 * @param numa 输入操作数指针,长度为 na
710 * @param na 输入操作数的 limb 长度
711 * @warning ???<=na, sep(dst,numa), dst!=NULL, numa!=NULL
712 * @return 无返回值,结果存储在dst中
713 */
715
716/**
717 * @brief FFT不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
718 * @param dst 输出结果缓冲区,长度至少为 na+nb
719 * @param hn FFT模域参数
720 * @param numa 第一个输入操作数,长度为 na
721 * @param na 第一个操作数的 limb 长度
722 * @param numb 第二个输入操作数,长度为 nb
723 * @param nb 第二个操作数的 limb 长度
724 * @warning ???<=nb<=na, na>=3*nb, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
725 * @return 无返回值,结果存储在dst中
726 */
728
729/**
730 * @brief 平方操作 [dst,2*na] = [numa,na]^2
731 * @param dst 平方结果输出指针(需要2*na的limb长度)
732 * @param numa 输入操作数指针
733 * @param na 输入的 limb 长度
734 * @warning na>0, sep(dst,numa), dst!=NULL, numa!=NULL
735 * @return 无返回值,结果存储在dst中
736 */
738
739/**
740 * @brief 等长乘法操作 [dst,2*n] = [numa,n] * [numb,n]
741 * @param dst 乘积结果输出指针(需要 2*n 的 limb 长度)
742 * @param numa 第一个乘数指针
743 * @param numb 第二个乘数指针
744 * @param n limb长度
745 * @warning n>0, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
746 * @return 无返回值,结果存储在dst中
747 */
749
750/**
751 * @brief 不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
752 * @param dst 乘积结果输出指针(需要 na+nb 的 limb 长度)
753 * @param numa 第一个乘数指针(较长的操作数)
754 * @param na 第一个操作数的 limb 长度
755 * @param numb 第二个乘数指针(较短的操作数)
756 * @param nb 第二个操作数的 limb 长度
757 * @warning 0<nb<=na, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
758 * @return 无返回值,结果存储在dst中
759 */
761
762/**
763 * @brief 基础低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
764 * @param dst 输出结果缓冲区,长度至少为 n
765 * @param numa 第一个输入操作数,长度为 n
766 * @param numb 第二个输入操作数,长度为 n
767 * @param n limb长度
768 * @warning n>0, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
769 * @return 无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n
770 */
772
773/**
774 * @brief 基础低位平方 [dst,n] = [numa,n]^2 mod B^n
775 * @param dst 输出结果缓冲区,长度至少为 n
776 * @param numa 输入操作数,长度为 n
777 * @param n limb长度
778 * @warning n>0, sep(dst,numa), dst!=NULL, numa!=NULL
779 * @return 无返回值,结果存储在dst中,[dst,n]=[numa,n]^2 mod B^n
780 * @note 三角分解:上三角交叉积每对只乘一次(约 n^2/4 次 limb 乘法,
781 * 为 mullo(a,a) 的一半),末尾一趟融合的倍增+对角平方收尾
782 */
784
785/**
786 * @brief 低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
787 * @param dst 输出结果缓冲区,长度至少为 n
788 * @param numa 第一个输入操作数,长度为 n
789 * @param numb 第二个输入操作数,长度为 n
790 * @param n limb长度
791 * @warning n>0, sep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
792 * @return 无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n
793 */
795
796/**
797 * @brief 低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
798 * @param dst 输出结果缓冲区,长度至少为 n
799 * @param numa 第一个输入操作数,长度为 n
800 * @param numb 第二个输入操作数,长度为 n
801 * @param tp 临时缓冲区,长度至少为 2*n
802 * @param n limb长度
803 * @warning n>0, sep(dst,[numa|numb],tp), dst!=NULL, numa!=NULL, numb!=NULL
804 * @return 无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n
805 */
807
808/**
809 * @brief 低位平方 [dst,n] = [numa,n]^2 mod B^n
810 * @param dst 输出结果缓冲区,长度至少为 n
811 * @param numa 第一个输入操作数,长度为 n
812 * @param tp 临时缓冲区,长度至少为 2*n
813 * @param n limb长度
814 * @warning n>0, sep(dst,numa,tp), dst!=NULL, numa!=NULL, tp!=NULL
815 * @return 无返回值,结果存储在dst中,[dst,n]=[numa,n]^2 mod B^n
816 */
818
819/**
820 * @brief 低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
821 * @param dst 输出结果缓冲区,长度至少为 n
822 * @param numa 第一个输入操作数,长度为 n
823 * @param numb 第二个输入操作数,长度为 n
824 * @param scratch 临时缓冲区,长度至少为 2*n
825 * @param n 缓冲区 limb 长度
826 * @warning ???<n, sep(scratch,[numa|numb]), eqsep(dst,scratch)
827 * @return 无返回值,结果存储在dst中,[dst,n]=[numa,n] * [numb,n] mod B^n
828 */
830
831/**
832 * @brief 1阶逆元计算 (inv1)
833 * @param x 输入的64位无符号整数,最高位为1(MSB(x)=1)
834 * @return 计算结果:(B^2-1)/x - B
835 * @warning MSB(x)=1, 即x>=2^63
836 */
838
839/**
840 * @brief 2-1阶逆元计算 (inv21)
841 * @param xh 输入数的高64位部分
842 * @param xl 输入数的低64位部分
843 * @return 计算结果:(B^3-1)/(xh*B+xl) - B
844 * @warning MSB(xh)=1, 即xh>=2^63
845 */
847
848/**
849 * @brief 近似逆元计算
850 * @param dst 输出结果缓冲区,长度为na
851 * @param numa 输入操作数,长度为na
852 * @param na 输入操作数的 limb 长度
853 * @warning na>0, MSB(numa)=1, sep(dst,numa), dst!=NULL, numa!=NULL
854 * @return 无返回值,结果存储在dst中,[dst,na]=(B^(2*na)-1)/[numa,na] - B^na
855 */
857
858/**
859 * @brief 近似逆元计算(牛顿迭代法)
860 * @param dst 输出结果缓冲区,长度为na
861 * @param numa 输入操作数,长度为na
862 * @param na 输入操作数的 limb 长度
863 * @warning na>4, MSB(numa)=1, sep(dst,numa), dst!=NULL, numa!=NULL
864 * @return 无返回值,结果存储在dst中,[dst,na]=(B^(2*na)-1)/[numa,na]-B^na+[0|-1]
865 */
867
868/**
869 * @brief 近似逆元计算 (invappr)
870 * @param dst 输出结果缓冲区,长度为na
871 * @param numa 输入操作数,长度为na
872 * @param na 输入操作数的 limb 长度
873 * @warning na>0, MSB(numa)=1, sep(dst,numa), dst!=NULL, numa!=NULL
874 * @return 无返回值,结果存储在dst中,[dst,na] = (B^(2*na)-1)/[numa,na] - B^na + [0|-1]
875 */
877
878/**
879 * @brief 3/2位除法运算 [numa,2]=[numa,3] mod [numb,2]
880 * @param numa 输入被除数(长度3),运算后存储余数(长度2)
881 * @param numb 输入除数(长度2)
882 * @param inv21 除数的2-1阶逆元(提前计算好的inv21([numb,2]))
883 * @warning [numa,3]<[numb,2]*B, MSB(numb)=1, inv21=inv21([numb,2]), eqsep(numa,numb), numb!=NULL, numa!=NULL
884 * @return 商值(单精度数)
885 */
887
888/**
889 * @brief 单精度数除法
890 * @param dstq 输出商的缓冲区(可为NULL,此时仅计算余数)
891 * @param numa 输入被除数,长度为na
892 * @param na 被除数的 limb 长度
893 * @param x 除数(单个 limb )
894 * @return 除法余数(单个 limb )
895 * @warning na>0, x!=0, eqsep(dstq,numa),
896 * @warning eqsep(numa,dstq), numa!=NULL, na>0, x>0, dstq>=numa-1 是可以接受的
897 * @note if (dstq!=NULL) [dstq,na] = [numa,na] div x
898 */
900
901/**
902 * @brief 单精度数取余
903 * @param numa 输入被除数,长度为na
904 * @param na 被除数的 limb 长度
905 * @param x 除数(单个 limb )
906 * @return 除法余数(单个 limb )
907 * @warning na>0, x!=0, numa!=NULL
908 */
910
911/**
912 * @brief 单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
913 * @param numa 输入被除数,长度为na
914 * @param na 被除数的 limb 长度
915 * @param x 除数(单个 limb )
916 * @param inv 预计算逆元 lmmp_inv_1_(x<<k)
917 * @param k 预计算移位量 lmmp_leading_zeros_(x)
918 * @return 除法余数(单个 limb )
919 * @warning na>0, x!=0, numa!=NULL, k=lmmp_leading_zeros_(x), inv=lmmp_inv_1_(x<<k)
920 * @note 同一 x 反复取模时(如固定素数逐候选判整除),预处理一次、多次调用本函数,
921 * 省去每次调用的 clz/归一化/lmmp_inv_1_ 开销
922 */
924 mp_limb_t k);
925
926/**
927 * @brief 双精度数除法 (除数为2个limb)
928 * @param dstq 输出商的缓冲区,长度至少为na-1(可为NULL,此时仅计算余数)
929 * @param numa 输入被除数(长度na)
930 * @param na 被除数的 limb 长度
931 * @param numb 输入除数(长度2)[numb,2]=[numa,na] mod [numb,2]
932 * @warning na>=2, numb[1]!=0, eqsep(dstq,numa), numa!=NULL, numb!=NULL, dstq>=numa 是可以接受的
933 * @note if (dstq!=NULL) [dstq,na-1]=[numa,na] div [numb,2]
934 */
936
937/**
938 * @brief 双精度数取余 (除数为2个limb)
939 * @param numa 输入被除数(长度na)
940 * @param na 被除数的 limb 长度
941 * @param numb 输入除数(长度2)[numb,2]=[numa,na] mod [numb,2]
942 * @warning na>=2, numb[1]!=0, numb!=NULL, numa!=NULL
943 */
945
946/**
947 * @brief 基础除法运算
948 * @param dstq 输出商的缓冲区,长度至少为na-nb
949 * @param numa 输入被除数(长度na),运算后存储余数(长度nb)
950 * @param na 被除数的 limb 长度
951 * @param numb 输入除数,长度为nb
952 * @param nb 除数的 limb 长度
953 * @param inv21 除数的2-1阶逆元(inv21([numb+nb-2,2]))
954 * @return 商的最高位(qh)
955 * @warning na>=nb>=3, MSB(numb)=1, inv21=inv21([numb+nb-2,2]), sep(dstq,numa,numb),
956 * dstq!=NULL, numa!=NULL, numb!=NULL
957 * @note qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,na-nb]=[numa,na] mod [numb,nb], return qh
958 */
961
962/**
963 * @brief 分治除法运算
964 * @param dstq 输出商的缓冲区,长度至少为na-nb
965 * @param numa 输入被除数(长度na),运算后存储余数(长度nb)
966 * @param na 被除数的 limb 长度
967 * @param numb 输入除数,长度为nb
968 * @param nb 除数的 limb 长度
969 * @param inv21 除数的2-1阶逆元(inv21([numb+nb-2,2]))
970 * @return 商的最高位(qh)
971 * @warning na>=2*nb, nb>=6, MSB(numb)=1, inv21=inv21([numb+nb-2,2]), sep(dstq,numa,numb),
972 * dstq!=NULL, numa!=NULL, numb!=NULL
973 * @note qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,na-nb]=[numa,na] mod [numb,nb], return qh
974 */
977
978/**
979 * @brief 计算预计算逆元的尺寸
980 * @param nq 商的 limb 长度
981 * @param nb 除数的 limb 长度
982 * @return 计算需要预计算逆元尺寸ni(ni<=nb)
983 * @note 用于已归一化除法([nq+nb]/[nb]=[nq])的逆元 ni 尺寸
984 */
986 mp_size_t ni, b;
987 if (nq > nb) {
988 b = (nq - 1) / nb + 1; // ceil(nq/nb), number of blocks
989 ni = (nq - 1) / b + 1; // ceil(nq/b)
990 } else if (3 * nq > nb) {
991 ni = (nq - 1) / 2 + 1; // b=2
992 } else {
993 ni = (nq - 1) / 1 + 1; // b=1
994 }
995 return ni;
996}
997
998/**
999 * @brief 除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
1000 * @param dst 输出预计算逆元的缓冲区,长度为ni
1001 * @param numa 输入操作数,长度为na
1002 * @param na 输入操作数的 limb 长度
1003 * @param ni 预计算逆元的目标尺寸
1004 * @warning na>=ni>0, MSB(numa)=1, eqsep(dst,numa), dst!=NULL, numa!=NULL
1005 * @note if (ni=na) [dst,na] = (B^(2*na)-1) / [numa,na] - B^na
1006 */
1008
1009/**
1010 * @brief 求逆操作 [dst,na+nf+1] = (B^(2*(na+nf)) - 1) / ([numa,na]*B^nf) + [0|-1]
1011 * @param dst 逆元结果输出指针
1012 * @param numa 源操作数指针
1013 * @param na 操作数的 limb 长度
1014 * @param nf 精度因子
1015 * @warning na>0, numa[na-1]!=0, eqsep(dst,numa), dst!=NULL, numa!=NULL
1016 */
1017LMMP_API void lmmp_inv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t nf);
1018
1019/**
1020 * @brief 近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]
1021 * @param dstq 输出逆元的缓冲区,长度至少为na+ni+2
1022 * @param numa 输入指针(长度na)
1023 * @param na 输入指针的 limb 长度
1024 * @param ni 精度因子
1025 * @warning na>0, sep(dstq,numa), dstq!=NULL, numa[na-1]!=0, dstq!=NULL, numa!=NULL
1026 * @note 也就是计算 B^(2*na+ni) div [numa,na] + [0|-ept],存在接近2^-64的绝对误差
1027 */
1029
1030/**
1031 * @brief 乘法逆元除法
1032 * @param dstq 输出商的缓冲区,长度至少为na-nb
1033 * @param numa 输入被除数(长度na),运算后存储余数(长度nb)
1034 * @param na 被除数的 limb 长度
1035 * @param numb 输入除数,长度为nb
1036 * @param nb 除数的 limb 长度
1037 * @param invappr 预计算的近似逆元,长度为ni
1038 * @param ni 预计算逆元的 limb 长度
1039 * @return 商的最高位(qh)
1040 * @warning na>=nb>=ni>0, MSB(numb)=1, [invappr,ni]=inv_prediv([numb,nb]), sep(dstq,numa,numb,invappr))
1041 * dstq!=NULL, numa!=NULL, numb!=NULL, invappr!=NULL
1042 * @note qh:[dstq,na-1]=[numa,na] div x, [numa,1]=[numa,na] mod x, return qh
1043 */
1046
1047/**
1048 * @brief 单精度数除法(除数为1个limb)
1049 * @param dstq 输出商的缓冲区,长度至少为na-1
1050 * @param numa 输入被除数(长度na),运算后存储余数(长度1)
1051 * @param na 被除数的 limb 长度
1052 * @param x 除数(单个 limb )
1053 * @return 商的最高位(qh)
1054 * @warning na>1, MSB(x)=1, sep(dstq,numa), dstq!=NULL, numa!=NULL
1055 * @note qh:[dstq,na-1]=[numa,na] div x, [numa,1]=[numa,na] mod x, return qh
1056 */
1058
1059/**
1060 * @brief 双精度数除法(除数为2个limb)
1061 * @param dstq 输出商的缓冲区,长度至少为na-2
1062 * @param numa 输入被除数(长度na),运算后存储余数(长度2)
1063 * @param na 被除数的 limb 长度
1064 * @param numb 输入除数,长度为2
1065 * @return 商的最高位(qh)
1066 * @warning na>2, MSB(numb)=1, sep(dstq,numa,numb), dstq!=NULL, numa!=NULL, numb!=NULL
1067 * @note qh:[dstq,na-2]=[numa,na] div [numb,2], [numa,2]=[numa,na] mod [numb,2], return qh
1068 */
1070
1071/**
1072 * @brief 除法运算
1073 * @param dstq 输出商的缓冲区,长度至少为na-nb
1074 * @param numa 输入被除数(长度na),运算后存储余数(长度nb)
1075 * @param na 被除数的 limb 长度
1076 * @param numb 输入除数,长度为nb
1077 * @param nb 除数的 limb 长度
1078 * @return 商的最高位(qh)
1079 * @warning na>=nb>0, MSB(numb)=1, sep(dstq,numa,numb), dstq!=NULL, numa!=NULL, numb!=NULL
1080 * @note qh:[dstq,na-nb]=[numa,na] div [numb,nb], [numa,nb]=[numa,na] mod [numb,nb], return qh
1081 */
1083
1084/**
1085 * @brief 除法和取模操作
1086 * @param dstq 商结果输出指针(NULL表示不计算商)
1087 * @param dstr 余数结果输出指针(NULL表示不计算余数)
1088 * @param numa 被除数指针
1089 * @param na 被除数的 limb 长度
1090 * @param numb 除数指针
1091 * @param nb 除数的 limb 长度
1092 * @warning 0<nb<=na, numb[nb-1]!=0, sep(dstq,[numa|numb]), eqsep(dstr,[numa|numb]))
1093 * numa!=NULL, numb!=NULL
1094 * 特殊情况: nb==1时, dstq>=numa-1 是允许的
1095 * nb==2时, dstq>=numa 是允许的
1096 * @note 如果dstq不为NULL: [dstq,na-nb+1] = [numa,na] / [numb,nb] (商)
1097 * 如果dstr不为NULL: [dstr,nb] = [numa,na] mod [numb,nb] (余数)
1098 */
1099LMMP_API void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb);
1100
1101/**
1102 * @brief加1宏(预期无进位)
1103 * @param p 指针
1104 * @note 从最低位开始加1,直到遇到非零值(预期无进位溢出)
1105 */
1106#define lmmp_inc(p) \
1107 do { \
1108 mp_ptr _p_ = (p); \
1109 while (++(*(_p_++)) == 0); \
1110 } while (0)
1111
1112/**
1113 * @brief 加指定值宏(预期无进位)
1114 * @param p 指针
1115 * @param inc 要加的单精度数值
1116 * @note 先加最低位,若产生进位则逐位加1,直到无进位(预期无溢出)
1117 */
1118#define lmmp_inc_1(p, inc) \
1119 do { \
1120 mp_ptr _p_ = (p); \
1121 mp_limb_t _inc_ = (inc), _x_; \
1122 _x_ = *_p_ + _inc_; \
1123 *_p_ = _x_; \
1124 if (_x_ < _inc_) \
1125 while (++(*(++_p_)) == 0); \
1126 } while (0)
1127
1128/**
1129 * @brief 减1宏(预期无借位)
1130 * @param p 指针
1131 * @note 从最低位开始减1,直到遇到非零值(预期无借位溢出)
1132 */
1133#define lmmp_dec(p) \
1134 do { \
1135 mp_ptr _p_ = (p); \
1136 while ((*(_p_++))-- == 0); \
1137 } while (0)
1138
1139/**
1140 * @brief 减指定值宏(预期无借位)
1141 * @param p 指针
1142 * @param dec 要减的单精度数值
1143 * @note 先减最低位,若产生借位则逐位减1,直到无借位(预期无溢出)
1144 */
1145#define lmmp_dec_1(p, dec) \
1146 do { \
1147 mp_ptr _p_ = (p); \
1148 mp_limb_t _dec_ = (dec), _x_; \
1149 _x_ = *_p_; \
1150 *_p_ = _x_ - _dec_; \
1151 if (_x_ < _dec_) \
1152 while ((*(++_p_))-- == 0); \
1153 } while (0)
1154
1155/**
1156 * @brief 比较函数
1157 * @param numa 第一个指针,长度为n
1158 * @param numb 第二个指针,长度为n
1159 * @param n 比较两数的 limb 长度
1160 * @return 1(numa>numb) / 0(numa==numb) / -1(numa<numb)
1161 * @warning n>0, numa!=NULL, numb!=NULL
1162 * @note 从最高位开始逐位比较,直到找到不同位。
1163 */
1165
1166/**
1167 * @brief 判零函数
1168 * @param p 指针
1169 * @param n 数的 limb 长度
1170 * @return 1(全零) / 0(非零)
1171 * @warning n>0, p!=NULL
1172 * @note 从最高位开始检查,只要有非零位则返回0。
1173 */
1175
1176#if defined(__GNUC__) && !defined(__clang__) && __GNUC__ >= 15
1177 #define LMMP_NOVECTOR _Pragma("GCC novector")
1178#else
1179 #define LMMP_NOVECTOR
1180#endif
1181
1182#define LMMP_AORS_(FUNCTION, TEST) \
1183 mp_limb_t _x_; \
1184 if (FUNCTION(dst, numa, numb, nb)) { \
1185 LMMP_NOVECTOR \
1186 do { \
1187 if (nb >= na) \
1188 return 1; \
1189 _x_ = numa[nb]; \
1190 } while (TEST); \
1191 } \
1192 if (dst != numa && na != nb) \
1193 lmmp_copy(dst + nb, numa + nb, na - nb); \
1194 return 0
1195
1196/**
1197 * @brief 加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
1198 * @param dst 输出结果缓冲区,存储numa + numb
1199 * @param numa 第一个加数,长度为na
1200 * @param na 第一个加数的 limb 长度
1201 * @param numb 第二个加数,长度为nb
1202 * @param nb 第二个加数的 limb 长度
1203 * @return 进位标志(1表示有进位,0表示无进位)
1204 * @warning 0<nb<=na, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
1205 */
1207 LMMP_AORS_(lmmp_add_n_, ((dst[nb++] = _x_ + 1) == 0));
1208}
1209
1210/**
1211 * @brief 减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
1212 * @param dst 输出结果缓冲区,存储numa - numb
1213 * @param numa 被减数,长度为na
1214 * @param na 被减数的 limb 长度
1215 * @param numb 减数,长度为nb
1216 * @param nb 减数的 limb 长度
1217 * @return 借位标志(1表示有借位,0表示无借位)
1218 * @warning 0<nb<=na, eqsep(dst,[numa|numb]), dst!=NULL, numa!=NULL, numb!=NULL
1219 */
1221 LMMP_AORS_(lmmp_sub_n_, ((dst[nb++] = _x_ - 1), _x_ == 0));
1222}
1223
1224#undef LMMP_AORS_
1225
1226// 单精度加减运算通用宏:封装单精度加减的公共逻辑
1227#define LMMP_AORS_1_(OP, CB) \
1228 mp_size_t _i_ = 1; \
1229 mp_limb_t _x_ = numa[0], _r_ = _x_ OP x; \
1230 dst[0] = _r_; \
1231 if (CB(_r_, _x_, x)) { \
1232 do { \
1233 if (_i_ >= na) \
1234 return 1; \
1235 _x_ = numa[_i_]; \
1236 _r_ = _x_ OP 1; \
1237 dst[_i_] = _r_; \
1238 ++_i_; \
1239 } while (CB(_r_, _x_, 1)); \
1240 } \
1241 if (numa != dst && na != _i_) \
1242 lmmp_copy(dst + _i_, numa + _i_, na - _i_); \
1243 return 0
1244
1245// 加法进位判断宏:判断加法是否产生进位
1246#define LMMP_ADDCB_(r, x, y) ((r) < (y))
1247// 减法借位判断宏:判断减法是否产生借位
1248#define LMMP_SUBCB_(r, x, y) ((x) < (y))
1249
1250/**
1251 * @brief 加单精度数静态内联函数 [dst,na]=[numa,na]+x
1252 * @param dst 输出结果缓冲区,存储numa + x
1253 * @param numa 被加数,长度为na
1254 * @param na 被加数的 limb 长度
1255 * @param x 加数(单个 limb )
1256 * @return 进位标志(1表示有进位,0表示无进位)
1257 * @warning na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL
1258 */
1262
1263/**
1264 * @brief 减单精度数静态内联函数 [dst,na]=[numa,na]-x
1265 * @param dst 输出结果缓冲区,存储numa - x
1266 * @param numa 被减数,长度为na
1267 * @param na 被减数的 limb 长度
1268 * @param x 减数(单个 limb )
1269 * @return 借位标志(1表示有借位,0表示无借位)
1270 * @warning na>0, eqsep(dst,numa), dst!=NULL, numa!=NULL
1271 */
1275
1276/**
1277 * @brief 计算转换为字节数组,字节数组需要的缓冲区长度
1278 * @param numa 输入指针,长度为na
1279 * @param na 输入的 limb 长度
1280 * @param base 目标基数(2~256)
1281 * @warning na>=0, 2<=base<=256
1282 * @note 将会忽略numa的前导零,
1283 * 1. if (numa!=NULL) 返回的长度可能会多分配一个字节
1284 * 2. if (numa==NULL) 返回na个limb长度的数的最大可能字节长度(最坏情况)
1285 * @return 在指定基数下的位数
1286 */
1288
1289/**
1290 * @brief 计算字节数组转limb数组所需的 limb 缓冲区长度
1291 * @param src 输入字节数组指针
1292 * @param len 字节数组长度
1293 * @param base 字节数组的基数(2~256)
1294 * @return 存储该字节数组数值所需的 limb 缓冲区长度
1295 * @warning len>=0, 2<=base<=256
1296 * @note 将会忽略前导零,
1297 * 1. if (src!=NULL) 返回的长度可能会多分配一个 limb 空间
1298 * 2. if (src==NULL) 返回len位base进制数的最大可能 limb 长度(最坏情况)
1299 */
1300LMMP_API mp_size_t lmmp_from_str_len_(const mp_byte_t* src, mp_size_t len, int base);
1301
1302/**
1303 * @brief 字节数组转limb数组操作 [src,len,base] to [dst,return value,B]
1304 * @param dst 结果输出指针
1305 * @param src 字节数组源指针
1306 * @param len 字节数组长度
1307 * @param base 字节数组的进制基数
1308 * @warning len>=0, 2<=base<=256, dst!=NULL, src!=NULL
1309 * @return 转换后的结果的 limb 长度
1310 */
1311LMMP_API mp_size_t lmmp_from_str_(mp_ptr dst, const mp_byte_t* src, mp_size_t len, int base);
1312
1313/**
1314 * @brief limb数组转字节数组操作 [numa,na,B] to [dst,return value,base]
1315 * @param dst 字节数组结果输出指针
1316 * @param numa 输入指针
1317 * @param na 输入的 limb 长度
1318 * @param base 目标字节数组的进制基数
1319 * @warning na>=0, 2<=base<=256, dst!=NULL, numa!=NULL
1320 * @return 转换后的字节数组长度
1321 */
1323
1324/**
1325 * @brief 十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']
1326 * @param dst 输入数字字节数组,同时也是字符输出数组
1327 * @param n 字节数组长度
1328 * @warning n>=0, dst!=NULL, 0<=dst[i]<=9
1329 * @note 原地操作,数值数组转化成字符串
1330 */
1332
1333/**
1334 * @brief 36进制数字字节原地转字符 [dst,n]: [0,35] -> ['0'-'9','a'-'z']或['0'-'9','A'-'Z']
1335 * @param dst 输入数字字节数组,同时也是字符输出数组
1336 * @param n 字节数组长度
1337 * @param upper 大小写选择:true输出大写字母,false输出小写字母
1338 * @warning n>=0, dst!=NULL, 0<=dst[i]<=35
1339 * @note 原地操作,数值数组转化成字符串
1340 */
1341LMMP_API void lmmp_b36_to_chars_(mp_byte_t* dst, mp_size_t n, bool upper);
1342
1343/**
1344 * @brief 计算转换为十六进制字符串需要的缓冲区长度
1345 * @param numa 输入指针,长度为na
1346 * @param na 输入的 limb 长度
1347 * @warning na>=0
1348 * @note 将会忽略numa的前导零limb,
1349 * 1. if (numa!=NULL) 返回精确的十六进制字符长度(零值返回0)
1350 * 2. if (numa==NULL) 返回na个limb长度的数的最大可能字符长度(最坏情况)
1351 * @return 十六进制字符数
1352 */
1354
1355/**
1356 * @brief limb数组转十六进制字符串 [numa,na,B] to [dst,return value,16]
1357 * @param dst 字符串输出指针
1358 * @param numa 输入指针
1359 * @param na 输入的 limb 长度
1360 * @param upper 大小写选择:true输出大写字母,false输出小写字母
1361 * @warning na>=0, dst!=NULL, numa!=NULL
1362 * @note 低位digit(nibble)在数组前端;小端序平台下与字节串布局一致,
1363 * 输出长度恰好为 lmmp_to_hex_len_(numa,na)
1364 * @return 转换后的字符串长度(零值返回0)
1365 */
1366LMMP_API mp_size_t lmmp_to_hex_(char* dst, mp_srcptr numa, mp_size_t na, bool upper);
1367
1368/**
1369 * @brief 计算十六进制字符串转limb数组所需的 limb 缓冲区长度
1370 * @param src 输入字符串指针
1371 * @param len 字符串长度
1372 * @warning len>=0
1373 * @note 将会忽略字符串末尾的'0'(值前导零),
1374 * 1. if (src!=NULL) 返回精确的 limb 长度(零值返回0)
1375 * 2. if (src==NULL) 返回len个字符的最大可能 limb 长度(最坏情况)
1376 * @return 所需的 limb 缓冲区长度
1377 */
1378LMMP_API mp_size_t lmmp_from_hex_len_(const char* src, mp_size_t len);
1379
1380/**
1381 * @brief 十六进制字符串转limb数组 [src,len,16] to [dst,return value,B]
1382 * @param dst 结果输出指针
1383 * @param src 字符串源指针
1384 * @param len 字符串长度
1385 * @warning len>=0, dst!=NULL, src!=NULL, src[i] in {'0'-'9','a'-'f','A'-'F'}
1386 * @note 低位digit(nibble)在数组前端;将忽略末尾的'0';将会忽略大小写,'a'等同于'A'
1387 * @return 转换后的结果的 limb 长度(零值返回0)
1388 */
1389LMMP_API mp_size_t lmmp_from_hex_(mp_ptr dst, const char* src, mp_size_t len);
1390
1391/**
1392 * @brief 计算转换为十进制字符串需要的缓冲区长度
1393 * @param numa 输入指针,长度为na
1394 * @param na 输入的 limb 长度
1395 * @warning na>=0
1396 * @note 将会忽略numa的前导零limb,
1397 * 1. if (numa!=NULL) 返回的长度可能会多分配一个字节
1398 * 2. if (numa==NULL) 返回na个limb长度的数的最大可能字符长度(最坏情况)
1399 * @return 十进制字符数的上界
1400 */
1402
1403/**
1404 * @brief limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]
1405 * @param dst 字符串输出指针
1406 * @param numa 输入指针
1407 * @param na 输入的 limb 长度
1408 * @warning na>=0, dst!=NULL, numa!=NULL
1409 * @note 低位digit在数组前端,数值与字符转换一次遍历完成
1410 * @return 转换后的字符串长度(零值返回0)
1411 */
1413
1414/**
1415 * @brief 计算十进制字符串转limb数组所需的 limb 缓冲区长度
1416 * @param src 输入字符串指针
1417 * @param len 字符串长度
1418 * @warning len>=0
1419 * @note 将会忽略字符串末尾的'0'(值前导零),
1420 * 1. if (src!=NULL) 零值返回0,其余情况返回的长度可能会多分配一个 limb 空间
1421 * 2. if (src==NULL) 返回len个字符的最大可能 limb 长度(最坏情况)
1422 * @return 所需的 limb 缓冲区长度上界
1423 */
1425
1426/**
1427 * @brief 十进制字符串转limb数组 [src,len,10] to [dst,return value,B]
1428 * @param dst 结果输出指针
1429 * @param src 字符串源指针
1430 * @param len 字符串长度
1431 * @warning len>=0, dst!=NULL, src!=NULL, src[i] in {'0'-'9'}
1432 * @note 低位digit在数组前端;将忽略末尾的'0';
1433 * dst 需要 lmmp_from_decimal_len_(src,len) 的长度(转换过程中作为临时空间使用)
1434 * @return 转换后的结果的 limb 长度(零值返回0)
1435 */
1436LMMP_API mp_size_t lmmp_from_decimal_(mp_ptr dst, const char* src, mp_size_t len);
1437
1438/**
1439 * @brief 提取高位指定位数,并返回低位bits位数
1440 * @param num 待提取的指针
1441 * @param n num的 limb 长度
1442 * @param bits 待提取的位数(1-64)
1443 * @param ext 提取结果输出指针
1444 * @warning n>0, 1<=bits<=64, ext!=NULL, num!=NULL
1445 * @note 如果bits大于num的实际位数,则不会保证ext有效位数为bits位;
1446 * 如果bits小于等于num的实际位数,则ext将会有bits位有效位数。
1447 * @return 剩余的低位bits数量
1448 */
1450
1451#ifdef __cplusplus
1452} // extern "C"
1453#endif
1454
1455#undef LMMP_ADDCB_
1456#undef LMMP_SUBCB_
1457#undef LMMP_AORS_1_
1458
1459
1460#undef LMMP_INLINE
1461
1462#endif // LMMP_LMMPN_H
#define k
#define an
#define lmmp_limb_bits_
#define lmmp_leading_zeros_
#define lmmp_mul_n_
#define lmmp_mullh_
#define lmmp_sqr_
#define lmmp_limb_popcnt_
#define lmmp_tailing_zeros_
#define lmmp_mulh_
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint8_t mp_byte_t
定义 lmmp.h:91
#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
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t lmmp_shlnot_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移后按位取反操作 [dst,na] = ~([numa,na] << shl),dst的低shl位填充1
#define LMMP_SUBCB_(r, x, y)
mp_limb_t lmmp_div_3_2_(mp_ptr numa, mp_srcptr numb, mp_limb_t inv21)
3/2位除法运算 [numa,2]=[numa,3] mod [numb,2]
void lmmp_b36_to_chars_(mp_byte_t *dst, mp_size_t n, bool upper)
36进制数字字节原地转字符 [dst,n]: [0,35] -> ['0'-'9','a'-'z']或['0'-'9','A'-'Z']
void lmmp_mul_toom22_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-22乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_div_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法运算
void lmmp_invappr_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算 (invappr)
static mp_size_t lmmp_div_inv_size_(mp_size_t nq, mp_size_t nb)
计算预计算逆元的尺寸
mp_limb_t lmmp_div_1_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_limb_t x)
单精度数除法(除数为1个limb)
mp_limb_t lmmp_div_1_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数除法
定义 div.c:137
void lmmp_mul_toom44_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-44乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
#define LMMP_AORS_(FUNCTION, TEST)
void lmmp_mul_toom6h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-6.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±4,...
void lmmp_mul_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
分治梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_mul_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
mp_limb_t lmmp_shr1add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位加法后右移1位 [dst,n] = ([numa,n] + [numb,n] + c) >> 1
定义 shr.c:53
mp_limb_t lmmp_shr_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr, mp_limb_t c)
带进位的右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充c的高shr位
定义 shr.c:39
mp_limb_t lmmp_shr1add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法后右移1位 [dst,n] = ([numa,n] + [numb,n]) >> 1
定义 shr.c:65
mp_limb_t lmmp_addmul_2_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_srcptr bp)
乘以双limb并累加 [numa,n] += [numb,n] * [bp,2]
定义 mul_1.c:99
mp_size_t lmmp_to_hex_len_(mp_srcptr numa, mp_size_t na)
计算转换为十六进制字符串需要的缓冲区长度
mp_size_t lmmp_from_hex_len_(const char *src, mp_size_t len)
计算十六进制字符串转limb数组所需的 limb 缓冲区长度
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
mp_size_t lmmp_to_decimal_(char *dst, mp_srcptr numa, mp_size_t na)
limb数组转十进制字符串 [numa,na,B] to [dst,return value,10]
void lmmp_mul_toom42_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqrlo_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t n)
基础低位平方 [dst,n] = [numa,n]^2 mod B^n
void lmmp_inv_prediv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t ni)
除法前的逆元预计算,[dst,ni] = invappr( (ni+1 MSLs of numa) + 1 ) / B
void lmmp_mul_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT 梅森数模乘法 [dst,rn] = [numa,na]*[numb,nb] mod B^rn-1
void lmmp_div_2_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数除法 (除数为2个limb)
定义 div.c:294
void lmmp_sqr_toom8_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-8平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±8,±4,±2,±1,±1/2,±1/4,±1/8,0,无inf点)
void lmmp_sqr_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
基础平方运算 [dst,2*na] = [numa,na]^2
mp_limb_t lmmp_mod_preinv_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x, mp_limb_t inv, mp_limb_t k)
单精度数取余(预备逆元版) [numa,na] mod x,同 lmmp_mod_1_
定义 div.c:89
void lmmp_mul_toom42_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-42不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_mersenne_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_mullo_dc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_ptr tp, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
void lmmp_mullo_basecase_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
基础低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
mp_limb_t lmmp_subshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法结合左移1位操作 [dst,n] = [numa,n] - ([numb,n] << 1)
定义 shl.c:80
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
mp_bitcnt_t lmmp_extract_bits_(mp_srcptr num, mp_size_t n, mp_limb_t *ext, int bits)
提取高位指定位数,并返回低位bits位数
mp_size_t lmmp_from_decimal_(mp_ptr dst, const char *src, mp_size_t len)
十进制字符串转limb数组 [src,len,10] to [dst,return value,B]
void lmmp_mul_toom43_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-43乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
mp_size_t lmmp_to_str_(mp_byte_t *dst, mp_srcptr numa, mp_size_t na, int base)
limb数组转字节数组操作 [numa,na,B] to [dst,return value,base]
mp_size_t lmmp_to_hex_(char *dst, mp_srcptr numa, mp_size_t na, bool upper)
limb数组转十六进制字符串 [numa,na,B] to [dst,return value,16]
void lmmp_mod_2_(mp_srcptr numa, mp_size_t na, mp_ptr numb)
双精度数取余 (除数为2个limb)
定义 div.c:215
#define LMMP_AORS_1_(OP, CB)
void lmmp_dec_to_chars_(mp_byte_t *dst, mp_size_t n)
十进制数字字节原地转字符 [dst,n]: [0,9] -> ['0','9']
void lmmp_mul_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
基础乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
#define LMMP_INLINE
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 lmmpn.h:30
void lmmp_sqr_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
FFT平方运算 [dst,2*na] = [numa,na]^2
mp_size_t lmmp_from_str_(mp_ptr dst, const mp_byte_t *src, mp_size_t len, int base)
字节数组转limb数组操作 [src,len,base] to [dst,return value,B]
void lmmp_sqr_mersenne_fft_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
FFT 梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
void lmmp_mul_toom32_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-32乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_size_t lmmp_to_str_len_(mp_srcptr numa, mp_size_t na, int base)
计算转换为字节数组,字节数组需要的缓冲区长度
void lmmp_mul_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
费马数模乘法 [dst,rn+1]=[numa,na]*[numb,nb] mod B^rn+1
void lmmp_sqr_fermat_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
SSA FFT 版费马数模平方 [dst,rn+1]=[numa,na]^2 mod B^rn+1
void lmmp_invappr_newton_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算(牛顿迭代法)
void lmmp_mul_toom52_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-52乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_shl_c_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl, mp_limb_t c)
带进位的左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充c的低shl位
定义 shl.c:39
mp_limb_t lmmp_addshl1_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
加法结合左移1位操作 [dst,n] = [numa,n] + ([numb,n] << 1)
定义 shl.c:53
void lmmp_mul_toom62_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom2_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-2平方运算 [dst,2*na] = [numa,na]^2
mp_limb_t lmmp_add_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带进位的n位加法 [dst,n] = [numa,n] + [numb,n] + c
定义 add_n.c:58
void lmmp_sqr_toom3_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-3平方运算 [dst,2*na] = [numa,na]^2
void lmmp_mul_fft_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
mp_limb_t lmmp_shr1sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位减法后右移1位 [dst,n] = ([numa,n] - [numb,n] - c) >> 1
定义 shr.c:69
void lmmp_bninv_(mp_ptr dstq, mp_srcptr numa, mp_size_t na, mp_size_t ni)
近似逆元计算 [dstq,na+ni+2] = B^(2*(na+ni)) / ([numa,na] * B^ni) + [0|-ept]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
mp_size_t lmmp_fft_next_size_(mp_size_t n)
计算满足 >=n 的最小费马/梅森乘法可行尺寸
void lmmp_sqrlo_dc_(mp_ptr dst, mp_srcptr numa, mp_ptr tp, mp_size_t n)
低位平方 [dst,n] = [numa,n]^2 mod B^n
int lmmp_zero_q_(mp_srcptr p, mp_size_t n)
判零函数
定义 cmp.c:55
void lmmp_sqr_mersenne_dc_(mp_ptr dst, mp_size_t rn, mp_srcptr numa, mp_size_t na)
分治梅森数模平方 [dst,rn] = [numa,na]^2 mod B^rn-1
mp_limb_t lmmp_shl_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shl)
左移操作 [dst,na] = [numa,na]<<shl,dst的低shl位填充0
定义 shl.c:26
#define LMMP_ADDCB_(r, x, y)
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
void lmmp_mul_toom8h_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-8.5乘法运算 [dst,na+nb] = [numa,na] * [numb,nb] (非对称切分+条件inf点,原生支持不平衡;评估点 inf,±8,...
void lmmp_mul_toom53_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-53乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mullo_fft_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_ptr scratch)
低位FFT乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
定义 mullo.c:68
mp_size_t lmmp_to_decimal_len_(mp_srcptr numa, mp_size_t na)
计算转换为十进制字符串需要的缓冲区长度
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
void lmmp_inv_basecase_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
近似逆元计算
mp_size_t lmmp_from_decimal_len_(const char *src, mp_size_t len)
计算十进制字符串转limb数组所需的 limb 缓冲区长度
mp_limb_t lmmp_add_n_sub_n_(mp_ptr dsta, mp_ptr dstb, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
同时执行n位加法和减法 ([dsta,n],[dstb,n]) = ([numa,n]+[numb,n],[numa,n]-[numb,n])
static bool lmmp_endian(void)
运行时判断端序
定义 lmmpn.h:40
mp_size_t lmmp_from_hex_(mp_ptr dst, const char *src, mp_size_t len)
十六进制字符串转limb数组 [src,len,16] to [dst,return value,B]
mp_limb_t lmmp_div_mulinv_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_srcptr invappr, mp_size_t ni)
乘法逆元除法
void lmmp_inv_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t nf)
求逆操作 [dst,na+nf+1] = (B^(2*(na+nf)) - 1) / ([numa,na]*B^nf) + [0|-1]
定义 inv.c:173
static mp_limb_t lmmp_sub_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
减单精度数静态内联函数 [dst,na]=[numa,na]-x
mp_limb_t lmmp_div_2_s_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb)
双精度数除法(除数为2个limb)
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
void lmmp_mul_fft_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
FFT乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_not_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
按位取反操作 [dst,na] = ~[numa,na] (对每个limb执行按位非操作)
定义 not.c:26
mp_limb_t lmmp_submul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累减操作 [numa,n] -= [numb,n] * b
mp_limb_t lmmp_sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无借位的n位减法 [dst,n] = [numa,n] - [numb,n]
定义 sub_n.c:84
mp_limb_t lmmp_inv_1_(mp_limb_t x)
1阶逆元计算 (inv1)
定义 inv.c:124
mp_limb_t lmmp_shr1sub_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
减法后右移1位 [dst,n] = ([numa,n] - [numb,n]) >> 1
定义 shr.c:87
void lmmp_sqr_toom6_(mp_ptr dst, mp_srcptr numa, mp_size_t na)
Toom-6平方运算 [dst,2*na] = [numa,na]^2 (评估点 ±4,±2,±1,±1/2,±1/4,0,无inf点)
mp_limb_t lmmp_inv_2_1_(mp_limb_t xh, mp_limb_t xl)
2-1阶逆元计算 (inv21)
定义 inv.c:27
mp_limb_t lmmp_div_basecase_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
基础除法运算
void lmmp_mul_toom62_unbalance_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-62不平衡乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_mullo_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
低位乘法 [dst,n] = [numa,n] * [numb,n] mod B^n
mp_limb_t lmmp_sub_nc_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t c)
带借位的n位减法 [dst,n] = [numa,n] - [numb,n] - c
定义 sub_n.c:67
mp_limb_t lmmp_div_divide_(mp_ptr dstq, mp_ptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb, mp_limb_t inv21)
分治除法运算
mp_size_t lmmp_mersenne_next_size_(mp_size_t n)
计算满足 >=n 的最小分治梅森乘法可行尺寸
mp_limb_t lmmp_add_n_(mp_ptr dst, mp_srcptr numa, mp_srcptr numb, mp_size_t n)
无进位的n位加法 [dst,n] = [numa,n] + [numb,n]
定义 add_n.c:76
void lmmp_mul_toom33_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
Toom-33乘法运算 [dst,na+nb] = [numa,na] * [numb,nb]
void lmmp_sqr_toom4_(mp_ptr dst, mp_srcptr numa, mp_size_t an)
Toom-4平方运算 [dst,2*na] = [numa,na]^2
mp_size_t lmmp_from_str_len_(const mp_byte_t *src, mp_size_t len, int base)
计算字节数组转limb数组所需的 limb 缓冲区长度
#define numb
#define tp
#define n
#define scratch