LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
test_modinv.c 文件参考
#include "lmmp/lmmpn.h"
#include "lmmp/numth.h"
#include "cases.h"
#include "support/lmmp_test_utils.h"
test_modinv.c 的引用(Include)关系图:

浏览该文件的源代码.

函数

static u64 gcd_u64 (u64 a, u64 b)
 Copyright (C) 2026 HJimmyK (Jericho Knox)
 TEST_CASE ("numth/modinv", modinv_big)
 TEST_CASE ("numth/modinv", modinv_ulong)
void test_modinv (void)

函数说明

◆ gcd_u64()

u64 gcd_u64 ( u64 a,
u64 b )
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

在文件 test_modinv.c 第 36 行定义.

36 {
37 while (b) {
38 u64 t = a % b;
39 a = b;
40 b = t;
41 }
42 return a;
43}
mp_limb_t u64
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define t

引用了 gcd_u64() , 以及 t.

函数调用图:

◆ TEST_CASE() [1/2]

TEST_CASE ( "numth/modinv" ,
modinv_big  )

在文件 test_modinv.c 第 87 行定义.

87 {
88 u64 seed = 0x2b44ae9d4d6c8f13ull;
89 const mp_size_t mn_values[] = {2, 3, 5, 9, 17, 33, 60};
90 for (size_t mn_index = 0; mn_index < ARRAY_SIZE(mn_values); ++mn_index) {
91 mp_size_t mn = mn_values[mn_index];
92 for (int iter = 0; iter < 7; ++iter) {
93 mp_ptr m = alloc_limbs(mn);
94 random_limbs(m, mn, &seed);
95 m[0] |= 1;
96 mp_ptr u;
97 mp_size_t un;
98 if (iter == 6) {
99 // un < mn:u 直接取短随机数(覆盖 modinv 短分支)
100 un = mn / 2 > 0 ? mn / 2 : 1;
101 u = alloc_limbs(un);
102 random_limbs(u, un, &seed);
103 u[0] |= 1;
104 } else if (iter % 2 == 0) {
105 // u = m + 1(与 m 互素)
106 un = mn;
107 u = alloc_limbs(mn + 1);
108 lmmp_copy(u, m, mn);
109 lmmp_zero(u + mn, 1);
110 add_small_inplace(u, mn + 1, 1);
111 un = norm_len(u, mn + 1);
112 } else {
113 un = mn;
114 u = alloc_limbs(un);
115 random_limbs(u, un, &seed);
116 u[0] |= 1;
117 }
118 mp_ptr dst = alloc_limbs(mn);
119 mp_size_t rn = lmmp_modinv_(dst, u, un, m, mn);
120 // 互素性与逆元验证(库交叉):inv*u mod m == 1
121 mp_ptr gr = alloc_limbs(un > mn ? un : mn);
122 mp_size_t gn = lmmp_gcd_(gr, u, un, m, mn);
123 if (gn == 1 && gr[0] == 1) {
124 TEST_CHECK_MSG(rn > 0, "inverse exists");
125 mp_ptr prod = alloc_limbs(mn + un + 1), q = alloc_limbs(mn + un + 1),
126 r = alloc_limbs(mn);
127 if (rn >= un) lmmp_mul_(prod, dst, rn, u, un);
128 else lmmp_mul_(prod, u, un, dst, rn);
129 lmmp_div_(q, r, prod, rn + un, m, mn);
130 TEST_CHECK_MSG(norm_len(r, mn) == 1 && r[0] == 1, "inv*u mod m == 1");
131 TEST_CHECK_MSG(mpn_cmp(dst, rn, m, mn) < 0, "inverse in range");
133 } else {
134 TEST_CHECK_MSG(rn == 0, "non-invertible reported");
135 }
136 lmmp_free(gr);
137 // dst 与 u 别名(eqsep 契约)
138 mp_ptr u2 = alloc_limbs(un > mn ? un : mn);
139 lmmp_copy(u2, u, un);
140 mp_size_t rn2 = lmmp_modinv_(u2, u2, un, m, mn);
141 TEST_CHECK_MSG(rn2 == rn && (rn == 0 || mpn_cmp(u2, rn2, dst, rn) == 0),
142 "alias stable");
143 lmmp_free(m); lmmp_free(u); lmmp_free(dst); lmmp_free(u2);
144 }
145 }
146}
#define prod
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
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]
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
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]
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
#define ARRAY_SIZE(a)
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 perf.h:40
#define TEST_CHECK_MSG(cond, msg)
定义 test.h:38

