LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
trialdiv.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_TRIALDIV_H__
24
#define __LMMP_TRIALDIV_H__
25
26
#include "
lmmp/numth.h
"
27
#include "
lmmp/lmmpn.h
"
28
29
/**
30
* @brief 试除法:判定 [np,nn] 是否存在小奇素数因子
31
* @param np 被除数(长度为 nn 个limb)
32
* @param nn 被除数的 limb 长度
33
* @param N 试除上界提示
34
* @warning np!=NULL, nn>0
35
* @note 试除素数自 3 起(因子 2 由调用方自理);N 仅为上界提示——实际试除
36
* 范围为所有含 <=N 素数的块之并(块粒度向上取整,可能试除 N 之后的
37
* 素数),需要精确 N 边界者勿用
38
* @return 存在能整除 [np,nn] 的试除素数则返回true,否则返回false
39
*/
40
bool
lmmp_trialdiv_
(
mp_srcptr
np,
mp_size_t
nn,
ushort
N);
41
42
/* 全局试除块表释放(lmmp_global_entries 钩子;表本身首次试除时惰性构建) */
43
void
lmmp_trialdiv_table_free_
(
void
);
44
45
/**
46
* @brief 4 链折叠取模:r = [numa,na] mod d
47
* @param numa 被除数(长度为 na 个limb)
48
* @param na 被除数的 limb 长度
49
* @param d 除数(单个 limb)
50
* @param dinv 除数的逆元(d*dinv==1 mod 2^64)
51
* @param r2 蒙域预处理(r2=B^2 mod d)
52
* @param base 蒙域预处理(base=B mod d)
53
* @param mi 蒙域预处理(mi=-dinv mod 2^64)
54
* @warning na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64,
55
* dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
56
* @return [numa,na] mod d
57
*/
58
mp_limb_t
lmmp_mod_4chunk_1_
(
mp_srcptr
numa,
mp_size_t
na,
mp_limb_t
d,
mp_limb_t
dinv,
59
mp_limb_t
r2
,
mp_limb_t
base,
mp_limb_t
mi);
60
61
/**
62
* @brief 8 链折叠取模:r = [numa,na] mod d
63
* @param numa 被除数(长度为 na 个limb)
64
* @param na 被除数的 limb 长度
65
* @param d 除数(单个 limb)
66
* @param dinv 除数的逆元(d*dinv==1 mod 2^64)
67
* @param r2 蒙域预处理(r2=B^2 mod d)
68
* @param base 蒙域预处理(base=B mod d)
69
* @param mi 蒙域预处理(mi=-dinv mod 2^64)
70
* @warning na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64,
71
* dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
72
* @return [numa,na] mod d
73
*/
74
mp_limb_t
lmmp_mod_8chunk_1_
(
mp_srcptr
numa,
mp_size_t
na,
mp_limb_t
d,
mp_limb_t
dinv,
75
mp_limb_t
r2
,
mp_limb_t
base,
mp_limb_t
mi);
76
77
// 3,5,7,11的余数掩码表
78
extern
const
mp_limb_t
r35711_mask_map
[19];
79
80
/**
81
* @brief 校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0
82
*/
83
static
inline
int
trial_div35711
(
ulong
n
) {
84
uint
rem =
n
% 1155;
// 1155 = 3 * 5 * 7 * 11
85
uint
idx = rem /
LIMB_BITS
;
86
uint
bit = rem %
LIMB_BITS
;
87
return
(
r35711_mask_map
[idx] >> bit) & 1ULL;
88
}
89
90
#endif
/* __LMMP_TRIALDIV_H__ */
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
LIMB_BITS
#define LIMB_BITS
定义
lmmp.h:102
lmmpn.h
r2
#define r2
n
#define n
numth.h
uint
uint32_t uint
定义
numth.h:38
ushort
uint16_t ushort
定义
numth.h:36
ulong
uint64_t ulong
定义
numth.h:39
trial_div35711
static int trial_div35711(ulong n)
校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0
定义
trialdiv.h:83
lmmp_mod_8chunk_1_
mp_limb_t lmmp_mod_8chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
8 链折叠取模:r = [numa,na] mod d
定义
mod_chunk.c:114
r35711_mask_map
const mp_limb_t r35711_mask_map[19]
定义
trialdiv.c:216
lmmp_trialdiv_table_free_
void lmmp_trialdiv_table_free_(void)
定义
trialdiv.c:205
lmmp_trialdiv_
bool lmmp_trialdiv_(mp_srcptr np, mp_size_t nn, ushort N)
Copyright (C) 2026 HJimmyK (Jericho Knox)
lmmp_mod_4chunk_1_
mp_limb_t lmmp_mod_4chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
4 链折叠取模:r = [numa,na] mod d
定义
mod_chunk.c:52
src
lmmp
impl
trialdiv.h
生成于
, 为 LMMP使用
1.18.0