|
LMMP 4.3.0
Lamina High-Precision Arithmetic Library
|
#include "numth/gcd.h"#include "impl/inlines.h"#include "impl/longlong.h"#include "mparam.h"#include "impl/tmp_alloc.h"#include "lmmp/lmmpn.h"#include "lmmp/numth.h"函数 | |
| static mp_size_t | gcdext_pick_s_ (mp_ptr sp, int *sneg, mp_srcptr u0p, mp_size_t u0n, mp_srcptr u1p, mp_size_t u1n, int det, mp_ptr t1) |
| static void | gcdext_row_mul_ (mp_ptr u0p, mp_ptr u1p, mp_size_t *u0n, mp_size_t *u1n, const lmmp_hgcd_matrix_t *M1, lmmp_hgcd_scratch_t *sc) |
| static void | gcdext_row_qscalar_ (mp_ptr *u0p, mp_ptr *u1p, mp_size_t *u0n, mp_size_t *u1n, ulong q) |
| Copyright (C) 2026 HJimmyK (Jericho Knox) | |
| 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 | |
| mp_size_t | lmmp_gcdext_derive_ (mp_ptr dst, int *tneg, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp, mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt) |
| 导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除) | |
| void | lmmp_gcdext_emit_ (mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt, mp_ptr qt) |
| 发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出 | |
| 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_modinv_ (mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t mn) |
| 模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn] | |
| ulong | lmmp_modinv_ulong_ (ulong u, ulong m) |
| 模逆元(单 limb):求 u^{-1} mod m | |
|
static |
引用了 gcdext_pick_s_(), lmmp_cmp_(), lmmp_copy, lmmp_mul_1_() , 以及 lmmp_sub_().
被这些函数引用 gcdext_pick_s_() , 以及 lmmp_gcdext_hgcd_().
|
static |
引用了 gcdext_row_mul_(), lmmp_add_(), lmmp_copy, lmmp_gcd_matrix_maxlen_(), lmmp_gcd_mul_(), lmmp_hgcd_salloc_(), M1 , 以及 lmmp_hgcd_scratch_t::used.
被这些函数引用 gcdext_row_mul_() , 以及 lmmp_gcdext_hgcd_().
|
static |
Copyright (C) 2026 HJimmyK (Jericho Knox)
This file is part of LMMP.
LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.
SPDX-License-Identifier: LGPL-3.0-or-later
引用了 gcdext_row_qscalar_(), lmmp_add_1_(), lmmp_addmul_1_(), LMMP_SWAP , 以及 lmmp_zero.
被这些函数引用 gcdext_row_qscalar_() , 以及 lmmp_gcdext_hgcd_().
| 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
| dstg | 结果指针(长度至少为 min(un,vn)) |
| dsts | u 的贝祖系数幅度(长度至少为 vn 个limb) |
| sn | 输出 s 的带符号 limb 长度 |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
引用了 GCD_HGCD_THRESHOLD, lmmp_gcdext_(), lmmp_gcdext_1_(), lmmp_gcdext_2_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_() , 以及 lmmp_param_assert.
被这些函数引用 lmmp_gcdext_(), lmmp_modinv_(), run_gcdext_pair(), TEST_CASE() , 以及 TEST_CASE().
| mp_size_t lmmp_gcdext_derive_ | ( | mp_ptr | dst, |
| int * | tneg, | ||
| mp_srcptr | gp, | ||
| mp_size_t | gn, | ||
| mp_srcptr | sp, | ||
| mp_size_t | sn, | ||
| int | sneg, | ||
| mp_srcptr | xp, | ||
| mp_size_t | xn, | ||
| mp_srcptr | yp, | ||
| mp_size_t | yn, | ||
| mp_ptr | nb, | ||
| mp_ptr | yt, | ||
| mp_ptr | qt ) |
导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
| dst | 输出(容量 >= xn+2) |
| tneg | 出参,tv 的符号 |
| gp | g(归一化) |
| gn | g 的长度 |
| sp | S 的幅度(归一化) |
| sn | S 的幅度长 |
| sneg | S 的符号 |
| xp | 值序大者原对(归一化) |
| xn | 其长度 |
| yp | 值序小者原对(归一化) |
| yn | 其长度 |
| nb | 全乘积暂存(容量 >= xn+yn+2) |
| yt | Y 奇化暂存(容量 >= yn+1) |
| qt | 整商暂存(容量 >= xn+2;lmmp_divexact_ 写入长 nn-yn2+1 可超 出 dst 公开容量,先落此处再按归一化长度拷出) |
引用了 ctz_shr_u64, lmmp_add_(), lmmp_copy, lmmp_debug_assert, lmmp_divexact_(), lmmp_gcdext_derive_(), lmmp_mul_(), lmmp_shr_(), lmmp_sub_(), xn , 以及 xp.
被这些函数引用 lmmp_gcdext_derive_() , 以及 lmmp_gcdext_emit_().
| void lmmp_gcdext_emit_ | ( | mp_ptr | dstg, |
| mp_ptr | dsts, | ||
| mp_ssize_t * | sn, | ||
| mp_ptr | dstt, | ||
| mp_ssize_t * | tn, | ||
| mp_srcptr | gp, | ||
| mp_size_t | gn, | ||
| mp_srcptr | sp, | ||
| mp_size_t | sun, | ||
| int | suneg, | ||
| int | sw, | ||
| mp_srcptr | up, | ||
| mp_size_t | un, | ||
| mp_srcptr | vp, | ||
| mp_size_t | vn, | ||
| mp_ptr | nb, | ||
| mp_ptr | yt, | ||
| mp_ptr | qt ) |
发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出
| dstg | 结果 g 输出(容量 >= gn) |
| dsts | u 侧系数输出(容量 >= max(un,vn)+1) |
| sn | 输出 s 的带符号长度 |
| dstt | v 侧系数输出(容量 >= max(un,vn)+1,可为 NULL 表示不需要) |
| tn | 输出 t 的带符号长度(dstt==NULL 时忽略,可为 NULL) |
| gp | g(归一化) |
| gn | g 的长度 |
| sp | S 的幅度(归一化) |
| sun | S 的幅度长 |
| suneg | S 的符号 |
| sw | 值序归一化的交换标志(1 表示 up/vp 已交换,S 为 vp 侧系数) |
| up | 值序大者原对 |
| un | 其长度 |
| vp | 值序小者原对 |
| vn | 其长度 |
| nb | 导出全乘积暂存(容量 >= 2*max(un,vn)+4) |
| yt | 导出奇化暂存(容量 >= max(un,vn)+2) |
| qt | 导出整商暂存(容量 >= max(un,vn)+2) |
引用了 lmmp_copy, lmmp_gcdext_derive_() , 以及 lmmp_gcdext_emit_().
被这些函数引用 lmmp_gcdext_emit_(), lmmp_gcdext_hgcd_() , 以及 lmmp_gcdext_lehmer_().
| 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
| dstg | 结果指针(长度至少为 min(un,vn)) |
| dsts | u 的贝祖系数幅度(长度至少为 vn 个limb,s==0 时写 0) |
| sn | 输出 s 的带符号 limb 长度([1|-1|0]) |
| dstt | v 的贝祖系数幅度(长度至少为 un 个limb,可为 NULL) |
| tn | 输出 t 的带符号 limb 长度(dstt==NULL 时忽略) |
| up | 第一个无符号整数指针 |
| un | 第一个无符号整数的 limb 长度 |
| vp | 第二个无符号整数指针 |
| vn | 第二个无符号整数的 limb 长度 |
引用了 ALLOC_TYPE, gcdext_pick_s_(), gcdext_row_mul_(), gcdext_row_qscalar_(), HGCD_RECURSE_THRESHOLD, lmmp_add_(), lmmp_cmp_(), lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_gcd_matrix_init_buf_(), lmmp_gcd_matrix_maxlen_(), lmmp_gcd_matrix_swap_cols_(), lmmp_gcd_mul_(), lmmp_gcd_norm_(), lmmp_gcdext_emit_(), lmmp_gcdext_hgcd_(), lmmp_gcdext_lehmer_(), lmmp_gcdext_smag_(), lmmp_hgcd_adjust_(), lmmp_hgcd_core_(), lmmp_hgcd_salloc_(), lmmp_hgcd_scratch_size_(), lmmp_mul_1_(), lmmp_param_assert, lmmp_sub_(), LMMP_SWAP, lmmp_zero, M1, n , 以及 r0.
被这些函数引用 lmmp_gcdext_() , 以及 lmmp_gcdext_hgcd_().
模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
| dst | 结果指针(长度至少为 mn 个limb) |
| up | 被求逆元数指针 |
| un | 被求逆元数的 limb 长度 |
| mp | 模数指针 |
| mn | 模数的 limb 长度 |
引用了 BALLOC_TYPE, lmmp_cmp_(), lmmp_copy, lmmp_debug_assert, lmmp_div_(), lmmp_gcdext_(), lmmp_mod_1_(), lmmp_modinv_(), lmmp_modinv_ulong_(), lmmp_param_assert, lmmp_sub_(), s, TEMP_B_DECL , 以及 TEMP_B_FREE.
被这些函数引用 lmmp_modinv_() , 以及 TEST_CASE().
模逆元(单 limb):求 u^{-1} mod m
| u | 被求逆元数 |
| m | 模数 |
引用了 lmmp_gcdext_11_(), lmmp_modinv_ulong_(), lmmp_param_assert , 以及 s.
被这些函数引用 lmmp_modinv_(), lmmp_modinv_ulong_() , 以及 TEST_CASE().