引用了 ARRAY_SIZE, lmmp_copy, lmmp_div_(), lmmp_free(), lmmp_gcd_(), lmmp_modinv_(), lmmp_mul_(), lmmp_zero, prod, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ TEST_CASE() [2/2]

TEST_CASE ( "numth/modinv" ,
modinv_ulong  )

在文件 test_modinv.c 第 45 行定义.

45 {
46 // 穷举小值(u*inv mod m 经 mod_1 判模)
47 for (u64 m = 1; m <= 200; ++m) {
48 for (u64 u = 1; u <= 200; ++u) {
49 ulong inv = lmmp_modinv_ulong_(u, m);
50 if (m == 1) {
51 TEST_CHECK_MSG(inv == 0, "m=1 inverse is 0");
52 continue;
53 }
54 u64 r = u % m;
55 ulong g = (r == 0) ? m : gcd_u64(r, m);
56 if (g != 1) {
57 TEST_CHECK_MSG(inv == 0, "non-invertible");
58 } else {
59 mp_limb_t prod[2];
60 lmmp_mullh_(u, inv, prod);
61 TEST_CHECK_MSG(lmmp_mod_1_(prod, 2, m) == 1 && inv < m, "inverse");
62 }
63 }
64 }
65 // 随机 64 位
66 u64 seed = 0x51ce1b7ea4df7c21ull;
67 for (int i = 0; i < 20000; ++i) {
68 u64 m = xorshift64(&seed);
69 u64 u = xorshift64(&seed);
70 if (m == 0) m = 1;
71 if (u == 0) u = 1;
72 ulong inv = lmmp_modinv_ulong_(u, m);
73 u64 r = u % m;
74 ulong g = (r == 0) ? m : gcd_u64(r, m);
75 if (m == 1) {
76 TEST_CHECK_MSG(inv == 0, "m=1");
77 } else if (g != 1) {
78 TEST_CHECK_MSG(inv == 0, "non-invertible random");
79 } else {
80 mp_limb_t prod[2];
81 lmmp_mullh_(u, inv, prod);
82 TEST_CHECK_MSG(lmmp_mod_1_(prod, 2, m) == 1 && inv < m, "inverse random");
83 }
84 }
85}
#define lmmp_mullh_
uint64_t mp_limb_t
定义 lmmp.h:92
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
ulong lmmp_modinv_ulong_(ulong u, ulong m)
模逆元(单 limb):求 u^{-1} mod m
uint64_t ulong
定义 numth.h:39
static u64 gcd_u64(u64 a, u64 b)
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 gcd_u64(), lmmp_mod_1_(), lmmp_modinv_ulong_(), lmmp_mullh_, prod, TEST_CASE , 以及 TEST_CHECK_MSG.

函数调用图:

◆ test_modinv()

void test_modinv ( void )

在文件 test_modinv.c 第 148 行定义.

148 {
149 TEST_RUN("numth/modinv", modinv_ulong);
150 TEST_RUN("numth/modinv", modinv_big);
151}
#define TEST_RUN(category, name)
定义 test.h:36

引用了 test_modinv() , 以及 TEST_RUN.

被这些函数引用 main() , 以及 test_modinv().

函数调用图:
这是这个函数的调用关系图: